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.

La sécurité de la propriété d'un UOWHF est comme suit. Soit ${\displaystyle A}$ un algorithme qui fonctionne en deux phases :

• Dans un premier temps, ${\displaystyle A}$ prend en entrée le paramètre de sécurité et choisit une valeur ${\displaystyle x}$ ;
• Une fonction de hachage ${\displaystyle H}$ est choisie uniformément au hasard à partir de la famille de fonctions. L’adversaire ${\displaystyle A}$ reçoit alors ${\displaystyle H}$ et doit renvoyer une valeur ${\displaystyle y\neq x}$ telle que ${\displaystyle H(x)=H(y)}$.

On dit que l'UOWHF est sûre si pour tout PPT ${\displaystyle A}$, la probabilité que ${\displaystyle A}$ gagne dans le jeu ci-dessus est négligeable.

Les UOWHFs sont conçues pour être moins gourmandes 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).

• Oded Goldreich, Foundations of Cryptography, vol. 2, Cambridge University Press, 2004 (lire en ligne)
• Moni Naor et Moti Yung, « Universal one-way hash functions and their cryptographic applications », STOC, ACM,‎ 1989, p. 33–43

• Fonctions de hachage
• Attaque de préimage

• Moni Naor et Moti Yung, « Universal One-Way Hash Functions and their Cryptographic Applications », 1989.

• Portail de la cryptologie
• Portail de l'informatique théorique