Cryptography Reference
In-Depth Information
provides some useful evidence for the security of a cryptographic system. In fact,
Bellare and Rogaway claimed that the random oracle model can serve as the basis for
efficient cryptographic systems with security properties that can at least be analyzed
to some extent. Because people do not often want to pay more than a negligible price
for security, such an argument for practical systems seems to be more useful than
formal security proofs for inefficient systems.
There are basically two problems when it comes to an implementation of an
ideal system (in step three of the random oracle methodology).
•
First, it is impossible to implement a random function by a (single) cryp-
tographic hash function. In a random function
f
, the preimages and images
are not related to each other, meaning that
x
does not reveal any information
about
f
(
x
) and
f
(
x
) does not reveal any information about
x
. If the random
function were implemented by a (single) cryptographic hash function
h
,then
the preimage
x
would leak a lot of information about the image
h
(
x
). In fact,
h
(
x
) would be completely determined by
x
. This problem can easily be solved
by using a (large) family of cryptographic hash functions and choosing one at
random [5].
•
Second, it was shown that random oracles cannot be implemented crypto-
graphically. More specifically, it was shown in [6] that there exists a(n artifi-
cially designed) DSS that is secure in the random oracle model but that gets
insecure when the random oracle is implemented by a family of cryptographic
hash functions.
The second problem is particularly worrisome, and since the publication of [6]
many researchers have started to think controversially about the usefulness of the
random oracle methodology in general, and the random oracle model in particular.
Following a line of argumentation that is due to Doug Stinson,
2
the
correct way to interpret a proof of security for a protocol
P
in the
random oracle model is to view it as a proof of security against certain
types of attacks on the protocol
P
. More precisely, the proof shows that
the protocol
P
is secure against what might be termed “hash-generic”
attacks. This means that any attack which treats the hash function as a
random function will not be successful (regardless of whether the hash
function is actually a random function). In other words, it is better to
think of a proof in the random oracle model as a proof in which we make
an assumption about the attacking algorithm rather than an assumption
about the hash function.
2
http://www.cacr.math.uwaterloo.ca/
∼
dstinson/CO 685/randomoracle.html
