Cryptography Reference
In-Depth Information
where
X
i
+
1
def
X
i
+
1
. Using the fact that
H
n
is distributed identically to the
distribution obtained by taking
H
i
+
1
n
=
1
−
=
X
1
···
X
i
X
i
+
1
R
i
+
2
···
R
n
with probabi-
def
=
X
1
···
X
i
X
i
+
1
R
i
+
2
1
···
R
n
lity
2
, and
Z
otherwise, we obtain
D
H
i
+
n
=
1
+
Pr
D
H
n
=
1
=
Pr
[
D
(
Z
)
=
1]
Pr
2
Pr
Pr
[
D
(
H
n
)
=
1]
−
Pr
[
D
(
H
i
+
1
n
which implies
[
D
(
Z
)
=
1]
=
2
)
=
1]. Thus, using
Claim 3.3.7.1 in the last step, we get
n
−
1
1
2
+
1
2
n
·
D
H
i
+
n
=
1
−
Pr
1]
s
A
(
n
)
=
Pr
[
D
(
Z
)
=
i
=
0
n
−
1
1
2
+
1
2
n
·
D
H
i
+
n
=
1
Pr
=
i
=
0
−
2
D
H
n
=
1
−
Pr
D
H
i
+
n
=
1
Pr
n
−
1
1
2
+
1
n
·
D
H
i
+
n
=
1
−
Pr
D
H
n
=
1
Pr
=
i
=
0
1
2
+
1
p
(
n
)
·
n
≥
and the claim follows.
Because
A
is a probabilistic polynomial-time algorithm, Claim 3.3.7.2 contradicts
the hypothesis that
X
n
}
n
∈N
is polynomial-time-unpredictable, and so the opposite
direction of the theorem also follows.
{
Comment.
Unfolding the argument for the “opposite direction,” we note that all the
hybrids considered in it are in fact polynomial-time-indistinguishable, and hence they
are all pseudorandom. The argument actually shows that if the
i
-bit prefix of
H
i
+
1
n
is
pseudorandom and the (
i
+
1)-bit prefix of
H
i
+
1
is unpredictable (which is the same as
n
saying that
H
i
+
1
n
1)-bit prefix of
H
i
+
n
is pseudorandom.
This coincides with the motivating discussion presented at the beginning of the proof
for the “opposite direction.”
is unpredictable), then the (
i
+
3.3.6. Pseudorandom Generators Imply One-Way Functions
Up to this point we have avoided the question of whether or not pseudorandom genera-
tors exist at all. Before saying anything positive, we remark that a necessary condition
to the existence of pseudorandom generators is the existence of one-way function.
Jumping ahead, we mention that this necessary condition is also sufficient: Hence,
pseudorandom generators exist if and only if one-way functions exist. At this point we
shall prove only that the existence of pseudorandom generators implies the existence
of one-way function. Namely:
