Cryptography Reference
In-Depth Information
G
. . .
f
f
f
f
S
0
S
S
S
p(n)
1
2
b
b
b
b
σ
σ
σ
p(n)
1
2
n
.
Figure 3.4:
Construction 3.4.2, as operating on seed s
0
∈{0, 1}
Proposition 3.4.3:
Let f , b, and G be as in Construction 3.4.2. If b is a hard-core
of f , then G is a pseudorandom generator.
Proof:
Consider the generator
G
obtained by reversing the order of the bits in
the output of
G
. That is, if
G
(
s
)
=
σ
1
σ
2
···
σ
p
(
|
s
|
)
, then
G
(
s
)
=
σ
p
(
|
s
|
)
···
σ
2
σ
1
.
We first observe that the ensemble
{
G
(
U
n
)
}
n
∈N
is pseudorandom if and only if
the ensemble
}
n
∈N
is pseudorandom. Using Theorem 3.3.7, it suffices to
show that the ensemble
{
G
(
U
n
)
}
n
∈N
is unpredictable in polynomial time. This
is shown by generalizing the argument used in the first proof of Theorem 3.4.1.
Toward this goal, it is instructive to notice that
{
G
(
U
n
)
=
b
f
p
(
|
s
|
)
−
1
(
s
)
·
b
f
p
(
|
s
|
)
−
2
(
s
)
···
b
(
s
)
G
(
s
)
where
f
0
(
s
)
=
s
and
f
i
+
1
(
s
)
=
f
i
(
f
(
s
)). That is, the
j
th bit in
G
(
s
), which
equals the
p
(
|
s
|
)
−
j
+
1 bit in
G
(
s
), equals
b
(
f
p
(
|
s
|
)
−
j
(
s
)).
Intuitively, the proof of unpredictability proceeds as follows. Suppose, to-
ward the contradiction, that for some
j
def
=
<
t
p
(
n
), given the
j
-bit-long prefix
of
G
(
U
n
), an algorithm
A
can predict the
j
+
1 bit of
G
(
U
n
). That is, given
b
(
f
t
−
1
(
s
))
b
(
f
t
−
j
(
s
)), algorithm
A
predicts
b
(
f
t
−
(
j
+
1)
(
s
)), where
s
is uni-
formly distributed in
···
{
0
,
1
}
n
. Then for
x
uniformly distributed in
{
0
,
1
}
n
,given
f
(
x
), one can predict
b
(
x
) by invoking
A
on input
b
(
f
j
−
y
=
1
(
y
))
···
b
(
y
)
=
j
(
x
))
b
(
f
=
f
(
x
). In the analysis, we use the hypothesis that
f
induces a permutation over
{
···
b
(
f
(
x
)), which in turn is polynomial-time-computable from
y
n
, and we associate
x
with
f
t
−
(
j
+
1)
(
s
). Details follow.
Suppose, toward the contradiction, that there exists a probabilistic polynomial-
time algorithm
A
and a polynomial
p
such that for infinitely many
n
's,
0
,
1
}
A
1
p
(
n
)
,
G
(
U
n
)
=
next
A
(
G
(
U
n
))
>
1
2
+
1
p
(
n
)
Pr
(3.13)
Then we derive a contradiction by constructing an algorithm
A
that, given
f
(
U
n
),
predicts
b
(
U
n
) with probability that is non-negligibly higher than
1
2
. Algorithm
def
=
p
(
n
):
A
operates as follows, on input
y
∈{
0
,
1
}
n
, where
t
1.
Uniformly select
j
∈{
0
,...,
t
−
1
}
.
j
−
1
(
y
))
2.
Compute
α
←
b
(
f
···
b
(
y
). (Note that
|
α
|=
j
.)
