Cryptography Reference
In-Depth Information
note, “We stress that we don't know of any
attack
on this scheme. But we
prefer, for such important primitives, to have some proof of security rather
than just an absence of known attacks.”
16
The ROM is an attempt to solve this lingering problem. The principle
is simple: if a cryptographic function truly fulfills its properties of collision
resistance, it is not possible to find the message
m
that corresponds to the
output
h(m)
of the function. That is, for all intents and purposes, the
output of a cryptographic hash function appears perfectly random to all
participants in the signature protocol. The ROM provides a methodology
that simply assumes this ideal state of affair to be the case: “Provide all
parties
—
good and bad alike
—
with access to a (public) function
h
; prove
correct a protocol assuming
h
is truly random, i.e. a random oracle; later,
in practice, set
h
to some specific function derived in some way from a
standard cryptographic hash function like SHA-1 or RIPEMD-160.”
17
The ROM is thus a framework in which perfect mathematical idealiza-
tions (random oracles) of a troublesome real world cryptographic object
(hash functions) are assumed to exist for the purpose of proving the overall
correctness of the protocol. “Later, in practice,” after the idealized protocol
has been proven correct, designers should simply replace the idealization
with the real-world object. The issue for the cryptographic research com-
munity has been to ascertain the relationship, if any, between the idealized
protocol proved under the ROM and the one relying on the real-world
function.
18
Given that no real-world deterministic hash function produces truly
random outputs, Bellare and Rogaway have emphasized from the begin-
ning that proofs under the ROM should not enjoy the same status as
“ordinary” proofs: “We stress that the proof is in the random oracle model
and the last step is heuristic in nature. It is a thesis of this paper that sig-
nificant assurance benefits nonetheless remain.”
19
Determining the precise
nature of those benefits has, however, proven highly controversial. At the
very least, Bellare argued, proof under ROM is better than no proof at all:
“In comparison with totally ad hoc design, a proof in the random oracle
model has the benefit of viewing the scheme with regard to its meeting a
strong and formal notion of security, even if this is assuming some under-
lying primitive is very strong. This is better than not formally modeling
the security of the scheme in any way. This explains why the random
oracle model is viewed as a bridge between theory and practice.”
20
