Cryptography Reference
In-Depth Information
string is distributed as in
I
(1
n
), and (2) for every (
i, t
) in the range of
I
(1
n
)andevery
x
D
i
it holds that
F
−
1
(
t, f
i
(
x
)) =
x
.(Thatis,
t
is a
trapdoor that allows to invert
f
i
.)
∈
For example, in the case of the RSA,
f
N,e
can be inverted by raising to
the power
d
(modulo
N
=
P ·Q
), where
d
is the multiplicative inverse of
e
modulo (
P
−
1)
·
(
Q
−
1). Indeed, in this case, the trapdoor information
is (
N,d
).
Strong versus weak one-way functions
Recall that the above definitions require that any feasible algorithm
succeeds in inverting
the function
with negligible probability
.Aweaker
notion only requires that any feasible algorithm
fails to invert
the
function
with noticeable probability
. It turns out that the existence of
such weak one-way functions implies the existence of strong one-way
functions (as defined above). The construction itself is straightforward:
one just parses the argument to the new function into suciently many
blocks, and applies the weak one-way function on the individual blocks.
We warn that the hardness of inverting the resulting function is not
established by mere “combinatorics” (i.e., considering the relative vol-
ume of
S
t
in
U
t
,for
S
U
,where
S
represents the set of “easy to invert”
images). Specifically, one may
not
assume that the potential inverting
algorithm works independently on each block. Indeed this assumption
seems reasonable, but we should not assume that the adversary behaves
in a reasonable way (unless we can actually prove that it gains nothing
by behaving in other ways, which seem unreasonable to us).
The hardness of inverting the resulting function is proved via a
so-called “reducibility argument” (which is used to prove all condi-
tional results in the area). Specifically, we show that any algorithm that
inverts the resulting function
F
with non-negligible success probability
can be used to construct an algorithm that inverts the original function
f
with success probability that violates the hypothesis (regarding
f
). In
other words, we reduce the task of “strongly inverting”
f
(i.e., violating
its weak one-wayness) to the task of “weakly inverting”
F
(i.e., violating
its strong one-wayness). We hint that, on input
y
=
f
(
x
), the reduction
⊂
