« Fonction à trappe » : différence entre les versions
Ϛ (discuter | contributions) création :) |
(Aucune différence)
|
Version du 29 août 2018 à 08:57
En cryptologie, une fonction à trappe ou TDF (pour l'anglais trapdoor function) est un modèle idéalisé permettant de raisonner à propos de systèmes cryptographiques. En première approche, il s'agit d'une fonction qu'il est facile d'évaluer en chaque point de son domaine, mais qu'il est difficile d'inverser à moins de disposer d'une information particulière, appelée « trappe »[Note 1]. La notion de fonction à trappe a été introduite par les cryptologues américains Whitfield Diffie et Martin Hellman en 1979[1], comme une manière de résoudre le problème de la cryptographie à clé publique tel que posé par Ralph Merkle quelques années plus tôt[2],[Note 2]. Étant donnée une fonction à trappe, il est en effet immédiat de construire un algorithme de chiffrement ou de signature numérique. Cependant Diffie et Hellman ne proposent pas de telle fonction dans leur article[1].
La question de l'existence de fonctions à trappes a été difficile, le premier exemple pratique étant dû à Rivest, Shamir et Adleman en 1976[3],[Note 3],[4] et reposant sur le problème RSA. C'est en partie pour ces travaux que les trois reçoivent en 2002 le prestigieux prix Turing. En 1979 Michael Rabin a proposé montré comment construire une fonction à trappe reposant sur le problème de la factorisation[5]. Dans les deux cas, RSA et Rabin, la trappe est donnée par un facteur d'un grand nombre composé.
Dans les années qui suivirent, les progrès en cryptologie (dus notamment à Lamport, Goldwasser-Micali-Rivest, Goldreich-Goldwasser-Micali, Goldreich, Naor-Yung, Rompel[6] et d'autres) ont montré comment construire des algorithmes de signature simplement à partir de fonctions à sens unique, relativisant grandement l'intérêt des fonctions à trappes[6],[7]. Ainsi par exemple, es signatures ECDSA reposent sur le problème du logarithme discret, pour lequel aucune trappe n'est connue. Construire génériquement un chiffrement à clé publique à partir de fonctions à sens unique uniquement est interdit par un résultat de séparation dû à Impagliazzo et Rudich[8], mais il existe des constructions ad hoc telles que le chiffrement d'ElGamal ou de Cramer-Shoup reposant seulement sur le logarithme discret.
Un regain d'intérêt pour les fonctions à trappe est apparu avec le développement de la cryptographie à base de réseaux[9],[10],[11],[12] où la trappe est généralement donnée par une « bonne base » d'un réseau euclidien.
Notes et références
Notes
- Pour que la notion ne soit pas creuse, il faut bien entendu que la trappe ne soit pas elle même facile à calculer à partir d'une représentation de la fonction.
- Les puzzles de Merkle sont un premier pas dans cette direction, mais la difficulté d'inverser le problème reste quadratique (i.e. polynomiale) alors qu'une fonction à trappe exige un avantage négligeable (i.e. exponentiel).
- Voir aussi Ron Rivest, The early days of RSA.
Références
- (en) W. Diffie et M. Hellman, « New directions in cryptography », IEEE Transactions on Information Theory, vol. 22, no 6, , p. 644–654 (ISSN 0018-9448, DOI 10.1109/TIT.1976.1055638, lire en ligne, consulté le )
- (en) Ralph Merkle, "Secure Communication Over Insecure Channels", 1975
- R. L. Rivest, A. Shamir et L. Adleman, « A method for obtaining digital signatures and public-key cryptosystems », Communications of the ACM, vol. 21, no 2, , p. 120–126 (ISSN 0001-0782, DOI 10.1145/359340.359342, lire en ligne, consulté le )
- (en) Rivest, Shamir, Adleman, Cryptographic communications system and method, (lire en ligne)
- (en) M. O. Rabin, « Digitalized Signatures and Public-Key Functions as Intractable as Factorization », Technical Report, MIT, (lire en ligne, consulté le )
- (en) J. Rompel, « One-way functions are necessary and sufficient for secure signatures », STOC '90 Proceedings of the twenty-second annual ACM symposium on Theory of computing, ACM, , p. 387–394 (ISBN 0897913612, DOI 10.1145/100216.100269, lire en ligne, consulté le )
- (en) Boaz Barak, Public Key Cryptography, Lecture 14, Princeton University, (lire en ligne)
- (en) R. Impagliazzo et S. Rudich, « Limits on the provable consequences of one-way permutations », STOC '89 Proceedings of the twenty-first annual ACM symposium on Theory of computing, ACM, , p. 44–61 (ISBN 0897913078, DOI 10.1145/73007.73012, lire en ligne, consulté le )
- (en) Oded Goldreich, Shafi Goldwasser et Shai Halevi, « Public-key cryptosystems from lattice reduction problems », dans Advances in Cryptology — CRYPTO '97, Springer Berlin Heidelberg, (ISBN 9783540633846, DOI 10.1007/bfb0052231, lire en ligne), p. 112–131
- (en) Craig Gentry, Chris Peikert et Vinod Vaikuntanathan, « Trapdoors for hard lattices and new cryptographic constructions », STOC '08 Proceedings of the fortieth annual ACM symposium on Theory of computing, ACM, , p. 197–206 (ISBN 9781605580470, DOI 10.1145/1374376.1374407, lire en ligne, consulté le )
- (en) David Cash, Dennis Hofheinz, Eike Kiltz et Chris Peikert, « Bonsai Trees, or How to Delegate a Lattice Basis », Journal of Cryptology, vol. 25, no 4, , p. 601–639 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-011-9105-2, lire en ligne, consulté le )
- (en) Daniele Micciancio et Chris Peikert, « Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller », dans Advances in Cryptology – EUROCRYPT 2012, Springer Berlin Heidelberg, (ISBN 9783642290107, DOI 10.1007/978-3-642-29011-4_41, lire en ligne), p. 700–718
