The random oracle model is a very convenient setting for designing cryptographic protocols. In this idealized model all parties have access to a common, public random function, called a random oracle. Protocols in this model are often very simple and e cient; also the analysis is often clearer. However, we do not have a general mechanism for transforming protocols that are secure in the random oracle model into protocols that are secure in real life. In fact, we do not even know how to meaningfully specify the properties required from such a mechanism. Instead, it is a common practice to simply replace -often without mathematical justi cationthe random oracle with a`cryptographic hash function' (e.g., MD5 or SHA). Consequently, the resulting protocols have no meaningful proofs of security. We propose a research program aimed at rectifying this situation by means of identifying, and subsequently realizing, the useful properties of random oracles. As a rst step, we introduce a new primitive that realizes a speci c aspect of random oracles. This primitive, called oracle hashing, is a hash function that, like random oracles,`hides all partial information on its input'. A salient property of oracle hashing is that it is probabilistic: di erent applications to the same input result in di erent hash values. Still, we maintain the ability to verify whether a given hash value was generated from a given input. We describe constructions of oracle hashing, as well as applications where oracle hashing successfully replaces random oracles.
First steps in the direction of identifying and studying useful special-purpose properties of the Random Oracle Model have been taken by Canetti REF .
Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information
CRYPTO
Computer Science