Cryptography Reference
In-Depth Information
hard to invert in practice on 1% of the strings of length 1000, then g is hard to invert
in practice on almost all strings of length 5000
. The following definition is natural for
a general discussion of amplification of one-way functions.
Definition 2.6.1 (Quantitative One-Wayness):
Let T
:
N → N
and
ε
:
N → R
be polynomial-time-computable functions. A polynomial-time-computable func-
tion f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
is called
ε
(
·
)-
one-way with respect to time
T
(
·
)
if for
every algorithm A
, with running time bounded by T
(
·
)
and all sufficiently large
n's,
Pr
[
A
(
f
(
U
n
))
f
−
1
(
f
(
U
n
))]
∈
>ε
(
n
)
Using this terminology, we review what we already know about amplification of one-
way functions. A function
f
is weakly one-way if there exists a polynomial
p
(
·
) such
1
p
(
that
f
is
)
-one-way with respect to polynomial time.
14
A function
f
is strongly
·
1
one-way if for every polynomial
q
(
·
), the function
f
is (1
−
q
(
·
)
)-one-way with respect
to polynomial time. (The identity function is only 0-one-way with respect to linear
time, whereas no function is (1
−
exp(
·
))-one-way with respect to linear time.
15
) The
amplification result of Theorem 2.3.2 can be generalized and restated as follows:
If there
exist a polynomial p and a
(
polynomial-time-computable
)
function f that is
1
p
(
·
)
-one-
way with respect to time T
(
·
)
, then there exists a
(
polynomial-time-computable
)
function
g that is strongly one-way with respect to respect to time T
(
·
)
, where T
(
n
2
·
p
(
n
))
=
·
p
(
n
))
ε
≤
n
.In
contrast, an efficient amplification of one-way functions, as given later, should state
that the foregoing holds with respect to
T
(
O
(
n
))
T
(
n
)
, or, in other words, T
(
n
)
=
T
(
n
ε
)
for some
ε>
0
satisfying
(
n
2
=
T
(
n
) (in other words,
T
(
n
)
=
0). Such a result can be obtained for
regular
one-way functions.
A function
f
is called
regular
if there exists a polynomial-time-computable function
m
:
T
(
ε
·
n
) for some
ε>
) such that for every
y
in the range of
f
, the number
of pre-images (of length
n
)of
y
under
N → N
and a polynomial
p
(
·
m
(
n
)
p
(
n
)
p
(
n
). In this
topic we review the result only for one-way permutations (i.e., length-preserving 1-1
functions).
f
is between
and
m
(
n
)
·
Theorem 2.6.2 (Efficient Amplification of One-Way Permutations):
Let p
(
·
)
be a polynomial, and T
:
N → N
. function. Suppose that
f is a polynomial-
1
p
(
time-computable permutation that is
)
-one-way with respect to time T
(
·
)
. Then
there exists a constant
γ>
1
, a polynomial q, and a polynomial-time-computable
permutation F such that for every polynomial-time-computable function
·
N →
:
[0
,
1]
, the function F is
(1
−
(
·
))
-one-way with respect to time T
(
·
)
, where
T
(
γ
·
n
)
def
=
(
n
)
2
q
(
n
)
·
T
(
n
)
.
The constant
γ
depends only on the polynomial
p
(
·
).
14
Here and later,
with respect to polynomial time
means with respect to time
T
, for every polynomial
T
.
15
The identity function can be “inverted” with failure probability zero in linear time. On the other hand, for
every function
f
, the algorithm that, given
y
, outputs 0
|
y
|
inverts
f
on
f
(
U
n
) with failure probability of at most
1
−
2
−
n
<
1
−
exp(
−
n
).
