Cryptography Reference
In-Depth Information
H
n
, is a function ensemble consisting of 2
2
i
·n
n
functions
{
0
,
1
}
→
n
, each defined by 2
i
{
0
,
1
}
random
n
-bit strings, denoted
s
=
=
i
,is
G
α
(
s
β
). (Pictorially, the function
h
s
is defined by placing the strings in
s
in the corresponding vertices of level
i
, and labeling vertices of lower
levels using the very rule used in the definition of
f
s
.) The extreme
hybrids correspond to our indistinguishability claim (i.e.,
H
n
≡
s
β
β∈{
0
,
1
}
i
. The value of such function
h
s
at
x
=
αβ
,where
|
β
|
f
U
n
and
H
n
is a truly random function), and neighboring hybrids can be
related to our indistinguishability hypothesis (specifically, to the indis-
tinguishability of
G
(
U
n
)and
U
2
n
under multiple samples).
Useful variants (and generalizations) of the notion of pseudorandom
functions include Boolean pseudorandom functions that are defined for
all strings (i.e.,
f
s
:
}
∗
→{
) and pseudorandom functions
that are defined for other domains and ranges (i.e.,
f
s
:
{
0
,
1
}
{
0
,
1
0
,
1
}
d
(
|s|
)
→
r
(
|s|
)
, for arbitrary polynomially bounded functions
d, r
:
{
0
,
1
}
N
→
N
). Various transformations between these variants are known (cf. (65,
Sec. 3.6.4) and (67, Apdx. C.2)).
Applications and a generic methodology.
Pseudorandom func-
tions are a very useful cryptographic tool: One may first design a
cryptographic scheme assuming that the legitimate users have black-
box access to a random function, and next implement the random func-
tion using a pseudorandom function. The usefulness of this tool stems
from the fact that having (black-box) access to a random function gives
the legitimate parties a potential advantage over the adversary (which
does not have free access to this function).
2
The security of the resulting
implementation (which uses a pseudorandom function) is established
in two steps: First one proves the security of an idealized scheme that
uses a truly random function, and next one argues that the actual
implementation (which uses a pseudorandom function) is secure (as
otherwise one obtains an ecient oracle machine that distinguishes a
pseudorandom function from a truly random one).
2
The aforementioned methodology is sound provided that the adversary does not get the
description of the pseudorandom function (i.e., the seed) in use, but has only (possibly
limited) oracle access to it. This is different from the so-called Random Oracle Methodology
formulated in (22) and criticized in (38).
