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é 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].