Cryptography Reference
In-Depth Information
These approaches have been critically analysed by Leurent and Nguyen [
347
]. They
give a number of results that demonstrate that care is needed in assessing the security level
of a hash function with “full domain” output.
3.7 Random oracle model
The random oracle model is a tool for the security analysis of cryptographic systems. It is
a computational model that includes the
standard model
(i.e., the computational model
mentioned in Section
2.1
) together with an oracle that computes a “random” function from
the set
}
∞
(i.e., bitstrings of
countably infinite length). Since the number of such functions is uncountable, care must be
taken when defining the word “random”. In any given application, one has a fixed bit-length
l
in mind for the output, and one also can bound the length of the inputs. Hence, one is
considering functions
H
:
{
}
∗
(i.e., binary strings of arbitrary finite length) to
{
0
,
1
0
,
1
l
and, since there are
l
2
n
such functions, we can
define “random” to mean uniformly chosen from the set of all possible functions. We stress
that a random oracle is a function: if it is queried twice on the same input then the output
is the same.
A
cryptosystem in the random oracle model
is a cryptosystem where one or more hash
functions are replaced by oracle queries to the random function. A cryptosystem is
secure
in the random oracle model
if the cryptosystem in the random oracle model is secure.
This does not imply that the cryptosystem in the standard model is secure, since there may
be an attack that exploits some feature of the hash function. Indeed, there are “artificial”
cryptosystems that are proven secure in the random oracle model, but that are insecure for
any instantiation of the hash function (see Canetti, Goldreich and Halevi [
108
]).
The random oracle model enables security proofs in several ways. We list three of these
ways in increasing order of power.
n
{
0
,
1
}
→{
0
,
1
}
1. It ensures that the output of
H
is truly random (rather than merely pseudorandom).
2. It allows the security proof to “look inside” the working of the adversary by learning
the values that are inputs to the hash function.
3. It allows the security proof to “programme” the hash function so that it outputs a specific
value at a crucial stage in the security game.
A classic example of a proof in the random oracle model is Theorem
20.4.11
. An extensive
discussion of the random oracle model is given in Section 13.1 of Katz and Lindell [
300
].
Since a general function from
l
cannot be represented more compactly
than by a table of values, a random oracle requires
l
2
n
bits to describe. It follows that a ran-
dom oracle cannot be implemented in polynomial space. However, the crucial observation
that is used in security proofs is that a random oracle can be simulated in polynomial-time
and space (assuming only polynomially many queries to the oracle are made) by creating,
on-the-fly, a table giving the pairs (
x,y
) such that
H
(
x
)
n
to
{
0
,
1
}
{
0
,
1
}
=
y
.
