Cryptography Reference
In-Depth Information
as follows:
g
x
1
,...,
x
t
(
n
)
def
,...,
f
x
t
(
n
)
=
f
(
x
1
)
(2.5)
where
|
x
1
|=···=|
x
t
(
n
)
|=
n
and
t
(
n
)
def
=
n
·
p
(
n
). Namely, the
n
2
p
(
n
)-bit-long in-
put of
g
is partitioned into
t
(
n
) blocks, each of length
n
, and
f
is applied to each
block.
Clearly,
g
can be computed in polynomial time (by an algorithm that breaks the
input into blocks and applies
f
to each block). Furthermore, it is easy to see that
inverting
g
on
g
(
x
1
,...,
x
t
(
n
)
) requires finding a pre-image to each
f
(
x
i
). One may
be tempted to deduce that it is also clear that
g
is a strongly one-way function. A
naive argument might proceed by assuming implicitly (with no justification) that the
inverting algorithm worked separately on each
f
(
x
i
). If that were indeed the case,
then the probability that an inverting algorithm could successfully invert all
f
(
x
i
)
1
would be at most (1
2
−
n
(which is negligible also as a function of
n
2
p
(
n
)). However, the assumption that an algorithm trying to invert
g
works inde-
pendently on each
−
p
(
n
)
)
n
·
p
(
n
)
<
f
(
x
i
) cannot be justified. Hence, a more complex argument is
required.
Following is an outline of our proof. The proof that
g
is strongly one-way proceeds
by a contradiction argument. We assume, on the contrary, that
g
is not strongly one-way;
namely, we assume that there exists a polynomial-time algorithm that inverts
g
with
probability that is not negligible. We derive a contradiction by presenting a polynomial-
time algorithm that, for infinitely many
n
's, inverts
f
on
f
(
U
n
) with probability greater
than 1
1
p
(
n
)
(in contradiction to our hypothesis). The inverting algorithm for
f
uses
the inverting algorithm for
g
as a subroutine (without assuming anything about the
manner in which the latter algorithm operates). (We stress that we do not assume that
the
g
-inverter works in a particular way, but rather use any
g
-inverter to construct, in a
generic way, an
f
-inverter.) Details follow.
Suppose that
g
is not strongly one-way. By definition, it follows that there exists a
probabilistic polynomial-time algorithm
B
and a polynomial
q
(
·
) such that for infinitely
many
m
's,
−
1
q
(
m
)
Pr
[
B
(
g
(
U
m
))
∈
g
−
1
(
g
(
U
m
))]
>
(2.6)
Let us denote by
M
the infinite set of integers for which this holds. Let
N
denote the
infinite set of
n
's for which
n
2
M
(note that all
m
's considered are of the form
·
p
(
n
)
∈
n
2
p
(
n
), for some integer
n
).
Using
B
, we now present a probabilistic polynomial-time algorithm
A
for inverting
f
. On input
y
(supposedly in the range of
f
), algorithm
A
proceeds by applying
the following probabilistic procedure, denoted
I
, on input
y
for
a
(
·
) times, where
a
(
·
) is a polynomial that depends on the polynomials
p
and
q
(specifically, we set
a
(
n
)
def
|
y
|
=
2
n
2
·
p
(
n
)
·
q
(
n
2
p
(
n
))).
Procedure
I
def
=|
Input
:
y
(denote
n
y
|
).
