Séparation (cryptologie)

Parmi les premiers résultats de séparation, Impagliazzo et Rudich[3] - [4] ont montré en 1988 que l'échange de clé ne pouvait pas découler de la seule existence de fonctions à sens unique[Note 1] - [5]. Leur technique (dite de « relativisation ») a permis de montrer notamment :

• Que l'existence de fonctions à sens unique (OWF) ne suffit pas à montrer l'existence de fonctions résistantes aux collisions[6] (CR) ;
• Que l'existence du chiffrement à clé publique (PKE) est incomparable à l'existence du transfert inconscient[7] (OT) ;
• Que l'existence de fonctions à trappe (TDF) ne suffit pas à montrer l'existence des preuves à divulgation nulle statistiques[8] (SZK) ;

À partir de 2004, de nouvelles techniques de preuves ont été introduites ne reposant pas sur la relativisation[9], permettant notamment de montrer :

• Qu'il n'y a pas de réduction entre fonctions résistantes aux collisions utilisant des aléas public et utilisant des aléas secrets[9] ;
• Que l'existence de fonctions à sens unique (OWF) est incomparable à l'existence de fonctions non malléables[10] ;
• Que le modèle de l'oracle aléatoire non programmable ne permet pas de preuve par réduction pour les signatures FDH[11];
• Que les fonctions aléatoires vérifiables (VRF) ne peuvent pas être construites à partir de fonctions à sens unique[12] (OWF) ni de fonctions à trappe[13] (TDF).

La technique de « méta-réduction[Note 2] » est apparue initialement dans l'étude des problèmes RSA[14] - [15] et du logarithme discret[16]. Elle a permis notamment de montrer :

• Que plusieurs protocoles classiques (authentification de Schnorr, engagements non malléables, etc.) ne peuvent être basés sur aucune hypothèse standard[17] ;
• Que la sécurité des arguments succincts non interactifs (SNARGs) ne peut être basée sur aucune hypothèse falsifiable[18] ;

ainsi que de raffiner les résultats de séparation pour les signatures RSA-FDH[19] et Schnorr[20].