Cryptography Reference
In-Depth Information
f
s
(
x
) is the string residing in the leaf reachable from the root by a path corresponding
to the string
x
. The random variable
F
n
is assigned labeled trees corresponding to all
possible 2
n
labelings of the root, with uniform probability distribution.
A function operating on
n
-bit strings in the ensemble just constructed can be specified
by
n
bits. Hence, selecting, exchanging, and storing such a function can be implemented
at the cost of selecting, exchanging, and storing a single
n
-bit string.
Theorem 3.6.6:
Let G and F be as in Construction 3.6.5, and suppose that G
is a pseudorandom generator. Then F is an efficiently computable ensemble of
pseudorandom functions.
Combining Theorems 3.5.12 and 3.6.6, we immediately get the following:
Corollary 3.6.7:
If there exist one-way functions, then pseudorandom functions
exist as well.
Also, combining Theorem 3.6.6 with the observation that for
log
2
n
, any pseu-
dorandom function (as in Definition 3.6.4) gives rise to a pseudorandom generator (see
Exercise 28), we obtain the following:
(
n
)
>
Corollary 3.6.8:
Pseudorandom functions ( for super-logarithmic
) exist if and
only if pseudorandom generators exist.
Proof of Theorem 3.6.6:
Clearly, the ensemble
F
is efficiently computable. To
prove that
F
is pseudorandom, we use the hybrid technique. The
k
th hybrid will
be assigned a function that results from uniformly selecting labels for the vertices
of the
k
th (highest) level of the tree and computing the labels for lower levels
as in Construction 3.6.5. The 0 hybrid will correspond to the random variable
F
n
(since a uniformly chosen label is assigned to the root), whereas the
n
hybrid
will correspond to the uniform random variable
H
n
(since a uniformly chosen
label is assigned to each leaf). It will be shown that an efficient oracle machine
distinguishing neighboring hybrids can be transformed into an algorithm that
distinguishes polynomially many samples of
G
(
U
n
) from polynomially many
samples of
U
2
n
. Using Theorem 3.2.6, we derive a contradiction to the hypothesis
(that
G
is a pseudorandom generator). Details follows.
For every
k
, with 0
≤
k
≤
n
, we define a hybrid distribution
H
n
, assigned
as values functions
f
:
{
0
,
1
}
n
→{
0
,
1
}
n
, as follows. For every
s
1
,
s
2
,...,
s
2
k
∈
{
0
,
1
}
n
, we define a function
f
s
1
,...,
s
2
k
:
{
0
,
1
}
n
→{
0
,
1
}
n
such that
G
σ
n
G
σ
k
+
2
G
σ
k
+
1
s
idx(
σ
k
···
σ
1
)
σ
1
σ
2
···
σ
n
)
def
f
s
1
,...,
s
2
k
(
=
···
···
where idx(
α
) is the index of
α
in the standard lexicographic order of binary
strings of length
. Namely,
f
s
1
,...,
s
2
k
(
x
) is computed by first using the
k
-bit-
long prefix of
x
to determine one of the
s
j
's and then using the (
n
|
α
|
k
)-bit-long
suffix of
x
to determine which of the functions
G
0
and
G
1
to apply at each of the
152
−
