Cryptography Reference
In-Depth Information
Proof:
Let
q
be a polynomial (as guaranteed by the polynomial-time enumer-
ability of
I
) such that
s
I
(
n
)
<
q
(
n
). Then, for every
m
,wehave
m
<
s
I
(
I
(
m
))
<
q
(
I
(
m
)).
def
={
I
(
m
):
m
By Claim 2.2.3.2, the set
S
∈
M
}
is infinite (as, otherwise, for
u
upper-
bounding the elements in
S
we get
m
<
q
(
≤
q
(
u
) for every
m
∈
M
, which
contradicts the hypothesis that
M
is infinite). Using Claim 2.2.3.1, it follows that for
every
n
I
(
m
))
S
, the probability that
A
inverts
f
on
f
(
U
n
) is at least
1
p
(
m
)
>
=
I
(
m
)
∈
1
poly(
n
)
where the inequality is due to Claim 2.2.3.2. It follows that
f
is not strongly one-way,
in contradiction to the proposition's hypothesis.
1
p
(
q
(
I
(
m
)))
=
1
p
(
q
(
n
))
=
2.2.3.2. Length-Regular and Length-Preserving Functions
A second useful convention regarding one-way functions is to assume that the function
f
is
length-regular
in the sense that for every
x
}
∗
,if
,
y
∈{
0
,
1
|
x
|=|
y
|
, then
|
f
(
x
)
|=
|
. We point out that the transformation presented earlier (i.e., both Eq. (2.1) and
Eq. (2.2)) preserves length regularity. A special case of length regularity, preserved by
Eq. (2.2), is that of
length-preserving
functions.
f
(
y
)
|
Definition 2.2.4 (Length-Preserving Functions):
A function
f
is
length-
preserving
if for every x
∈{
0
,
1
}
∗
it holds that
|
f
(
x
)
|=|
x
|
.
Given a strongly (resp., weakly) one-way function
f
, we can construct a strongly (resp.,
weakly) one-way function
f
that is length-preserving, as follows. Let
p
be a polyno-
mial bounding the length expansion of
f
(i.e.,
|
f
(
x
)
|≤
p
(
|
x
|
)). Such a polynomial must
exist because
f
is polynomial-time-computable. We first construct a length-regular
function
f
by defining
f
(
x
)
def
f
(
x
)10
p
(
|
x
|
)
−|
f
(
x
)
|
=
(2.3)
(We use a padding of the form 10
∗
in order to facilitate the parsing of
f
(
x
) into
f
(
x
)
and the “leftover” padding.) Next, we define
f
only on strings of length
p
(
n
)
+
1, for
n
∈ N
, by letting
f
(
x
x
)
def
=
f
(
x
) , where
|
x
x
|=
p
(
|
x
|
)
+
1
(2.4)
Clearly,
f
is length-preserving.
Proposition 2.2.5:
If f is a strongly
(
resp., weakly
)
one-way function, then so
are f
and f
(as defined in
Eq. (2.3)
and
Eq. (2.4)
, respectively).
Proof Sketch:
It is quite easy to see that both
f
and
f
are polynomial-time-
computable. Using “reducibility arguments” analogous to the one used in the
preceding proof, we can establish the hardness-to-invert of both
f
and
f
.For
example, given an algorithm
B
for inverting
f
, we construct an algorithm
A
for
39
