Cryptography Reference
InDepth Information
(1) The distribution
X
(in our case
{G
(
U
n
)
}
n∈
N
) is pseudoran
dom (i.e., is computationally indistinguishable from a uni
form distribution (on
U
(
n
)
}
n∈
N
)).
(2) The distribution
X
is unpredictable in polynomialtime; that
is, no feasible algorithm, given a prefix of the sequence, can
guess its next bit with a nonnegligible advantage over
{
1
2
.
Clearly, pseudorandomness implies polynomialtime unpredictabil
ity (i.e., polynomialtime predictability violates pseudorandomness).
The converse is shown using a hybrid argument, which refers to
hybrids consisting of a prefix of
X
followed by truly random bits
(i.e., a su
x of the uniform distribution). Thus, we focus on prov
ing that
G
(
U
n
) is polynomialtime unpredictable, where
G
(
s
)=
b
(
f
(
s
)
−
1
(
s
))
b
(
s
) is the reverse of
G
(
s
).
Suppose towards the contradiction that, for some
j<
de
=
(
n
),
given the
j
bit long prefix of
G
(
U
n
) an algorithm
A
can predict the
j
+1
st
···
b
(
f
(
s
))
·
b
(
f
−j
(
s
)), algo
rithm
A
predicts
b
(
f
−
(
j
+1)
(
s
)), where
s
is uniformly distributed in
{
bit of
G
(
U
n
). That is, given
b
(
f
−
1
(
s
))
···
n
,given
y
=
f
(
x
)
one can predict
b
(
x
)byinvoking
A
on input
b
(
f
j−
1
(
y
))
n
. Then, for
x
uniformly distributed in
0
,
1
}
{
0
,
1
}
b
(
y
)=
b
(
f
j
(
x
))
···b
(
f
(
x
)), which in turn is polynomialtime computable from
y
=
f
(
x
). In the analysis, we use the hypothesis that
f
induces a per
mutation over
···
n
, and associate
x
with
f
−
(
j
+1)
(
s
).
We mention that the existence of a pseudorandom generator with
any stretch function (including the very minimal stretch function
(
n
)=
n
+ 1) implies the existence of pseudorandom generators
for any desired stretch function. The construction is similar to the
one presented in Theorem 3.3. That is, for a pseudorandom gener
ator
G
1
,let
F
(
x
)(resp ,
B
(
x
)) denote the first
{
0
,
1
}

x

bits of
G
1
(
x
)
+1
st
x
bit of
G
1
(
x
)), and consider
G
(
s
)=
B
(
s
)
·
(resp., the
B
(
F
(
s
)
−
1
(
s
)), where
is the desired stretch. Although
F
is
not necessarily 11, it can be shown that
G
is a pseudorandom generator
(65, Sec. 3.3.2).
We conclude this section by mentioning that pseudorandom gen
erators can be constructed from
any
oneway function (rather than
merely from oneway permutations, as above). On the other hand, the
B
(
F
(
s
))
···