The Random Oracle Methodology, Revisited

This work takes 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''. It is shown that, in general, no such relation exist. Specifically, 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. This refutes the common belief that a security proof in the Random Oracle Model means that there are no ``structural flaws'' in the scheme, and that there can be no ``generic attacks'' against it.

Comments: Authored by R. Canetti, O. Goldreich and S. Halevi. Appeared in

• Proc. of the 30th STOC, pp. 209-218, 1998.