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

⊂