Cryptography Reference
In-Depth Information
a pair of neighboring hybrids that are polynomial-time-distinguishable. Actually,
this holds, on the average, for a “random” pair of neighboring hybrids:
Claim 3.3.7.1:
For each
n
satisfying Eq. (3.10),
n
−
1
1
n
·
Pr
D
H
i
+
n
=
1
−
Pr
D
H
n
=
1
≥
1
p
(
n
)
·
n
i
=
0
Proof:
The proof is immediate by Eq. (3.10) and the definition of the hybrids. In
particular, we use the fact that
H
n
≡
X
n
and
H
n
≡
U
n
.
Claim 3.3.7.1 suggests a natural algorithm for predicting the next bit of
{
X
n
}
n
∈N
.
The algorithm, denoted
A
, selects
i
uniformly in
, reads
i
bits
from
X
n
, and invokes
D
on the
n
-bit string that results by concatenating these
i
bits with
n
{
0
,
1
,...,
n
−
1
}
i
uniformly chosen bits. If
D
responds with 1, then
A
's prediction
is set to the value of the first among these
n
−
i
random bits; otherwise it is set
to the complementary value. The reasoning is as follows. If the first among the
n
−
i
random bits happens to equal the
i
+
1 bit of
X
n
, then
A
is invoked on
input distributed identically to
H
i
+
n
. On the other hand, if the first among the
n
−
i
random bits happens to equal the complementary value (of the
i
+
1 bit of
X
n
), then
A
is invoked on input distributed identically to a distribution
Z
that is
even more clearly distinguishable from
H
i
+
1
n
−
than is
H
n
(i.e.,
H
n
equals
Z
with
2
, and
H
i
+
n
otherwise). Details follow.
We start with a more precise description of algorithm
A
. On input 1
n
1
probability
and
x
=
x
1
···
x
n
, algorithm
A
proceeds as follows:
{
,
,...,
−
}
1.
Select
i
uniformly in
0
1
n
1
.
2.
Select
r
i
+
1
,...,
r
n
independently and uniformly in
{
0
,
1
}
.
3.
If
D
(
x
1
···
x
i
r
i
+
1
···
r
n
)
=
1, then output
r
i
+
1
, and otherwise output 1
−
r
i
+
1
.
Claim 3.3.7.2:
For each
n
satisfying Eq. (3.10),
1
2
+
1
p
(
n
)
·
n
[
A
(1
n
Pr
,
X
n
)
=
next
A
(
X
n
)]
≥
Proof:
Let us denote by
X
j
,...,
R
n
a sequence
of
n
−
i
independent random variables each uniformly distributed over
{
0
,
1
}
.
Using the definition of
A
and the fact that
the
j
th bit of
X
n
, and by
R
i
+
1
Pr
[
X
i
+
1
=
R
i
+
1
]
=
1
2
,wehave
s
A
(
n
)
def
[
A
(1
n
=
Pr
,
X
n
)
=
next
A
(
X
n
)]
n
−
1
1
n
·
Pr
[
D
(
X
1
···
X
i
R
i
+
1
···
R
n
)
=
1&
R
i
+
1
=
X
i
+
1
]
=
(
i
=
0
+
Pr
[
D
(
X
1
···
X
i
R
i
+
1
···
R
n
)
=
0&1
−
R
i
+
1
=
X
i
+
1
])
n
−
1
1
2
n
·
[
D
(
X
1
X
i
X
i
+
1
R
i
+
2
R
n
)
=
(
Pr
···
···
=
1]
i
=
0
X
i
X
i
+
1
R
i
+
2
[
D
(
X
1
R
n
)
+
1
−
Pr
···
···
=
1])
