Cryptography Reference
In-Depth Information
predicts the next bit, denoted next
A
(
G
(
U
n
)), with probability that is non-negligibly
higher than
1
2
. That is, for some positive polynomial
p
and infinitely many
n
's,
1
2
+
1
p
(
n
)
[
A
(1
n
+
1
Pr
,
G
(
U
n
))
=
next
A
(
G
(
U
n
))]
>
(3.11)
We first claim that, without loss of generality, algorithm
A
always tries to guess
the last (i.e.,
n
1) bit of
G
(
U
n
). This is justified by observing that the success
probability for any algorithm in guessing any other bit of
G
(
U
n
) is bounded above
by
+
1
1
2
in guessing any bit (and in
particular the last bit of
G
(
U
n
)) can be easily achieved by a random unbiased
coin toss.
2
. On the other hand, a success probability of
Rigorous justification of the preceding claim:
Given an algorithm
A
as before,
we consider a modified algorithm
A
that operates as follows. On input (1
n
+
1
,α
), where
1
, algorithm
A
emulates the execution of
A
, while always reading the first
n
bits of
α
and never reading the last bit of
α
. In the course of the emulation, exactly
one of the following three cases will arise:
n
+
α
∈{
0
,
1
}
, algorithm
A
outputs a uniformly
1.
In case
A
tries to predict one of the first
n
bits of
α
selected bit.
2.
In case
A
tries to predict the last bit of
, algorithm
A
outputs the prediction
α
obtained from
A
.
3.
In case
A
tries to read all bits of
, algorithm
A
outputs a uniformly selected bit.
(We stress that
A
never reads the last bit of
α
.)
α
2
(and is exactly
1
2
if
A
outputs a bit). The actions taken by
A
in these cases guarantee success probability
of
1
Note that the success probability for
A
in Cases 1 and 3 is at most
1
2
(in guessing the last bit of
α
). Thus, the success probability for
A
is no less than
that for
A
. (In the rest of the argument, we identify
A
with
A
.)
Next, we use algorithm
A
to predict
b
(
U
n
) from
f
(
U
n
). Recall that
G
(
x
)
=
n
.
f
(
x
)
·
b
(
x
),
where
x
∈{
0
,
1
}
Thus,
by
the
foregoing
claim,
on
input
(1
n
+
1
b
(
x
)), algorithm
A
always tries to guess
b
(
x
) after reading
f
(
x
)
(and without ever reading
b
(
x
)). Thus,
A
is actually predicting
b
(
U
n
) from
f
(
U
n
).
Again, a minor modification is required in order to make the last statement rig-
orous: We consider an algorithm
A
that on input
y
=
f
(
x
), where
x
∈{
0
,
1
}
,
f
(
x
)
·
n
,
invokes
A
on input (1
n
+
1
,
y
0) and outputs whatever
A
does. Because
A
never
reads the last bit of its input, its actions are independent of the value of that bit
(i.e.,
A
(1
n
+
1
,
y
0)
≡
A
(1
n
+
1
,
y
1)). Combining this fact with the fact that
A
always
tries to predict the last bit of its input (and thus next
A
(
y
·
σ
)
=
σ
), we get
Pr
[
A
(
f
(
U
n
))
=
b
(
U
n
)]
=
Pr
[
A
(1
n
+
1
,
f
(
U
n
)
·
0)
=
b
(
U
n
)]
[
A
(1
n
+
1
=
Pr
,
f
(
U
n
)
·
b
(
U
n
))
=
b
(
U
n
)]
[
A
(1
n
+
1
=
Pr
,
f
(
U
n
)
·
b
(
U
n
))
=
next
A
(
f
(
U
n
)
·
b
(
U
n
))]
1
p
(
n
)
for infinitely many
n
's, in contradiction to the hypothesis that
b
is a hard-core of
f
. The theorem follows.
1
2
Combining this with Eq. (3.11), we obtain
Pr
[
A
(
f
(
U
n
))
=
b
(
U
n
)]
≥
+
