Cryptography Reference
In-Depth 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 polynomial-time; that
is, no feasible algorithm, given a prefix of the sequence, can
guess its next bit with a non-negligible advantage over
{
1
2
.
Clearly, pseudorandomness implies polynomial-time unpredictabil-
ity (i.e., polynomial-time 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 polynomial-time 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 polynomial-time 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 1-1, 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
one-way function (rather than
merely from one-way permutations, as above). On the other hand, the
B
(
F
(
s
))
···
