Cryptography Reference
In-Depth Information
2.2.3.1. Functions Defined Only for Some Lengths
In many cases it is more convenient to consider one-way functions with domains partial
to the set of all strings. In particular, this facilitates the introduction of some structure in
the domain of the function. A particularly important case, used throughout the rest of this
section, is that of functions with domain
∪
n
∈N
{
0
,
1
}
l
(
n
)
, where
l
(
·
) is some polynomial.
We provide a more general treatment of this case.
Let
I
, and denote by
s
I
(
n
) the successor of
n
with respect to
I
; namely,
s
I
(
n
)is
the smallest integer that is both greater than
n
and in the set
I
(i.e.,
s
I
(
n
)
def
⊆ N
=
min
{
i
∈
I
:
i
is called
polynomial-time-enumerable
if there exists an algorithm
that on input
n
halts within poly(
n
) steps and outputs 1
s
I
(
n
)
. (The unary output forces
s
I
to be polynomially bounded; i.e.,
s
I
(
n
)
≤
poly(
n
).) Let
I
be a polynomial-time-
enumerable set and
f
be a function with domain
∪
n
∈
I
{
0
,
1
}
>
n
}
). A set
I
⊆ N
n
. We call
f
strongly (resp.,
weakly)
one-way on lengths in I
if
f
is polynomial-time-computable and is hard to
invert over
n
's in
I
. For example, the hardness condition for functions that are strongly
one-way on lengths in
I
is stated as follows:
For every probabilistic polynomial-time algorithm A
, every positive polynomial p
(
·
)
, and
all sufficiently large n's in I
,
1
p
(
n
)
Ordinary one-way functions, as defined in previous subsections, can be viewed as being
one-way on lengths in
N
.
One-way functions on lengths in any polynomial-time-enumerable set can be eas-
ily transformed into ordinary one-way functions (i.e., defined over all of
{
0
,
1
}
∗
). In
particular, for any function
f
with domain
∪
n
∈
I
{
0
,
1
}
[
A
(
f
(
U
n
)
1
n
)
f
−
1
(
f
(
U
n
))]
Pr
,
∈
<
n
, we can construct a function
g
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
by letting
g
(
x
)
def
f
(
x
)
=
(2.1)
where
x
is the longest prefix of
x
with length in
I
. In case the function
f
is length-
preserving (i.e.,
for all
x
), we can preserve this property by modifying the
construction to obtain a length-preserving function
g
:
|
f
(
x
)
|=|
x
|
}
∗
→{
}
∗
such that
{
0
,
1
0
,
1
g
(
x
)
def
=
f
(
x
)
x
(2.2)
where
x
=
x
x
, and
x
is the longest prefix of
x
with length in
I
.
Proposition 2.2.3:
Let I be a polynomial-time-enumerable set, and let f be
strongly (resp., weakly) one-way on lengths in I . Then g and g
(
as defined in
Eq. (2.1)
and
Eq. (2.2)
, respectively
)
are strongly (resp., weakly) one-way (in the
ordinary sense).
Although the validity of the foregoing proposition is very appealing, we urge the reader
not to skip the following proof. The proof, which is indeed quite simple, uses (for the
first time in this topic) an argument that is used extensively in the sequel. The argument
used to prove the hardness-to-invert property of the function
g
(resp.,
g
) proceeds by
36
