Cryptography Reference
In-Depth Information
only i
<
|
x
|
of the bits of x , and returns a uniformly chosen bit otherwise (i.e., in
case A reads the entire string x ).
The role of the input 1
|
x
|
given with
x
is to allow the algorithm to determine the
length of
x
(and operate in time polynomial in that length) before reading
x
. In case
A
reads all of
x
, it must guess a perfectly random bit and certainly cannot succeed with
probability higher than
1
2
. (Alternatively, one may disallow
A
to read all its input; see
Exercise 20.) The interesting case is, of course, when
A
chooses not to read the entire
input, but rather tries to guess the
i
1 bit of
x
based on the first
i
bits of
x
.An
ensemble is called unpredictable in polynomial time if no probabilistic polynomial-
time algorithm can succeed in the latter task with probability non-negligibly higher
than
+
1
2
.
Intuitively, pseudorandom ensembles are unpredictable in polynomial time (since so
are all uniform ensembles). It turns out that the converse holds as well. Namely, only
pseudorandom ensembles are unpredictable in polynomial time.
Theorem 3.3.7 (Pseudorandomness versus Unpredictability):
An ensemble
{
X
n
}
n
∈N
is pseudorandom if and only if it is unpredictable in polynomial time.
Proof for the “Only-if” Direction:
The proof that pseudorandomness implies
unpredictability indeed follows the intuition mentioned earlier. Because the en-
semble
X
def
={
X
n
}
n
∈N
is pseudorandom, it is polynomial-time-indistinguishable
from some uniform ensemble. Clearly, the uniform ensemble is unpredictable in
polynomial time; in fact, it is unpredictable regardless of the time bounds imposed
on the predicting algorithm. Thus, the ensemble
X
must also be polynomial-
time-unpredictable, or else we could distinguish the ensemble
X
from the uni-
form ensemble in polynomial time (in contradiction to the hypothesis). Details
follow.
For simplicity (and without loss of generality), suppose that the ensemble
X
n
and thus is polynomial-time-indistinguishable
from the standard uniform ensemble
={
X
n
}
n
∈N
satisfies
|
X
n
|=
{
U
n
}
n
∈N
. Suppose, toward the contradiction,
that
X
n
}
n
∈N
is predictable in polynomial time by an algorithm
A
; that is, for some
polynomial
p
and infinitely many
n
's,
{
1
2
+
1
p
(
n
)
Pr
[
A
(1
n
,
X
n
)
=
next
A
(
X
n
)]
≥
Then
A
can be easily transformed into a distinguisher, denoted
D
, operating as
follows. On input
y
, the distinguisher invokes
A
on input (1
|
y
|
,
y
) and records the
number of bits that
A
has actually read, as well as
A
's prediction for the next bit.
In case the prediction is correct,
D
outputs 1, and otherwise it outputs 0. Clearly,
[
A
(1
n
Pr
[
D
(
X
n
)
=
1]
=
Pr
,
X
n
)
=
next
A
(
X
n
)]
1
2
+
1
p
(
n
)
120
≥
