Fonction à trappe

Représentation d'une fonction à trappe. Il est facile d'évaluer la fonction mais son inversion est complexe sauf si la clé t est connue.

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 ».

Histoire

La notion de fonction à trappe a été introduite par les cryptologues américains Whitfield Diffie et Martin Hellman en 1979, 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. É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.

La question de l'existence de fonctions à trappes a été difficile, le premier exemple pratique étant dû à Rivest, Shamir et Adleman en 1976 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. 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 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. 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, et on ignore (en 2018) si combiner les fonctions à sens unique et les permutations pseudo-aléatoires suffit. Cela dit, il existe des constructions ad hoc telles que le chiffrement d'ElGamal ou de Cramer-Shoup reposant sur le logarithme discret.

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, 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 où la trappe est généralement donnée par une « bonne base » d'un réseau euclidien.

Définition

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

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

• La fonction $f$ obtenue en sortie de $G$ est à sens unique, c'est-à-dire que pour tout adversaire efficace $A$ il existe une fonction négligeable $\epsilon$ telle que
  $$\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. $S_{f}=S,T_{f}=T$ et que ce domaine est représentable i.e. $S=\{0,1\}^{\lambda }$.

On peut également demander que les fonctions de ${\mathcal {F}}$ soient des permutations (auquel cas $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.