International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: The Random Oracle Methodology, Revisited

Ran Canetti
Oded Goldreich
Shai Halevi
Search ePrint
Search Google
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 paper 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.
  title={The Random Oracle Methodology, Revisited},
  booktitle={IACR Eprint archive},
  keywords={foundations / correlation intractability, CS proofs, encryption and signature schemes, the random-oracle model},
  note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. 12268 received March 31st, 2003. last revised 3 Aug 2003},
  author={Ran Canetti and Oded Goldreich and Shai Halevi},