Cryptography Reference
In-Depth Information
whereas
[
A
(1
n
Pr
[
D
(
U
n
)
=
1]
=
Pr
,
U
n
)
=
next
A
(
U
n
)]
1
2
≤
Pr
[
D
(
X
n
)
=
1]
−
Pr
Thus,
[
D
(
U
n
)
=
1]
≥
1
/
p
(
n
), and we reach a contradiction to
that
{
X
n
}
n
∈N
the
hypothesis
is
pseudorandom.
The
“only-if”
direction
follows.
Proof for the “Opposite” Direction:
The proof for the opposite direction (i.e., un-
predictability implies pseudorandomness) is more complex. In fact, the intuition
in this case is less clear. One motivation is provided by the information-theoretic
analogue: The only sequence of 0-1 random variables that cannot be predicted
(when discarding computational issues) is the one in which the random variables
are independent and uniformly distributed over
{
0
,
1
}
. In the current case, the
computational analogue again holds, but proving it is (again) more complex. The
proof combines the use of the hybrid technique and a
special case
of the very
statement being proved. Loosely speaking, the special case refers to two ensem-
bles
Y
def
={
Y
n
}
n
∈N
and
Y
def
Y
n
}
n
∈N
, where
Y
n
is derived from
Y
n
by omitting the
last bit of
Y
n
. The claim is that if
Y
is pseudorandom and
Y
is unpredictable in
polynomial time, then
Y
is pseudorandom. By this claim, if the
i
-bit-long prefix
of
X
n
is pseudorandom and the (
i
={
1)-bit-long prefix of
X
n
is polynomial-time-
unpredictable, then the latter is also pseudorandom. We next work this intuition
into a rigorous proof.
Suppose, toward the contradiction, that
X
+
X
n
}
n
∈N
is not pseudorandom.
Again, for simplicity (and without loss of generality), we assume that
={
n
.
Thus there exists a probabilistic polynomial-time algorithm
D
that distinguishes
X
from the standard uniform ensemble
{
U
n
}
n
∈N
; that is, for some polynomial
p
and infinitely many
n
's,
|
X
n
|=
1
p
(
n
)
|
Pr
[
D
(
X
n
)
=
1]
−
Pr
[
D
(
U
n
)
=
1]
|≥
(3.9)
Assume, without loss of generality, that for infinitely many
n
's,
1
p
(
n
)
Pr
[
D
(
X
n
)
=
1]
−
Pr
[
D
(
U
n
)
=
1]
≥
(3.10)
Justification for the dropping of absolute value:
Let
S
be the infinite set of
n
's for which Eq. (3.9) holds. Then
S
must contain either an infinite subset of
n
's for
which
1] is positive or an infinite subset for which it is
negative. Without loss of generality, we assume that the former holds. Otherwise, we
modify
D
by flipping its output.
Pr
[
D
(
X
n
)
=
1]
−
Pr
[
D
(
U
n
)
=
For each
n
satisfying Eq. (3.10), we define
n
+
1 hybrids. The
i
th hybrid (
i
=
0
,
1
,...,
n
), denoted
H
n
, consists of the
i
-bit-long prefix of
X
n
followed by the
(
n
−
i
)-bit-long suffix of
U
n
. The foregoing hypothesis implies that there exists
121
