Cryptography Reference
In-Depth Information
Proof sketch:
The actual proof refers to an arbitrary algorithm
B
that, when given (
f
(
x
)
,r
), tries to guess
b
(
x, r
). Suppose that this
algorithm succeeds with probability
2
+
, where the probability is taken
over the random choices of
x
and
r
(as well as the internal coin tosses
of
B
). By an averaging argument, we first identify a
/
2fractionofthe
possible coin tosses of
B
such that using any of these coin sequences
B
succeeds with probability at least
1
2
+
/
2. Similarly, we can identify a
/
4fractionofthe
x
's such that
B
succeeds (in guessing
b
(
x, r
)) with
probability at least
1
2
+
/
4, where now the probability is taken only
over the
r
's. We will show how to use
B
in order to invert
f
, on input
f
(
x
), provided that
x
is in the good set (which has density
/
4).
As a warm-up, suppose for a moment that, for the aforemen-
tioned
x
's, algorithm
B
succeeds with probability
p>
4
+1
/
poly(
|x|
)
1
(rather than at least
2
+
/
4). In this case, retrieving
x
from
f
(
x
)
is quite easy: To retrieve the
i
th
bit of
x
, denoted
x
i
,wefirstran-
}
|x|
,andobtain
B
(
f
(
x
)
,r
)and
B
(
f
(
x
)
,r
e
i
),
domly select
r
∈{
0
,
1
⊕
where
e
i
=0
i−
1
10
|x|−i
u
denotes the addition mod 2 of the
binary vectors
v
and
u
. Note that if both
B
(
f
(
x
)
,r
)=
b
(
x, r
)and
B
(
f
(
x
)
,r⊕e
i
)=
b
(
x, r⊕e
i
) indeed hold, then
B
(
f
(
x
)
,r
)
⊕B
(
f
(
x
)
,r⊕e
i
)
equals
b
(
x, r
)
and
v
⊕
e
i
)=
b
(
x, e
i
)=
x
i
. The probability that both
B
(
f
(
x
)
,r
)=
b
(
x, r
)and
B
(
f
(
x
)
,r
⊕
b
(
x, r
⊕
e
i
)=
b
(
x, r
e
i
) hold, for a random
⊕
⊕
1
1
r
,isatleast1
−
2
·
(1
− p
)
>
poly(
|x|
)
. Hence, repeating the above
procedure suciently many times (using independent random choices
of such
r
's) and ruling by majority, we retrieve
x
i
with very high prob-
ability. Similarly, we can retrieve all the bits of
x
, and hence invert
f
on
f
(
x
). However, the entire analysis was conducted under (the unjus-
tifiable) assumption that
p>
4
+
2
+
1
poly(
|x|
)
, whereas we only know that
p>
2
+
4
(for
>
1
/
poly(
|x|
)).
The problem with the above procedure is that it doubles the orig-
inal error probability of algorithm
B
on inputs of the form (
f
(
x
)
,
).
Under the unrealistic assumption (made above), that
B
's average error
on such inputs is non-negligibly smaller than
·
1
4
, the “error-doubling”
phenomenon raises no problems. However, in general (and even in the
special case where
B
's error is exactly
4
) the above procedure is unlikely
to invert
f
. Note that the
average
error probability of
B
(for a fixed
