Cryptography Reference
In-Depth Information
Here the probability is taken over all possible values of
R
n
and all internal coin tosses
of algorithm
G
, whereas
x
is fixed.
E
Proof:
The claim follows by an averaging argument. Namely, write
(
s
(
X
n
))
=
1
2
+
ε
(
n
), and apply Markov's inequality.
In the sequel, we restrict our attention to
x
's in
S
n
. We shall show an efficient
algorithm that on every input
y
, with
y
S
n
, finds
x
with very high
probability. Contradiction to the (strong) one-wayness of
f
will follow by recalling
that
=
f
(
x
) and
x
∈
≥
ε
(
n
2
.
We start with a motivating discussion. The inverting algorithm that uses algorithm
G
as subroutine will be formally described and analyzed later.
Pr
[
U
n
∈
S
n
]
2.5.2.2. A Motivating Discussion
1
2
+
ε
(
n
)
2
1
2
1
Consider a fixed
x
∈
S
n
. By definition,
s
(
x
)
≥
>
+
2
p
(
n
)
. Suppose, for a
3
4
1
moment, that
s
(
x
)
2
p
(
n
)
. Of course there is no reason to believe that such is
the case; we are just doing a mental experiment. Still, in this case (i.e., of
s
(
x
)
>
+
>
3
4
1
poly(
|
x
|
)
), retrieving
x
from
f
(
x
) is quite easy. To retrieve the
i
th bit of
x
, denoted
x
i
, we randomly select
r
∈{
0
,
1
}
+
n
and compute
G
(
f
(
x
)
,
r
) and
G
(
f
(
x
)
,
r
⊕
e
i
), where
e
i
is an
n
-dimensional binary vector with 1 in the
i
th component, and 0 in all the others,
and
v
⊕
u
denotes the addition mod 2 of the binary vectors
v
and
u
. (The process is
actually repeated polynomially many times, using independent random choices of such
r
's, and
x
i
is determined by a majority vote.)
If both
G
(
f
(
x
)
,
r
)
=
b
(
x
,
r
) and
G
(
f
(
x
)
,
r
⊕
e
i
)
=
b
(
x
,
r
⊕
e
i
), then
,
r
⊕
e
i
)
⊕
b
(
x
,
r
⊕
e
i
)
G
(
f
(
x
)
,
r
)
⊕
G
(
f
(
x
)
=
b
(
x
,
r
)
=
b
(
x
,
e
i
)
=
x
i
where the second equality uses
n
n
n
b
(
x
,
r
)
⊕
b
(
x
,
s
)
≡
x
i
r
i
+
x
i
s
i
≡
x
i
(
r
i
+
s
i
)
≡
b
(
x
,
r
⊕
s
)
(mod 2)
i
=
1
i
=
1
i
=
1
The probability that both
G
(
f
(
x
)
,
r
)
=
b
(
x
,
r
) and
G
(
f
(
x
)
,
r
⊕
e
i
)
=
b
(
x
,
r
⊕
e
i
)
(
4
−
1
1
2
1
hold, for a random
r
, is at least 1
poly(
|
x
|
)
. Hence, repeat-
ing the foregoing procedure sufficiently many times and ruling by majority, we re-
trieve
x
i
with very high probability. Similarly, we can retrieve all the bits of
x
and
hence invert
f
on
f
(
x
). However, the entire analysis was conducted under (the un-
justifiable) assumption that
s
(
x
)
−
2
·
poly(
|
x
|
)
)
>
+
3
4
1
>
+
2
p
(
|
x
|
)
, whereas we know only that
s
(
x
)
>
1
2
1
2
p
(
)
.
The problem with the foregoing procedure is that it doubles the original error prob-
ability of algorithm
G
on inputs of the form (
f
(
x
)
+
|
x
|
,
·
). Under the unrealistic assumption
that
G
's average error on such inputs is non-negligibly smaller than
4
, the error-doubling
phenomenon raises no problems. However, in general (and even in the special case
67
