The Random Oracle Model

A popular methodology for designing cryptographic protocols consists of the following two steps. One first designs an ideal system in which all parties (including the adversary) have oracle access to a truly random function, and proves the security of this ideal system. Next, one replaces the random oracle by a ``good cryptographic hashing function'' (such as MD5 or SHA), providing all parties (including the adversary) with the succinct description of this function. Thus, one obtains an implementation of the ideal system in a ``real-world'' where random oracles do not exist. This methodology, explicitly formulated by Bellare and Rogaway, and hereafter referred to as the random oracle methodology, has been used in many works.

The Random Oracle Methodology, Revisited, by Ran Canetti, Oded Goldreich, Shai Halevi, takes 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''. The 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, possible definitions for the notion of a ``good implementation'' of a random oracle are considered and investigated.

Perfectly One-Way Probabilistic Hashing, by Ran Canetti, Daniele Micciancio and Omer Reingold. Given the above, it seems adequate to proceed by identifying useful (special-purpose) properties of a random oracle, which can be also provided by a fully specified function (or function ensemble), and so yield implementations of certain useful ideal systems. First steps in this direction were taken by Canetti and are futher developed in this work, which considers a property called ``perfect one-wayness," providing constructions which possess this property (under some reasonable assumptions).