Séparation (cryptologie)

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

Pour les articles homonymes, voir Séparation.

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 :

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

Notes et références

Notes
  1. Sur ce résultat, voir aussi (Brakerski et coll. 2011).
  2. Le nom n'est pas utilisé par (Boneh et Venkatesan 1998) mais est utilisé par (Brown 2005) et dans la littérature ultérieure. Voir aussi (Fischlin 2012).

Références
  1. (en) Omer Reingold, Luca Trevisan et Salil Vadhan, « Notions of Reducibility between Cryptographic Primitives », dans Theory of Cryptography, Springer Berlin Heidelberg, (ISBN 9783540210009, DOI 10.1007/978-3-540-24638-1_1, lire en ligne), p. 1–20
  2. (en) Marc Fischlin, « Black-Box Reductions and Separations in Cryptography », dans Progress in Cryptology - AFRICACRYPT 2012, Springer Berlin Heidelberg, (ISBN 9783642314094, DOI 10.1007/978-3-642-31410-0_26, lire en ligne), p. 413–422
  3. (en) Russell Impagliazzo et Steven Rudich, « Limits on the Provable Consequences of One-way Permutations », dans Advances in Cryptology — CRYPTO’ 88, Springer New York, (ISBN 9780387971964, DOI 10.1007/0-387-34799-2_2, lire en ligne), p. 8–26.
  4. (en) R. Impagliazzo et S. Rudich, « Limits on the provable consequences of one-way permutations », STOC '89 Proceedings of the twenty-first annual ACM symposium on Theory of computing, ACM,‎ , p. 44–61 (ISBN 0897913078, DOI 10.1145/73007.73012, lire en ligne, consulté le ).
  5. (en) Zvika Brakerski, Jonathan Katz, Gil Segev et Arkady Yerukhimovich, « Limits on the Power of Zero-Knowledge Proofs in Cryptographic Constructions », dans Theory of Cryptography, Springer Berlin Heidelberg, (ISBN 9783642195709, DOI 10.1007/978-3-642-19571-6_34, lire en ligne), p. 559–578.
  6. (en) Daniel R. Simon, « Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783540645184, DOI 10.1007/bfb0054137, lire en ligne), p. 334–345.
  7. (en) Y. Gertner, S. Kannan, T. Malkin et O. Reingold, « The relationship between public key encryption and oblivious transfer », Proceedings 41st Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc,‎ (ISBN 0769508502, DOI 10.1109/sfcs.2000.892121, lire en ligne, consulté le ).
  8. (en) Marc Fischlin, « On the Impossibility of Constructing Non-interactive Statistically-Secret Protocols from Any Trapdoor One-Way Function », dans Topics in Cryptology — CT-RSA 2002, Springer Berlin Heidelberg, (ISBN 9783540432241, DOI 10.1007/3-540-45760-7_7, lire en ligne), p. 79–95.
  9. (en) Chun-Yuan Hsiao et Leonid Reyzin, « Finding Collisions on a Public Road, or Do Secure Hash Functions Need Secret Coins? », dans Advances in Cryptology – CRYPTO 2004, Springer Berlin Heidelberg, (ISBN 9783540226680, DOI 10.1007/978-3-540-28628-8_6, lire en ligne), p. 92–105
  10. (en) Alexandra Boldyreva, David Cash, Marc Fischlin et Bogdan Warinschi, « Foundations of Non-malleable Hash and One-Way Functions », dans Advances in Cryptology – ASIACRYPT 2009, Springer Berlin Heidelberg, (ISBN 9783642103650, DOI 10.1007/978-3-642-10366-7_31, lire en ligne), p. 524–541
  11. (en) Marc Fischlin, Anja Lehmann, Thomas Ristenpart et Thomas Shrimpton, « Random Oracles with(out) Programmability », dans Advances in Cryptology - ASIACRYPT 2010, Springer Berlin Heidelberg, (ISBN 9783642173721, DOI 10.1007/978-3-642-17373-8_18, lire en ligne), p. 303–320
  12. (en) Zvika Brakerski, Shafi Goldwasser, Guy N. Rothblum et Vinod Vaikuntanathan, « Weak Verifiable Random Functions », dans Theory of Cryptography, Springer Berlin Heidelberg, (ISBN 9783642004568, DOI 10.1007/978-3-642-00457-5_33, lire en ligne), p. 558–576
  13. (en) Dario Fiore et Dominique Schröder, « Uniqueness Is a Different Story: Impossibility of Verifiable Random Functions from Trapdoor Permutations », dans Theory of Cryptography, Springer Berlin Heidelberg, (ISBN 9783642289132, DOI 10.1007/978-3-642-28914-9_36, lire en ligne), p. 636–653
  14. (en) Dan Boneh et Ramarathnam Venkatesan, « Breaking RSA may not be equivalent to factoring », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783540645184, DOI 10.1007/bfb0054117, lire en ligne), p. 59–71
  15. (en) Daniel R. L. Brown, « Breaking RSA May Be As Difficult As Factoring », Journal of Cryptology, vol. 29, no 1,‎ , p. 220–241 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-014-9192-y, lire en ligne, consulté le )
  16. (en) Pascal Paillier et Damien Vergnaud, « Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783540306849, DOI 10.1007/11593447_1, lire en ligne), p. 1–20
  17. (en) Rafael Pass, « Limits of provable security from standard assumptions », STOC '11 Proceedings of the forty-third annual ACM symposium on Theory of computing, ACM,‎ , p. 109–118 (ISBN 9781450306911, DOI 10.1145/1993636.1993652, lire en ligne, consulté le )
  18. (en) Craig Gentry et Daniel Wichs, « Separating succinct non-interactive arguments from all falsifiable assumptions », STOC '11 Proceedings of the forty-third annual ACM symposium on Theory of computing, ACM,‎ , p. 99–108 (ISBN 9781450306911, DOI 10.1145/1993636.1993651, lire en ligne, consulté le )
  19. (en) Yevgeniy Dodis, Iftach Haitner et Aris Tentes, « On the Instantiability of Hash-and-Sign RSA Signatures », dans Theory of Cryptography, Springer Berlin Heidelberg, (ISBN 9783642289132, DOI 10.1007/978-3-642-28914-9_7, lire en ligne), p. 112–132
  20. (en) Yannick Seurin, « On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model », dans Advances in Cryptology – EUROCRYPT 2012, Springer Berlin Heidelberg, (ISBN 9783642290107, DOI 10.1007/978-3-642-29011-4_33, lire en ligne), p. 554–571
  • Portail de la cryptologie
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.