Modèle standard (cryptologie)

En cryptologie, dans le contexte des preuves de sécurité, le modèle standard[Note 1] désigne un cadre conceptuel dans lequel on s'interdit de considérer des modèles idéalisés (modèles de l'oracle aléatoire, du chiffre idéal, du groupe générique, etc.) des objets mathématiques en jeu[1]. Une preuve dans le modèle standard est considérée beaucoup plus solide qu'une preuve dans un modèle idéal[2], ce qui est appuyé par l'existence de constructions sûres dans ces modèles idéaux mais cassés dans toute implémentation concrète[Note 2].

Pour les articles homonymes, voir Modèle standard.

Toutefois, de telles preuves sont notoirement difficiles à construire[1],[3],[4] et parfois même impossibles[5],[6],[7]. Ainsi de nombreuses constructions sont seulement analysées en dehors de ce modèle[Note 3],[8].

Définition

Une construction cryptographique est considérée sûre dans modèle standard lorsque l'adversaire n'est limité que par ses capacités calculatoires[1],[2] ; autrement dit les seules hypothèses faites portent sur la complexité algorithmique de certains problèmes. Cela fait contraste avec les preuves reposant sur une simplification des primitives (par exemple le modèle du groupe générique, faisant abstraction d'un groupe particulier) ou sur des hypothèses de confiance (par exemple le modèle de la chaîne de référence, qui fait abstraction d'une étape préliminaire de négociation entre participants).

Pour certains auteurs[2],[9], les hypothèses calculatoires elles-mêmes doivent être « standard » pour que la preuve soit considérée valide dans ce modèle. Concrètement, cette contrainte additionnelle élimine les variantes paramétrisées (dites « q-type »), les variantes fortes (comme le problème RSA fort), et les variantes ad hoc (telles que les hypothèses de séparation DDH-CDH dans les groupes bilinéaires) [Note 4],[10]. Sans que la liste soit exhaustive, les hypothèses suivantes sont généralement considérées standard[11] : le problème du logarithme discret, le problème de Diffie-Hellman, la factorisation, le problème RSA, le problème de la résiduosité quadratique, et les problèmes équivalents à ceux-ci.

Constructions sûres dans le modèle standard

Peu de constructions connues sont sûres dans le modèle standard. Le premier cryptosystème à clé publique prouvé sûr[Note 5] dans le modèle standard est le cryptosystème de Cramer-Shoup en 1998[12]. Les fonctions de hachage caméléon ont été introduites la même année par Hugo Krawczyk et Tal Rabin[13],[Note 6],[14]. Le premier schéma basé sur l'identité et la première signature prouvée sûre[Note 7] reposant dans le modèle standard sur le problème de Diffie-Hellman sont dus à Brent Waters en 2005[15]. En 2009, Hohenberger et Waters produisent le premier schéma de signature prouvé sûr reposant sur le problème RSA dans le modèle standard[9]. Le premier échange de clé authentifié et le premier mécanisme d'encapsulation de clé prouvés sûrs dans le modèle standard sont dus à Tatsuaki Okamoto en 2007[16], et un protocole en un tour a été proposé en 2015[17].

Notes et références

Notes
  1. Aussi parfois appelé « modèle ordinaire » (plain model) ou « modèle nu » (bare model) dans la littérature anglophone.
  2. Voir par exemple les articles sur le modèle de l'oracle aléatoire ou du groupe générique pour une discussion de ces aspects.
  3. Citant (Barthe et coll. 2014), « Bien qu'il soit largement admis que cette situation est loin d'être idéale, s'appuyer sur des hypothèses non standard est parfois la seule façon connue de construire de nouveaux (ou d'efficaces) schémas cryptographiques, et pour cette raison on ne peut l'ignorer. » (While it is widely acknowledged that this situation is far from ideal, relying on non-standard assumptions is sometimes the only known way to construct some new (or some efficient) cryptographic scheme, and hence it cannot be completely disregarded.)
  4. Pour une liste plus complète d'hypothèses, et certaines des relations qui les lient, voir (Berger et coll. 2013). Voir aussi (Naor 2003).
  5. À savoir, résistant aux attaques adaptatives à chiffrés choisis (INDA-CCA2).
  6. Voir aussi (Andreeva et coll. 2015) pour une discussion sur les problèmes ouverts relatifs aux fonctions de hachage cryptographiques dans le modèle standard.
  7. À savoir, résistante aux contrefaçons existentielles dans une attaque à messages choisis (EF-CMA).

