Fonction de hachage universelle à sens unique

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