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 a 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 [5] and hereafter referred to as the random oracle methodology, has been used in many works (see, for example, [14, 35, 23, 32, 5, 27,6, 33]).

Although the random oracle methodology seems to be useful in practice, it is unclear how to put this methodology on firm grounds. One can indeed make clear statements regarding the security of the ideal system, but it is not clear what happens when one replaces the random oracle by a “fully specified implementation”. What one would have liked is a realizable construct that, when used to replace the random oracle, maintains the security of the ideal scheme. The purpose of this work is to point out fundamental difficulties in proceeding towards this goal.

We demonstrate that the traditional approach of providing a single robust definition that supports a wide range of applications is bound to fail. That is, one cannot expect to see definitions such as of pseudorandom generators or functions [7, 36, 19], and general results of the type saying that these can be used in any application in which parties are restricted merely by computing resources. Specifically, we identify a specific property of the random oracle, that seems to capture one aspect of the random oracle methodology (and in particular seems to underline heuristics such as the Fiat–Shamir transformation of a three-round identification scheme into a signature scheme in the [14]). We show that even a minimalistic formulation of this property, called correlation intractability, cannot be obtained by any “fully specified implementation”.

To demonstrate the implications of the above to the security of cryptographic systems, we show that systems whose security relies on the “correlation intractability” of their oracle may be secure in the Random Oracle Model, and yet be insecure when implemented using any fully specified function (or function ensemble). In particular, we describe schemes for digital signatures and public-key encryption that are secure in the Random Oracle Model, but for which any implementation yields insecure schemes.

Download