Cryptography Reference
In-Depth Information
2.
For the second part, combining the definition of
H
k
+
1
n
and Eq. (3.7), we have
·
pref
p
(
n
)
−
(
k
+
1)
G
U
(2
n
H
k
+
1
n
U
(1)
k
=
+
1
·
pref
p
(
n
)
−
k
−
1
G
suff
n
U
(2
)
n
+
1
U
(1
)
k
U
(1
)
1
≡
·
pref
1
U
(2
)
n
+
1
·
pref
p
(
n
)
−
k
−
1
G
suff
n
U
(2
)
n
+
1
U
(1
)
k
≡
·
f
p
(
n
)
−
k
U
(2
)
1
U
(1
)
k
=
·
n
+
Thus, both parts are established.
Hence, distinguishing
G
1
(
U
n
) from
U
n
+
1
is reduced to distinguishing the neigh-
boring hybrids (i.e.,
H
n
and
H
k
+
n
) by applying
f
p
(
n
)
−
k
to the input, padding the
outcome (in the front) by a uniformly chosen string of length
k
, and applying the
hybrid-distinguisher to the resulting string. Further details follow.
We assume, contrary to the theorem, that
G
is not a pseudorandom generator.
Suppose that
D
is a probabilistic polynomial-time algorithm such that for some
polynomial
q
(
·
) and for infinitely many
n
's, it holds that
Pr
1
>
D
U
p
(
n
)
=
1
q
(
n
)
(
n
)
def
=
[
D
(
G
(
U
n
)
=
1]
−
Pr
We derive a contradiction by constructing a probabilistic polynomial-time algo-
rithm
D
that distinguishes
G
1
(
U
n
) from
U
n
+
1
.
Algorithm
D
uses algorithm
D
as a subroutine. On input
α
∈{
0
,
1
}
n
+
1
,
algorithm
D
operates as follows. First,
D
selects an integer
k
uniformly in
the set
{
0
,
1
,...,
p
(
n
)
−
1
}
, next it selects
β
uniformly in
{
0
,
1
}
k
, and finally it
β
·
f
p
(
n
)
−
k
(
α
halts with output
D
(
)), where
f
p
(
n
)
−
k
is as defined in Eq. (3.8).
Clearly,
D
can be implemented in probabilistic polynomial time (in particular,
f
p
(
n
)
−
k
is implemented by combining the algorithm for computing
G
with trivial
string operations). It is left to analyze the performance of
D
on each of the
distributions
G
1
(
U
n
) and
U
n
+
1
.
Claim 3.3.3.2:
p
(
n
)
−
1
1
p
(
n
)
D
H
n
=
1
[
D
(
G
1
(
U
n
))
=
1]
=
Pr
0
Pr
k
=
and
p
(
n
)
−
1
k
=
0
Pr
1
p
(
n
)
D
H
k
+
n
=
1
Pr
[
D
(
U
n
+
1
)
=
1]
=
Proof:
By construction of
D
, we get, for every
α
∈{
0
,
1
}
n
+
1
,
p
(
n
)
−
1
k
=
0
Pr
1
p
(
n
)
D
U
k
·
f
p
(
n
)
−
k
(
α
)
=
1
Pr
[
D
(
α
)
=
1]
=
Using Claim 3.3.3.1, our claim follows.
117
