Modèle de l'oracle aléatoire

En cryptologie, le modèle de l'oracle aléatoire[Note 1] est un cadre théorique idéalisé dans lequel on peut prouver la sécurité de certains algorithmes cryptographiques, en particulier les signatures numériques. Il postule l'existence d'un oracle, c'est-à-dire d'une boîte noire, qu'un adversaire peut interroger et qui fournit une réponse « aléatoire », dans un sens précisé plus bas. Ce modèle essaie de capturer le comportement idéal d'une fonction de hachage cryptographique.

Le modèle de l'oracle aléatoire a été introduit en 1993 par les cryptologues Mihir Bellare (en) et Phillip Rogaway (en)[1].

Un des intérêts du modèle de l'oracle aléatoire est qu'il permet de construire des preuves de sécurité pour les algorithmes utilisant des fonctions de hachage, sans avoir besoin de rentrer dans les détails d'implémentation de ces dernières. Toutefois, on sait qu'il existe des algorithmes prouvés sûrs dans le modèle de l'oracle aléatoire, qui sont complètement cassés si on remplace l'oracle par n'importe quelle fonction de hachage réelle[2], ce qui a initialement causé des doutes quant à la pertinence des preuves dans ce modèle[3],[4],[5],[6],[7],[8]. Pire, il n'est possible de prouver la sécurité de certains algorithmes, tel que FDH, que dans le modèle de l'oracle aléatoire[9].

Si les preuves dans le modèle standard restent préférables, les réticences face au modèle de l'oracle aléatoire sont aujourd'hui modérées[3],[10]. Qui plus est, des modèles a priori différents tels que le modèle du chiffre idéal se sont en fait avérés équivalents au modèle de l'oracle aléatoire[11]. Pour ces raisons une preuve dans le modèle de l'oracle aléatoire a surtout une valeur heuristique[3],[Note 2].

Exemples importants

Définition

Dans le modèle de l'oracle aléatoire, les participants ont accès à un oracle qui répond à un nombre polynomial de requêtes de la manière suivante :

  • Pour une requête jamais formulée auparavant, l'oracle répond une chaîne de bits choisie uniformément au hasard.
  • Pour une requête déjà reçue, l'oracle renvoie .

Comme souvent en informatique théorique, la notion de choix aléatoire peut se formaliser au moyen d'une « bande aléatoire[Note 3] » . La capacité pour le cryptologue de rembobiner cette bande est au cœur de nombreuses preuves de sécurité dans ce modèle, au moyen du forking lemma[12].

Dans la mesure où est choisi de manière qui ne peut être distinguée d'un véritable choix uniforme, il est possible de le générer d'une manière inconnue de l'adversaire. Ce modèle, dit « de l'oracle aléatoire programmable » permet de contraindre l'adversaire dans une preuve par réduction à casser une hypothèse calculatoire.

Voir aussi

Notes et références

Notes
  1. Souvent abrégé ROM pour l'anglais random oracle model.
  2. (Koblitz et Menezes 2005) notent toutefois qu'aucun système « réel » prouvé sûr dans le modèle de l'oracle aléatoire n'a été attaqué avec succès ; que les limitations mentionnées s'appliquent à des exemples artificiels et que l'absence d'exemples convaincants est en soi un argument en faveur du modèle.
  3. Au sens d'une bande d'une machine de Turing, utilisée par l'algorithme comme source d'entropie.

