Fonction de hachage universelle à sens unique
Une fonction de hachage universelle à sens unique (ou UOWHF, pour universal one-way hash function) désigne, en cryptographie, une famille de fonctions de hachage universelle possédant des propriétés de sécurité particulières[1]. Elles ont une importance particulière en cryptographie prouvée. Ces fonctions de hachage ont été proposées comme une alternative aux fonctions résistantes aux collisions. En effet, la résistance aux collisions est une propriété forte, que n'atteint pas nécessairement les UOWHFs. En effet, celles-ci sont seulement à sens unique. Cette primitive a été proposé par Moni Naor et Moti Yung[2], et sont aussi connu sous le nom de fonctions de hachage « résistantes aux collisions ciblées ».
Les UOWHFs ont de multiples applications en cryptographie, comme la conception de signature numériques sans trappes (ce qui les rendent plus efficaces), mais aussi pour la conception de cryptosystèmes sûrs face aux attaques à chiffrés choisis, comme le cryptosystème de Cramer-Shoup.
Une famille de fonctions de hachage universelles à sens unique contient un nombre fini de fonctions de hachage avec possédant chacune la même probabilité d'être utilisée.
Définition modifier
La sécurité de la propriété d'un UOWHF est comme suit. Soit un algorithme qui fonctionne en deux phases :
- Dans un premier temps, prend en entrée le paramètre de sécurité et choisit une valeur ;
- Une fonction de hachage est choisie uniformément au hasard à partir de la famille de fonctions. L’adversaire reçoit alors et doit renvoyer une valeur telle que .
On dit que l'UOWHF est sûre si pour tout PPT , la probabilité que gagne dans le jeu ci-dessus est négligeable.
Applications modifier
Les UOWHFs sont conçues pour être moins gourmand en ressources que fonctions résistantes aux collisions, et sont le plus souvent utilisées à des fins d'efficacité dans les schémas où le choix d'une fonction de hachage apparaît dans l'exécution, et non durant la phase d'initialisation. Par exemple, le cryptosystème de Cramer-Shoup utilise une UOWHF dans le cadre de la vérification de sa validité dans ses chiffrés (qui peut être vue comme une fonction de hachage projective-lisse).
Notes et références modifier
Annexes modifier
Bibliographie modifier
- [Goldreich 2004] Oded Goldreich, Foundations of Cryptography, vol. 2, Cambridge University Press, (lire en ligne)
- [Naor et Yung 1989] Moni Naor et Moti Yung, « Universal one-way hash functions and their cryptographic applications », STOC, ACM, , p. 33–43
Voir aussi modifier
Liens externes modifier
- Moni Naor et Moti Yung, « Universal One-Way Hash Functions and their Cryptographic Applications », 1989.
