The Random Oracle Methodology, Revisited

by Ran Canetti, Oded Goldreich, Shai Halevi


Abstract

We take a formal look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes which result from implementing the random oracle by so called ``cryptographic hash functions''. Our main result is a negative one: There exist signature and encryption schemes which 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.

Versions

Also available: a follow-up work (by the same authors, 2003).
Back to Oded Goldreich's homepage or to General list of Oded Goldreich's papers