Cryptography Reference
In-Depth Information
assuming, toward the contradiction, that
g
(resp.,
g
) can be efficiently inverted with
unallowable success probability. Contradiction is derived by deducing that
f
can be
efficiently inverted with unallowable success probability. In other words, inverting
f
is “reduced” to inverting
g
(resp.,
g
). The term “reduction” is used here in a stronger-
than-standard sense. Here a reduction needs to preserve the success probability of the
algorithms. This kind of argument is called a
reducibility argument
.
Proof:
We first prove that
g
and
g
can be computed in polynomial time. To this
end we use the fact that
I
is a polynomial-time-enumerable set, which implies that
we can decide membership in
I
in polynomial time (e.g., by observing that
m
∈
I
if and only if
s
I
(
m
−
1)
=
m
). It follows that on input
x
one can find in poly-
nomial time the largest
m
I
. Computing
g
(
x
) amounts
to finding this
m
and applying the function
f
to the
m
-bit prefix of
x
. Similarly
for
g
.
We next prove that
g
maintains the hardness-to-invert property of
f
. A similar
proof establishes the hardness-to-invert property of
g
. For the sake of brevity, we
present here only the proof for the case that
f
is strongly one-way. The proof for
the case that
f
is weakly one-way is analogous.
The proof proceeds by contradiction. We assume, contrary to the claim (of
the proposition), that there exists an efficient algorithm that inverts
g
with suc-
cess probability that is not negligible. We use this inverting algorithm (for
g
)to
construct an efficient algorithm that inverts
f
with success probability that is not
negligible, hence deriving a contradiction (to the hypothesis of the proposition).
In other words, we show that inverting
f
(with unallowable success probability)
is efficiently reducible to inverting
g
(with unallowable success probability) and
hence conclude that the latter is not feasible. The reduction is based on the obser-
vation that inverting
g
on images of arbitrary lengths yields inverting
g
also on
images of lengths in
I
, and that on such lengths
g
collides with
f
.
Intuitively, any algorithm inverting
g
can be used to invert
f
as follows. On
input (
y
≤|
x
|
that satisfies
m
∈
,
1
n
), where
y
is supposedly in the image of
f
(
U
n
)
=
g
(
U
m
) for any
m
1
m
) and output
the longest prefix with length in
I
of the string that the
g
-inverter returns (e.g., if the
g
-inverter returns an
m
-bit-long string, then we output its
n
-bit-long prefix). Thus,
our success probability in inverting
f
on
f
(
U
n
) equals the success probability of
the
g
-inverter on
g
(
U
m
). The question is which
m
∈{
n
,...,
s
I
(
n
)
−
1
}
we should
use, and the answer is to try them all (capitalizing on the fact that
s
I
(
n
)
=
poly(
n
)).
Note that the integers are partitioned to intervals of the form [
n
,...,
s
I
(
n
)
−
1],
each associated with a single
n
∈
I
. Thus, the success probability of any
g
-inverter on infinitely many lengths
m
∈ N
translates to the success probability
of our
f
-inverter on infinitely many lengths
n
∈
I
. Details follow.
Given an algorithm
B
for inverting
g
, we construct an algorithm
A
for invert-
ing
f
such that
A
has complexity and success probability related to those for
B
.
(For simplicity, we shall assume that
B
(
y
∈{
n
,...,
s
I
(
n
)
−
1
}
, we can invoke the
g
-inverter on input (
y
,
1
m
)
m
}
∗
,
∈{
0
,
1
}
holds for all
y
∈{
0
,
1
and
m
∈ N
; this assumption is immaterial, and later we comment about this aspect
in two footnotes.) Algorithm
A
uses algorithm
B
as a subroutine and proceeds
37
