Cryptography Reference
In-Depth Information
=
Pr
[
A
∩
B
]
Pr
[
B
]
(For the second inequality, we used
−
Pr
[
¬
B
].) It should not come as a surprise that the above expression is meaningful only
in case
Pr
[
A
|
B
]
and
Pr
[
A
∩
B
]
≥
Pr
[
A
]
[
B
(
g
(
U
2
n
))
g
−
1
(
g
(
U
2
n
))]
1
n
.
It follows that for every polynomial
p
(
·
) and every integer
n
,if
B
inverts
g
on
g
(
U
2
n
)
with probability greater than 1
Pr
∈
>
1
−
p
(2
n
)
, then
A
inverts
f
on
f
(
U
n
) with probability
1
−
n
p
(2
n
)
. Hence, if
g
is not weakly one-way (i.e., for every polynomial
greater than 1
−
) there exist infinitely many
m
's such that
g
can be inverted on
g
(
U
m
) with probabil-
ity
≥
1
−
1
/
p
(
m
)), then also
f
is not weakly one-way (i.e., for every polynomial
q
(
·
)
there exist infinitely many
n
's such that
f
can be inverted on
f
(
U
n
) with probability
≥
1
−
1
/
q
(
n
), where
q
(
n
)
=
p
(2
n
)
/
n
). This contradicts our hypothesis (that
p
(
·
f
is
weakly one-way).
To summarize, given a probabilistic polynomial-time algorithm that inverts
g
on
g
(
U
2
n
) with success probability 1
1
n
−
+
α
(
n
), we obtain a probabilistic
polynomial-time algorithm that inverts
f
on
f
(
U
n
) with success probability
n
q
(
n
)) must hold
for some polynomial
q
, and so
g
must be weakly one-way (since each proba-
bilistic polynomial-time algorithm trying to invert
g
on
g
(
U
2
n
) must fail with
probability at least
·
α
(
n
). Thus, since
f
is (weakly) one-way,
n
·
α
(
n
)
<
1
−
(1
/
1
n
1
−
α
(
n
)
>
n
·
q
(
n
)
).
We have just shown that unless no one-way functions exist, there exist weak one-
way functions that are not strong ones. This rules out the possibility that all one-way
functions are strong ones. Fortunately, we can also rule out the possibility that all
one-way functions are (only) weak ones. In particular, the existence of weak one-way
functions implies the existence of strong ones.
Theorem 2.3.2:
Weak one-way functions exist if and only if strong one-way
functions exist.
We strongly recommend that the reader not skip the proof (given in Section 2.3.1),
since we believe that the proof is very instructive to the rest of this topic. Furthermore,
the proof demonstrates that amplification of computational difficulty is much more
involved than amplification of an analogous probabilistic event. Both aspects are further
discussed in Section 2.3.3. An illustration of the proof in the context of a “toy” example
is provided in Section 2.3.2. (It is possible to read Section 2.3.2 before Section 2.3.1;
in fact, most readers may prefer to do so.)
2.3.1. Proof of Theorem 2.3.2
Let
f
be a weak one-way function, and let
p
be the polynomial guaranteed by the
definition of a weak one-way function. Namely, every probabilistic polynomial-time
algorithm fails to invert
f
on
f
(
U
n
) with probability at least
1
p
(
n
)
. We assume, for
simplicity, that
f
is length-preserving (i.e.
for all
x
's). This assumption,
which is not really essential, is justified by Proposition 2.2.5. We define a function
g
44
|
f
(
x
)
|=|
x
|
