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