The random oracle methodology, revisited

ABSTRACT

We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle by so called "cryptographic hash functions".The main result of this article is a negative one: There exist signature and encryption schemes that are secure in the Random Oracle Model, but for which any implementation of the random oracle results in insecure schemes. In the process of devising the above schemes, we consider possible definitions for the notion of a "good implementation" of a random oracle, pointing out limitations and challenges.

REFERENCES

• 1: B. Barak (Machtey Award Co-winner), How to Go Beyond the Black-Box Simulation Barrier, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.106, October 14-17, 2001
• 2: Boaz Barak, Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.345-355, November 16-19, 2002
• 3: Boaz Barak , Oded Goldreich , Russell Impagliazzo , Steven Rudich , Amit Sahai , Salil P. Vadhan , Ke Yang, On the (Im)possibility of Obfuscating Programs, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.1-18, August 19-23, 2001
• 4: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 5: Bellare, M., and Rogaway, P. 1996. The exact security of digital signatures: How to sign with RSA and Rabin. In Advances in Cryptology---EUROCRYPT'96. Lecture Notes in Computer Science, vol. 1070. Springer-Verlag, New York, 399--416.
• 6: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• 7: Ran Canetti, Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.455-469, August 17-21, 1997
• 8: Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238015]
• 9: Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.209-218, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276741]
• 10: Ran Canetti , Daniele Micciancio , Omer Reingold, Perfectly one-way probabilistic hash functions (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.131-140, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276721]
• 11: Damgård, I. B. 1987. Collision free hash functions and public key signature schemes. In Advances in Cryptology---EUROCRYPT'87. Lecture Notes in Computer Science, vol. 304. Springer-Verlag, New York, 203--216.
• 12: Cynthia Dwork , Moni Naor , Omer Reingold , Larry Stockmeyer, Magic Functions: In Memoriam: Bernard M. Dwork 1923--1998, Journal of the ACM (JACM), v.50 n.6, p.852-921, November 2003 [doi>10.1145/950620.950623]
• 13: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 14: Gennaro, R., Halevi, S., and Rabin, T. 1999. Secure hash-and-sign signatures without the random oracle. In Advances in Cryptology---EUROCRYPT'99. Lecture Notes in Computer Science, vol. 1592. Springer-Verlag, New York, 123--139.
• 15: Goldreich, O. 1993. A uniform complexity treatment of encryption and zero-knowledge. J. Crypt. 6, 1, 21--53.
• 16: Goldreich, O. 1999. Encryption schemes---Fragments of a chapter. Available from http://www.wisdom.weizmann.ac.il/∼oded/foc-vol2.html.
• 17: Goldreich, O. 2002. The GGM construction does NOT yield correlation intractable function ensembles. ECCC TR02-047, http://www.eccc.uni-trier.de/eccc/.
• 18: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 19: Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing, v.25 n.1, p.169-192, Feb. 1996 [doi>10.1137/S0097539791220688]
• 20: Goldwasser, S., and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2 (Apr.), 270--299.
• 21: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 22: L. C. Guillou , J.-J. Quisquater, A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory, Lecture Notes in Computer Science on Advances in Cryptology-EUROCRYPT'88, p.123-128, April 1988, Davos, Switzerland
• 23: Satoshi Hada , Toshiaki Tanaka, A Relationship between One-Wayness and Correlation Intractability, Proceedings of the Second International Workshop on Practice and Theory in Public Key Cryptography, p.82-96, March 01-03, 1999
• 24: R. Impagliazzo , S. Rudich, Limits on the provable consequences of one-way permutations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.44-61, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73012]
• 25: Joe Kilian, A note on efficient zero-knowledge proofs and arguments (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.723-732, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129782]
• 26: Silvio Micali, Computationally Sound Proofs, SIAM Journal on Computing, v.30 n.4, p.1253-1298, 2000 [doi>10.1137/S0097539795284959]
• 27: Naor, M., and Nissim, K. 1999. Computationally sound proofs: Reducing the number of random oracle calls. Manuscript.
• 28: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 29: Jesper Buus Nielsen, Separating Random Oracle Proofs from Complexity Theoretic Proofs: The Non-committing Encryption Case, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.111-126, August 18-22, 2002
• 30: Nissim, K. 1999. Two results regarding correlation intractability. Manuscript.
• 31: Tatsuaki Okamoto, Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.31-53, August 16-20, 1992
• 32: Pointcheval, D., and Stern, J. 1996. Security proofs for signature schemes. In Advances in Cryptology---EUROCRYPT'96. Lecture Notes in Computer Science, vol. 1070. Springer-Verlag, New York, 387--398.
• 33: J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100269]
• 34: Schnorr, C. 1991. Efficient signature generation by smart cards. J. Cryptology 4, 3, 161--174.
• 35: Yao, A. 1982. Theory and applications of trapdoor functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 80--91.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Authentication

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models

General Terms:
Security, Theory

Keywords:
CS-proofs, Correlation intractability, cryptography, diagonalization, the random-oracle model