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. Barak, B. 2001. How to go beyond the black-box simulation barrier. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 106--115.]]
2. Barak, B. 2002. Constant-round coin-tossing with a man in the middle or realizing the shared random string model. In Proceedings of the 43rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 345--355.]]
3. Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., and Yang, K. 2001. On the (im)possibility of software obfuscation. In Advances in Cryptology---CRYPTO '01. Lecture Notes in Computer Science, vol. 2139. Springer-Verlag, New York, 1--18.]]
4. Bellare, M., and Rogaway, P. 1993. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st Conference on Computer and Communications Security. ACM, New York, 62--73.]]
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. Blum, M., and Micali, S. 1984. How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13, 850--864.]]
7. Canetti, R. 1997. Towards realizing random oracles: Hash functions that hide all partial information. In Advances in Cryptology---CRYPTO'97. Lecture Notes in Computer Science, vol. 1294. Springer-Verlag, New York, 455--469.]]
8. Canetti, R., Feige, U., Goldreich, O., and Naor, M. 1996. Adaptively secure computation. In Proceedings of the 28th Annual Symposium on Theory of Computing. ACM, New York, (Longer version in MIT-LCS-TR #682, 1996).]]
9. Canetti, R., Goldreich, O., and Halevi, S. 1998a. The random oracle methodology, revisited (preliminary version). In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing. ACM, New York, 209--218. (TR version(s) available on-line from http://eprint.iacr.org/1998/011 and http://xxx.lanl.gov/abs/cs.CR/0010019.)]]
10. Canetti, R., Micciancio, D., and Reingold, O. 1998b. Perfectly one-way probabilistic hashing. In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing. ACM, New York, 131--140.]]
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. Dwork, C., Naor, M., Reingold, O., and Stockmeyer, L. 2003. Magic functions. J. ACM 50, 6 (Nov.), 852--921.]]
13. Fiat, A., and Shamir, A. 1986. How to prove yourself. Practical solutions to identification and signature problems. In Advances in Cryptology---CRYPTO'86. Lecture Notes in Computer Science, vol. 263. Springer-Verlag, New York, 186--189.]]
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. Goldreich, O., Goldwasser, S., and Micali, S. 1986. How to construct random functions. J. ACM 33, 4, 210--217.]]
19. Goldreich, O., and Krawczyk, H. 1996. On the composition of zero-knowledge proof systems. SIAM J. Comput. 25, 1, 169--192.]]
20. Goldwasser, S., and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2 (Apr.), 270--299.]]
21. Goldwasser, S., Micali, S., and Rivest, R. 1988. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17, 2 (Apr.), 281--308.]]
22. Guillou, L., and Quisquater, J. 1988. A practical zero-knowledge protocol fitted to security microprocessors minimizing both transmission and memory. In Advances in Cryptology---EUROCRYPT'88. Lecture Notes in Computer Science, vol. 330. Springer-Verlag, New York, 123--128.]]
23. Hada, S., and Tanaka, T. 1999. A relationship between one-wayness and correlation intractability. In Proceedings of the 2nd International Workshop on Practice and Theory in Public Key Cryptography (PKC'99). Lecture Notes in Computer Science, vol. 1560. Springer-Verlag, New York, 82--96.]]
24. Impagliazzo, R., and Rudich, S. 1989. Limits on the provable consequences of one-way permutations. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing. ACM, New York, 44--61.]]
25. Kilian, J. 1992. A note on efficient zero-knowledge proofs and arguments. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 723--732.]]
26. Micali, S. 2000. Computationally sound proofs. SIAM J. Comput. 30, 4, 1253--1298. (Preliminary version in 35th FOCS, 1994.)]]
27. Naor, M., and Nissim, K. 1999. Computationally sound proofs: Reducing the number of random oracle calls. Manuscript.]]
28. Naor, M., and Yung, M. 1989. Universal one-way hash functions and their cryptographic applications. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing. ACM, New York, 33--43.]]
29. Nielsen, J. 2002. Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case. In Advances in Cryptology---CRYPTO'02. Lecture Notes in Computer Science, vol. 2442. Springer-Verlag, New York, 111--126.]]
30. Nissim, K. 1999. Two results regarding correlation intractability. Manuscript.]]
31. Okamoto, T. 1992. Provably secure and practical identification scheme and corresponding signature scheme. In Advances in Cryptology---CRYPTO'92. Lecture Notes in Computer Science, vol. 740. Springer-Verlag, New York, 31--53.]]
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. Rompel, J. 1990. One-way functions are necessary and sufficient for secure signatures. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing. ACM, New York, 387--394.]]
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

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Public key encryption

  • Security services

    • Authentication

  • Systems security

    • Operating systems security

• Theory of computation

  • Models of computation