Cryptography Reference
In-Depth Information
Worried that proofs under ROM would become standard issue in the
cryptographic toolbox, three prominent theoreticians vehemently dis-
agreed: “Although the random oracle methodology seems to be useful in
practice, it is unclear how to put this methodology on firm grounds.”
21
In
interviews with me, cryptographers voiced various degrees of discomfort
with the model. Birgit Pfitzmann, for example, was concerned that more
work was needed before the epistemological status of proofs under ROM
could be ascertained: “The random oracle model is not an assumption, it
is an abstraction. An assumption, like 'factoring is hard' can be proven true
or false, eventually. But to say that a hash function is as good as a random
oracle is not an assumption
—
it is a simple abstraction, which cannot be
proved or disproved. And because, at the moment, there is no formaliza-
tion of that abstraction, all we can do is hope that it does not abstract from
anything important. But we don't know yet.”
Pointcheval and Stern have sought to resolve the tension between the
two camps by suggesting the model does not indeed provide proofs, but
rather,
arguments.
22
Although they do not formally clarify the relationship
of such arguments to provable security, they suggest these provide “quite
strong indication that the overall design . . . is presumably correct.” Thus,
cryptographers should accept proofs under ROM as useful adjuncts to
either the heuristic measure provided by cryptanalysis or the provable
security provided by complexity theory. However well-intentioned an
interpretation, Rogaway disagreed with its implications: “To some people,
proofs in the Random Oracle model are effectively not proofs. One well-
known researcher calls them
heuristic arguments.
That isn't right. A proof
in the Random Oracle model is still a proof, it's just a proof in a model of
computation that some people don't find worthwhile.”
23
Goldreich dis-
agreed in no uncertain terms: “The ROM has caused more harm than good,
because many people confuse it for the 'real thing' (while it is merely an
extremely idealized sanity check). . . . Given the sour state of affairs, it
seems good to us to abolish the ROM. At the very minimum, one should
issue a fierce warning that
security in the ROM does not provide any indication
towards security in the standard model
.”
24
Regardless of its epistemological validity, the best argument for using
the ROM might just be that it brings under the framework of provable
security objects that would otherwise remain outside of it, namely signa-
tures: “All things being equal, a proof of security in the random oracle
model is not as good as a proof of security in the 'real world,' but is much