Références
  1. (en) Mihir Bellare et Phillip Rogaway, « Random oracles are practical: a paradigm for designing efficient protocols », CCS '93 Proceedings of the 1st ACM conference on Computer and communications security, ACM,‎ , p. 62–73 (ISBN 0897916298, DOI 10.1145/168588.168596, lire en ligne, consulté le )
  2. (en) Ran Canetti, Oded Goldreich et Shai Halevi, « The random oracle methodology, revisited », Journal of the ACM (JACM), vol. 51, no 4,‎ , p. 557–594 (ISSN 0004-5411, DOI 10.1145/1008731.1008734, lire en ligne, consulté le )
  3. (en) Neal Koblitz et Alfred J. Menezes, « Another Look at "Provable Security" », Journal of Cryptology, vol. 20, no 1,‎ , p. 3–37 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-005-0432-z, lire en ligne, consulté le )
  4. (en) Gaëtan Leurent et Phong Q. Nguyen, « How Risky Is the Random-Oracle Model? », dans Advances in Cryptology - CRYPTO 2009, Springer Berlin Heidelberg, (ISBN 9783642033551, DOI 10.1007/978-3-642-03356-8_26, lire en ligne), p. 445–464
  5. (en) Mihir Bellare, Alexandra Boldyreva et Adriana Palacio, « An Uninstantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem », dans Advances in Cryptology - EUROCRYPT 2004, Springer Berlin Heidelberg, (ISBN 9783540219354, DOI 10.1007/978-3-540-24676-3_11, lire en ligne), p. 171–188
  6. (en) S. Goldwasser et Y.T. Kalai, « On the (In)security of the Fiat-Shamir paradigm », 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., IEEE Computer. Soc,‎ (ISBN 0769520405, DOI 10.1109/sfcs.2003.1238185, lire en ligne, consulté le )
  7. (en) Matthew D. Green, Jonathan Katz, Alex J. Malozemoff et Hong-Sheng Zhou, « A Unified Approach to Idealized Model Separations via Indistinguishability Obfuscation », dans Lecture Notes in Computer Science, Springer International Publishing, (ISBN 9783319446172, DOI 10.1007/978-3-319-44618-9_31, lire en ligne), p. 587–603
  8. (en) Oded Goldreich, « On Post-Modern Cryptography », IACR ePrint Archive, no 461,‎ (lire en ligne, consulté le )
  9. (en) Yevgeniy Dodis, Roberto Oliveira et Krzysztof Pietrzak, « On the Generic Insecurity of the Full Domain Hash », dans Advances in Cryptology – CRYPTO 2005, Springer Berlin Heidelberg, (ISBN 9783540281146, DOI 10.1007/11535218_27, lire en ligne), p. 449–466
  10. (en) Neal Koblitz et Alfred Menezes, « The Random Oracle Model: A Twenty-Year Retrospective », IACR ePrint Archive, no 140,‎ (lire en ligne, consulté le )
  11. (en) Jean-Sébastien Coron, Jacques Patarin et Yannick Seurin, « The Random Oracle Model and the Ideal Cipher Model Are Equivalent », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783540851738, DOI 10.1007/978-3-540-85174-5_1, lire en ligne), p. 1–20
  12. (en) David Pointcheval et Jacques Stern, « Security Proofs for Signature Schemes », dans Advances in Cryptology — EUROCRYPT ’96, Springer Berlin Heidelberg, (ISBN 9783540611868, DOI 10.1007/3-540-68339-9_33, lire en ligne), p. 387–398
  13. (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
  14. (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
  15. (en) Mihir Bellare et Phillip Rogaway, « Optimal asymmetric encryption », dans Advances in Cryptology — EUROCRYPT'94, Springer Berlin Heidelberg, (ISBN 9783540601760, DOI 10.1007/bfb0053428, lire en ligne), p. 92–111
  16. (en) Mihir Bellare et Phillip Rogaway, « The Exact Security of Digital Signatures-How to Sign with RSA and Rabin », dans Advances in Cryptology — EUROCRYPT ’96, Springer Berlin Heidelberg, (ISBN 9783540611868, DOI 10.1007/3-540-68339-9_34, lire en ligne), p. 399–416
  17. (en) Dan Boneh et Matt Franklin, « Identity-Based Encryption from the Weil Pairing », dans Advances in Cryptology — CRYPTO 2001, Springer Berlin Heidelberg, (ISBN 9783540424567, DOI 10.1007/3-540-44647-8_13, lire en ligne), p. 213–229
  • 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.