Fonction à trappe

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é 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é de montrer 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, les 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], et on ignore (en 2018) si combiner les fonctions à sens unique et les permutations pseudo-aléatoires suffit^[7]. Cela dit, il existe des constructions ad hoc telles que le chiffrement d'ElGamal ou de Cramer-Shoup reposant sur le logarithme discret^{[Note 4]}.

Comme mentionné plus haut, une fonction à trappe donne immédiatement un schéma de chiffrement à clé publique. Cependant il n'est pas possible de construire génériquement une fonction à trappe à partir d'un chiffrement à clé publique^[9], les deux notions étant séparées en boîte noire.

Un regain d'intérêt pour les fonctions à trappe est apparu avec le développement de la cryptographie à base de réseaux^{[10],[11],[12],[13]} où la trappe est généralement donnée par une « bonne base » d'un réseau euclidien.

Une collection de fonctions à trappe est la donnée d'un ensemble ${\displaystyle {\mathcal {F}}}$ de fonctions ${\displaystyle f:S_{f}\to T_{f}}$ satisfaisant les trois propriétés suivantes^[7] :

• Il existe un algorithme efficace^{[Note 5]} de « génération » ${\displaystyle G}$ qui prend en entrée un paramètre de sécurité en représentation unaire ${\displaystyle 1^{\lambda }}$ et produit une paire^{[Note 6]} ${\displaystyle (f,f^{-1})}$ de fonctions de ${\displaystyle {\mathcal {F}}}$ ;
• Il existe un algorithme efficace d'« échantillonnage » ${\displaystyle U}$, c'est-à-dire un algorithme qui prend en entrée ${\displaystyle f}$ et retourne un élément aléatoire de ${\displaystyle S_{f}}$, distribué de façon uniforme^{[Note 7]} ;

• La fonction ${\displaystyle f}$ obtenue en sortie de ${\displaystyle G}$ est à sens unique, c'est-à-dire que pour tout adversaire efficace ${\displaystyle A}$ il existe une fonction négligeable ${\displaystyle \epsilon }$ telle que $${\displaystyle \Pr _{(f,f^{-1})\gets G,x\gets U(f)}\left[A\left(1^{\lambda },f,f(x)\right)=x\right]<\epsilon (\lambda )}$$

Une définition moins générale mais plus proche des constructions consiste à supposer que toutes les fonctions ont même domaine, i.e. ${\displaystyle S_{f}=S,T_{f}=T}$ et que ce domaine est représentable i.e. ${\displaystyle S=\{0,1\}^{\lambda }}$^[14].

On peut également demander que les fonctions de ${\displaystyle {\mathcal {F}}}$ soient des permutations (auquel cas ${\displaystyle S=T}$), et on parle alors de « permutations à trappe ». À l'heure actuelle (2018) la seule construction connue susceptible de donner une permutation à trappe repose sur le problème RSA ou une variante mineure de celui-ci^[14].

• Portail de la cryptologie