Références
  1. (en) David Naccache, « Standard Model », dans Encyclopedia of Cryptography and Security, Springer US, (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_518, lire en ligne), p. 1253–1253
  2. (en) Shafi Goldwasser et Yael Tauman Kalai, « Cryptographic Assumptions: A Position Paper », dans Theory of Cryptography, Springer Berlin Heidelberg, (ISBN 9783662490952, DOI 10.1007/978-3-662-49096-9_21, lire en ligne), p. 505–522
  3. (en) Alon Rosen, Gil Segev et Ido Shahaf, « Can PPAD Hardness be Based on Standard Cryptographic Assumptions? », dans Theory of Cryptography, Springer International Publishing, (ISBN 9783319705026, DOI 10.1007/978-3-319-70503-3_25, lire en ligne), p. 747–776
  4. (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
  5. (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 )
  6. (en) Oded Goldreich et Yair Oren, « Definitions and properties of zero-knowledge proof systems », Journal of Cryptology, vol. 7, no 1,‎ (ISSN 0933-2790 et 1432-1378, DOI 10.1007/bf00195207, lire en ligne, consulté le )
  7. (en) Ran Canetti et Marc Fischlin, « Universally Composable Commitments », dans Advances in Cryptology — CRYPTO 2001, Springer Berlin Heidelberg, (ISBN 9783540424567, DOI 10.1007/3-540-44647-8_2, lire en ligne), p. 19–40
  8. (en) Gilles Barthe, Edvard Fagerholm, Dario Fiore et John Mitchell, « Automated Analysis of Cryptographic Assumptions in Generic Group Models », dans Advances in Cryptology – CRYPTO 2014, Springer Berlin Heidelberg, (ISBN 9783662443705, DOI 10.1007/978-3-662-44371-2_6, lire en ligne), p. 95–112
  9. (en) Susan Hohenberger et Brent Waters, « Short and Stateless Signatures from the RSA Assumption », dans Advances in Cryptology - CRYPTO 2009, Springer Berlin Heidelberg, (ISBN 9783642033551, DOI 10.1007/978-3-642-03356-8_38, lire en ligne), p. 654–670
  10. (en) Benger et coll., « Final Report on Main Computational Assumptions in Cryptography », D.MAYA.6 - ECRYPT II - ICT-2007-216676, Fré Vercauteren,‎ , p. 65 (lire en ligne)
  11. (en) Moni Naor, « On Cryptographic Assumptions and Challenges », dans Advances in Cryptology - CRYPTO 2003, Springer Berlin Heidelberg, (ISBN 9783540406747, DOI 10.1007/978-3-540-45146-4_6, lire en ligne), p. 96–109
  12. (en) Ronald Cramer et Victor Shoup, « A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack », dans Advances in Cryptology — CRYPTO '98, Springer Berlin Heidelberg, (ISBN 9783540648925, DOI 10.1007/bfb0055717, lire en ligne), p. 13–25
  13. (en) Hugo Krawczyk et Tal Rabin, « Chameleon Hashing and Signatures », sur eprint.iacr.org, (consulté le )
  14. (en) Elena Andreeva, Bart Mennink et Bart Preneel, « Open problems in hash function security », Designs, Codes and Cryptography, vol. 77, nos 2-3,‎ , p. 611–631 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-015-0096-0, lire en ligne, consulté le )
  15. (en) Brent Waters, « Efficient Identity-Based Encryption Without Random Oracles », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783540259107, DOI 10.1007/11426639_7, lire en ligne), p. 114–127
  16. (en) Tatsuaki Okamoto, « Authenticated Key Exchange and Key Encapsulation in the Standard Model », dans Advances in Cryptology – ASIACRYPT 2007, Springer Berlin Heidelberg, (ISBN 9783540768999, DOI 10.1007/978-3-540-76900-2_29, lire en ligne), p. 474–484
  17. (en) Florian Bergsma, Tibor Jager et Jörg Schwenk, « One-Round Key Exchange with Strong Security: An Efficient and Generic Construction in the Standard Model », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783662464465, DOI 10.1007/978-3-662-46447-2_21, lire en ligne), p. 477–494
  • 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.