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
Search WWH ::




Custom Search