Séparation (cryptologie)
Preuve que deux modèles idéaux sont différents
From Wikipedia, the free encyclopedia
En cryptologie, une séparation est une preuve qu'il est impossible d'établir une réduction entre deux modèles de sécurité. De tels résultats s'opposent en principe à l'existence de certaines preuves de sécurité.
Séparation en boîte noire
On considère généralement les résultats de « séparation en boîte noire », qui ne font aucune hypothèse sur la manière dont sont implémentés les modèles[1]. Ces modèles sont généralement plus simples à manier et plus généraux, mais ils laissent en principe ouverte la possibilité que des réductions ad hoc existent (qui tiennent alors compte de l'implémentation de l'objet visé). Les résultats de séparation en boîte noire s'appuient généralement sur l'une des techniques suivantes[2].
Séparation par relativisation
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) ;
Séparation par deux oracles
À 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).
Séparation par méta-réduction
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].
