Cryptography Reference
In-Depth Information
as follows. On input
y
and 1
n
(supposedly
y
is in the range of
f
(
U
n
), and
n
∈
I
),
algorithm
A
proceeds as follows:
def
=
1.
It computes
s
I
(
n
) and sets
k
s
I
(
n
)
−
n
−
1
≥
0. (Thus, for every
i
=
1
,...,
k
,
we have
n
+
i
∈
I
.)
k
, algorithm
A
invokes algorithm
B
on input (
y
1
n
+
i
), obtain-
2.
For
i
=
0
,
1
,...,
,
B
(
y
1
n
+
i
); if
g
(
z
i
)
y
, then
A
outputs the
n
-bit-long prefix
2
of
z
i
.
ing
z
i
←
,
=
Note that for all
x
∈{
0
,
1
}
n
and
|
x
|≤
k
,wehave
g
(
x
x
)
=
f
(
x
), and so if
g
(
x
x
)
=
y
, then
f
(
x
)
=
y
, which establishes the correctness of the output of
A
. Using
s
I
(
n
)
=
poly(
n
) and the fact that
s
I
(
n
) is computable in polynomial
time, it follows that if
B
is a probabilistic polynomial-time algorithm, then so is
A
. We next analyze the success probability of
A
(showing that if
B
inverts
g
with unallowable success probability, then
A
inverts
f
with unallowable success
probability).
Suppose that
B
inverts
g
on (
g
(
U
m
)
,
1
m
) with probability
ε
(
m
). Then there
exists an
n
such that
m
∈{
n
,...,
}
and such that
A
(
f
(
U
n
)
,
1
n
) invokes
B
poly(
n
)
on input (
f
(
U
n
)
,
1
m
)
=
(
g
(
U
m
)
,
1
m
). It follows that
A
(
f
(
U
n
)
,
1
n
) inverts
f
with
probability at least
ε
(
m
)
=
ε
(poly(
n
)). Thus,
A
(
f
(
U
n
)
,
1
n
) inherits the success
of
B
(
g
(
U
m
)
,
1
m
). A tedious analysis (which can be skipped) follows.
3
Suppose, contrary to our claim, that
g
is not strongly one-way, and let
B
be an algorithm
demonstrating this contradiction hypothesis. Namely, there exists a polynomial
p
(
·
)
such that for infinitely many
m
's the probability that
B
inverts
g
on
g
(
U
m
) is at least
1
p
(
m
)
. Let us denote the set of these
m
's by
M
. Define a function
I
:
N →
I
such that
I
(
m
) is the largest lower bound of
m
in
I
is both (i.e.,
I
(
m
)
def
=
max
{
i
∈
I
:
i
≤
m
}
).
Clearly,
m
1 for every
m
. The following two claims
relate the success probability of algorithm
A
with that of algorithm
B
.
≥
I
(
m
) and
m
≤
s
I
(
I
(
m
))
−
Claim 2.2.3.1:
Let
m
be an integer and
n
=
I
(
m
). Then
[
A
(
f
(
U
n
)
1
n
)
f
−
1
(
f
(
U
n
))]
[
B
(
g
(
U
m
)
1
m
)
g
−
1
(
g
(
U
m
))]
Pr
,
∈
≥
Pr
,
∈
(Namely, the success probability of algorithm
A
on
f
(
U
I
(
m
)
) is bounded below by
the success probability of algorithm
B
on
g
(
U
m
).)
Proof:
By construction of
A
, on input (
f
(
x
)
,
1
n
), where
x
∈{
0
,
1
}
n
, algorithm
A
obtains the value
B
(
f
(
x
)
1
t
) for every
t
. In particular, since
m
≥
n
and
m
≤
s
I
(
I
(
m
))
−
1
=
s
I
(
n
)
−
1, it follows that algorithm
A
obtains the
value
B
(
f
(
x
)
,
∈{
n
,...,
s
I
(
n
)
−
1
}
1
m
). By definition of
g
, for all
x
∈{
m
−
n
, it holds that
f
(
x
)
,
0
,
1
}
=
g
(
x
x
). The claim follows.
Claim 2.2.3.2:
There exists a polynomial
q
(
·
) such that
m
<
q
(
I
(
m
)) for all
m
's.
2
Here we use the assumption
z
i
∈{
0
,
1
}
n
+
i
, which implies that
n
is the largest integer that both is in
I
and
is at most
n
+
i
. In general,
A
outputs the longest prefix
x
of
z
i
satisfying
|
x
|∈
I
. Note that it holds that
f
(
x
)
=
g
(
z
i
)
=
y
.
3
The reader can verify that the following analysis does not refer to the length of the output of
B
and so does
not depend on the simplifying assumption made earlier.
