Cryptography Reference
In-Depth Information
We now present an upper bound on
s
2
(
n
). Recall that by the contradiction
hypothesis,
1
2
n
. It follows that
|
S
n
|≤
(1
−
2
p
(
n
)
)
·
∈
S
n
∀
i
:
U
(
i
)
n
s
2
(
n
)
≤
Pr
1
−
n
·
p
(
n
)
1
2
p
(
n
)
≤
n
2
p
(
n
)
a
(
n
)
(The last inequality holds for sufficiently large
n
.)
Combining the upper bounds on the
s
i
's, we have
s
1
(
n
)
1
2
n
/
2
<
·
<
2
n
2
·
p
(
n
)
a
(
n
)
+
s
2
(
n
)
<
=
1
q
(
n
2
p
(
n
))
, where equality is by the definition of
a
(
n
). Yet, on the other hand,
s
1
(
n
)
+
1
s
2
(
n
)
q
(
n
2
p
(
n
))
, where the inequality is due to Eq. (2.7). Contradiction is
reached, and the claim follows.
=
s
(
n
)
>
Combining Claims 2.3.2.1 and 2.3.2.2, we obtain
[
A
(
f
(
U
n
))
∈
f
−
1
(
f
(
U
n
))]
Pr
[
A
(
f
(
U
n
))
∈
f
−
1
(
f
(
U
n
))
∧
U
n
∈
S
n
]
≥
Pr
=
Pr
[
U
n
∈
S
n
]
·
Pr
[
A
(
f
(
U
n
))
∈
f
−
1
(
f
(
U
n
))
|
U
n
∈
S
n
]
1
−
·
1
−
2
−
n
>
1
−
1
p
(
n
)
It follows that there exists a probabilistic polynomial-time algorithm (i.e.,
A
)
that inverts
f
on
f
(
U
n
), for
n
1
2
p
(
n
)
≥
1
p
(
n
)
. This
conclusion, which follows from the hypothesis that
g
is not strongly one-way
(i.e., Eq. (2.6)), stands in contradiction to the hypothesis that every probabilistic
polynomial-time algorithm fails to invert
f
with probability at least
∈
N
, with probability greater than 1
−
1
p
(
n
)
, and the
theorem follows.
2.3.2. Illustration by a Toy Example
Let us try to further clarify the algorithmic ideas underlying the proof of Theorem 2.3.2.
To do so, consider the following quantitative notion of weak one-way functions. We say
that (a polynomial-time-computable)
f
is
ρ
-one-way
if for all probabilistic polynomial-
time algorithms
A
, for all but finitely many
n
's, the probability that on input
f
(
U
n
)
algorithm
A
fails
to find a pre-image under
f
is
at least
ρ
(
n
). (Each weak one-way
function is 1
/
p
()-one-way for some polynomial
p
, whereas strong one-way functions
are (1
−
µ
())-one-way, where
µ
is a negligible function.)
1
Proposition 2.3.3 (Toy Example):
Suppose that
f
is
3
-one-way, and let
g
(
x
1
,
x
2
)
def
(
3
)
2
)
.
=
(
f
(
x
1
)
,
f
(
x
2
))
. Then g is
0
.
55
-one-way
(
where
0
.
55
<
1
−
Proof Outline:
Suppose, toward the contradiction, that there exists a polynomial-
time algorithm
A
that inverts
g
(
U
2
n
) with success probability greater than
48
