Cryptography Reference
In-Depth Information
For
i
1
to
t
(
n
)
do begin
1.
Select uniformly and independently a sequence of strings
x
1
,...,
=
n
.
x
t
(
n
)
∈{
0
,
1
}
B
(
f
(
x
1
)
2.
Compute (
z
1
,...,
z
t
(
n
)
)
←
,...,
f
(
x
i
−
1
)
,
y
,
f
(
x
i
+
1
)
,...,
f
(
x
t
(
n
)
)).
(Note that
y
is placed in the
i
th position instead of
f
(
x
i
).)
3.
If
f
(
z
i
)
y
, then halt and output
z
i
.
(This is considered a
success
).
end
=
Using Eq. (2.6), we now present a lower bound on the success probability of algorithm
A
. To this end we define a set, denoted
S
n
, that contains all
n
-bit strings on which the
procedure
I
succeeds with non-negligible probability (specifically, greater than
n
a
(
n
)
).
(The probability is taken only over the coin tosses of procedure
I
.
) Namely,
x
:
n
a
(
n
)
def
=
f
−
1
(
f
(
x
))]
S
n
Pr
[
I
(
f
(
x
))
∈
>
1
2
p
(
n
)
In the next two claims we shall show that
S
n
contains all but at most a
fraction
S
n
the algorithm
A
inverts
f
on
f
(
x
) with probability exponentially close to 1. It will follow that
A
inverts
f
on
f
(
U
n
), for
n
∈
N
, with probability greater than 1
−
N
and that for each string
x
of the strings of length
n
∈
∈
1
p
(
n
)
, in contradiction to our
hypothesis.
Claim 2.3.2.1:
For every
x
∈
S
n
,
1
2
n
Proof:
By definition of the set
S
n
, the procedure
I
inverts
f
(
x
) with probability
at least
Pr
[
A
(
f
(
x
))
∈
f
−
1
(
f
(
x
))]
>
1
−
a
(
n
)
. Algorithm
A
merely repeats
I
for
a
(
n
) times, and hence
n
1
a
(
n
)
n
a
(
n
)
1
2
n
[
A
(
f
(
x
))
f
−
1
(
f
(
x
))]
Pr
∈
<
−
<
The claim follows.
Claim 2.3.2.2:
For every
n
∈
N
,
1
1
2
p
(
n
)
2
n
|
S
n
|
>
−
·
1
Proof:
We assume, to the contrary, that
2
n
. We shall reach a
contradiction to Eq. (2.6) (i.e., our hypothesis concerning the success probability
of
B
). Recall that by this hypothesis (for
n
|
S
n
|≤
(1
−
2
p
(
n
)
)
·
∈
N
0),
B
g
U
n
2
p
(
n
)
∈
g
−
1
g
U
n
2
p
(
n
)
>
1
q
(
n
2
p
(
n
))
s
(
n
)
def
=
Pr
(2.7)
U
(
n
·
p
(
n
))
Let
U
(1)
n
n
denote the
n
-bit-long blocks in the random variable
U
n
2
p
(
n
)
(i.e., these
U
(
i
n
's are independent random variables each uniformly distributed in
{
,...,
n
). We partition the event considered in Eq. (2.7) into two disjoint events
corresponding to whether or not one of the
U
(
i
n
's resides out of
S
n
. Intuitively,
B
cannot perform well in such a case, since this case corresponds to the success
46
0
,
1
}
