Cryptography Reference
In-Depth Information
Theorem 3.3.3:
Let G
1
,p
(
·
)
, and G be as in Construction 3.3.2 such that
p
(
n
)
>
n. If G
1
is a pseudorandom generator, then so is G.
Intuitively, the pseudorandomness of
G
follows from that of
G
1
by replacing each
application of
G
1
by a random process that on input a uniformly distributed
n
-bit-long
string will output a uniformly distributed (
n
+
1)-bit-long string. Loosely speaking,
the indistinguishability of a single application of the random process from a single
application of
G
1
implies that polynomially many applications of the random process
are indistinguishable from polynomially many applications of
G
1
. The actual proof
uses the hybrid technique.
Proof:
Suppose, to the contrary, that
G
is not a pseudorandom generator. It
follows that the ensembles
U
p
(
n
)
}
n
∈N
are not polynomial-time-
indistinguishable. We shall show that it follows that the ensembles
{
G
(
U
n
)
}
n
∈N
and
{
{
G
1
(
U
n
)
}
n
∈N
and
U
n
+
1
}
n
∈N
are not polynomial-time-indistinguishable, in contradiction to the
hypothesis that
G
1
is a pseudorandom generator with expansion factor
l
1
(
n
)
{
=
n
+
1. The implication is proved using the hybrid technique.
For every
k
, with 0
p
(
n
), we define a hybrid
H
n
to be the concatenation
of a uniformly chosen
k
-bit-long string and the (
p
(
n
)
≤
k
≤
−
k
)-bit-long prefix of
G
(
U
n
). Denoting by
pref
j
(
α
) the
j
-bit-long prefix of the strings
α
, where
j
≤
|
α
|
, and by
x
·
y
the concatenation of the strings
x
and
y
,wehave
·
pref
p
(
n
)
−
k
G
U
(2
n
def
H
n
=
U
(1)
k
(3.6)
where
U
(1)
k
and
U
(2)
n
are independent random variables (the first uniformly dis-
n
).
A different way of viewing the hybrid
H
n
is depicted in Figure 3.3: Start-
ing with Construction 3.3.2, we pick
s
k
uniformly in
k
, and the second uniformly distributed over
tributed over
{
0
,
1
}
{
0
,
1
}
n
{
0
,
1
}
and
σ
1
···
σ
k
uni-
k
, and for
i
formly in
{
0
,
1
}
=
k
+
1
,...,
p
(
n
) we obtain
σ
i
s
i
=
G
1
(
s
i
−
1
)asinthe
construction.
At this point it is clear that
H
n
equals
G
(
U
n
), whereas
H
p
(
n
n
equals
U
p
(
n
)
.It
follows that if an algorithm
D
can distinguish the extreme hybrids, then
D
can
also distinguish two neighboring hybrids (since the total number of hybrids is
polynomial in
n
, and a non-negligible gap between the extreme hybrids translates
into a non-negligible gap between some neighboring hybrids). The punch line
Figure 3.3:
Hybrid H
n
as a modification of Construction 3.3.2
115