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

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 Ralph Merkle, "Secure Communication Over Insecure Channels", 1975Les 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).. É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 1976Voir aussi Ron Rivest, The early days of RSA. 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. 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 discretNécessairement, ces constructions utilisent davantage que le sens unique de l'exponentiation modulaire..

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 de fonctions satisfaisant les trois propriétés suivantes :

Il existe un algorithme efficaceGénéralement, une machine de Turing probabiliste. de « génération » qui prend en entrée un paramètre de sécurité en représentation unaire et produit une pairePrécisément : il s'agit d'une paire de chaînes de caractères, de taille au plus polynomiale en , décrivant les fonctions et . de fonctions de ; Il existe un algorithme efficace d'« échantillonnage » , c'est-à-dire un algorithme qui prend en entrée et retourne un élément aléatoire de , distribué de façon uniformeC'est-à-dire que l'avantage d'un adversaire à distinguer la distribution effective des éléments ainsi obtenu d'une distribution uniforme est négligeable. ;

La fonction obtenue en sortie de est à sens unique, c'est-à-dire que pour tout adversaire efficace il existe une fonction négligeable telle que

Une définition moins générale mais plus proche des constructions consiste à supposer que toutes les fonctions ont même domaine, i.e. et que ce domaine est représentable i.e. .

On peut également demander que les fonctions de soient des permutations (auquel cas ), 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.

Notes et références

Notes

Références

Catégorie:Cryptologie