Cryptography Reference
In-Depth Information
Theorem 3.6.14:
Let G and the f
s
's be as in Construction 3.6.13, and suppose
that G is a pseudorandom generator. Then
{
f
s
}
s
∈{
0
,
1
}
∗
is an efficiently computable
ensemble of unbounded-input pseudorandom functions.
Proof Sketch:
We follow the proof method of Theorem 3.6.6. That is, we use the
hybrid technique, where the
k
th hybrid will be assigned a function that results from
uniformly selecting labels for the vertices of the highest
k
+
1 levels of the tree,
and computing the labels for lower levels as in Construction 3.6.13. Specifically,
the
k
th hybrid is defined as equal to the function
f
s
1
,...,
s
3
k
:
{
0
,
1
}
∗
→{
0
,
1
}
r
(
n
)
,
2
n
+
r
(
n
)
defined next, where
s
1
,...,
s
3
k
∈{
0
,
1
}
are uniformly and independently
distributed.
f
s
1
,...,
s
3
k
(
σ
1
σ
2
···
σ
d
)
P
2
s
idx(2
k
−
d
·
σ
d
···
σ
1
)
if
d
≤
k
G
2
G
σ
d
···
G
σ
k
+
2
G
σ
k
+
1
s
idx(
σ
k
···
σ
1
)
···
otherwise
def
=
where idx(
α
) is the index of
α
in the standard lexicographic order of ternary
strings of length
|
α
|
, and
P
2
(
β
)isthe
r
(
n
)-bit-long suffix of
β
.
Note that (unlike the proof of Theorem 3.6.6) for every
n
there are infinitely
many hybrids, because here
k
can be any non-negative integer (rather than
k
∈{
0
,
1
,...,
n
}
as in the proof of Theorem 3.6.6). Still, because we consider an
(arbitrary) probabilistic
polynomial-time
distinguisher denoted
M
, there exists a
polynomial
d
such that on input 1
n
the oracle machine
M
makes only queries
of length at most
d
(
n
)
−
1. Thus, giving
M
oracle access to the
d
(
n
) hybrid is
equivalent to giving
M
oracle access to the uniform random variable
H
n
(where
H
n
is as in Definition 3.6.12), because a uniformly chosen label is assigned to
each
i
-level leaf for
i
≤
d
(
n
). On the other hand, the 0 hybrid corresponds to the
random variable
F
n
(where
F
n
is as in Definition 3.6.12), because a uniformly
chosen label is assigned to the root. Thus, if
M
can distinguish
{
F
n
}
from
{
H
n
}
,
then it can distinguish a (random) pair of neighboring hybrids (i.e., the
k
−
1
and
k
hybrids, where
k
is uniformly selected in
). As in the proof of
Theorem 3.6.6, the latter assertion can be shown to violate the pseudorandomness
of
G
. Specifically, we can distinguish multiple independent samples taken from
the distribution
U
2
n
+
r
(
n
)
and multiple independent samples taken from the dis-
tribution
G
(
U
n
): Given a sequence of (2
n
{
1
,...,
d
(
n
)
}
r
(
n
))-bit-long strings, we use these
strings in order to label vertices in the highest
k
+
1 levels of the tree (by breaking
each string into three parts and using those parts as labels for the three children
of some (
i
−
1)-level node, for
i
≤
k
). In case the strings are taken from
U
2
n
+
r
(
n
)
,
we emulate the
k
hybrid, whereas in case the strings are taken from
G
(
U
n
), we
emulate the
k
−
1 hybrid. The theorem follows.
+
Comment.
Unbounded-input (and generalized) pseudorandom functions can be con-
structed directly from (ordinary) pseudorandom functions; see Section 3.8.2.
