Cryptography Reference
In-Depth Information
formulation to present one-way functions with additional properties; specifically, we
consider (one-way) trapdoor permutations and claw-free function pairs. We remark that
these additional properties are used in several constructions presented in other chapters
of this topic (e.g., trapdoor permutations are used in the construction of public-key
encryption schemes, whereas claw-free permutations are used in the construction of
collision-free hashing). We conclude this section with remarks concerning the “art” of
proposing candidates for one-way functions.
2.4.1.
∗
Universal One-Way Function
Using the notion of a universal machine and the result of the preceding section, it is
possible to prove the existence of a
universal
one-way function; that is, we present a
(fixed) function that is one-way, provided that one-way functions exist.
Proposition 2.4.1:
There exists a polynomial-time-computable function that is
(strongly) one-way if and only if one-way functions exist.
Proof Sketch:
A key observation is that there exist one-way functions if and
only if there exist one-way functions that can be evaluated by a quadratic-time
algorithm. (The choice of the specific time bound is immaterial; what is important
is that such a specific time bound exists.) This statement is proved using a padding
argument. Details follow.
Let
f
be an arbitrary one-way function, and let
p
(
·
) be a polynomial bounding
the time complexity of an algorithm for computing
f
. Define
g
(
x
x
)
def
=
f
(
x
)
x
,
where
|
x
x
|=
p
(
|
x
|
). An algorithm computing
g
first parses the input into
x
and
x
so that
) and then applies
f
to
x
. The parsing and the other
overhead operations can be implemented in quadratic time (in
|
x
x
|=
p
(
|
x
|
|
x
x
|
), whereas
computing
f
(
x
) is done within time
p
(
(which is linear in the input
length). Hence,
g
can be computed (by a Turing machine) in quadratic time. The
reader can verify that
g
is one-way using a “reducibility argument” (analogous
to the one used in the proof of Proposition 2.2.5).
We now present a (universal one-way) function, denoted
f
uni
:
|
x
|
)
=|
x
x
|
f
uni
(desc(
M
)
,
x
)
def
=
(desc(
M
)
,
M
(
x
))
(2.9)
where desc(
M
) is a description of Turing machine
M
, and
M
(
x
) is defined as
the output of
M
on input
x
if
M
runs at most quadratic time on
x
, and
M
(
x
)
is defined as
x
otherwise. (Without loss of generality, we can view any string
as the description of some Turing machine.) Clearly,
f
uni
can be computed in
polynomial time by a universal machine that uses a step counter. To show that
f
uni
is weakly one-way (provided that one-way functions exist at all), we use a
“reducibility argument.”
Assuming that one-way functions exist, and using the foregoing observation,
it follows that there exists a one-way function
g
that is computed in quadratic
time. Let
M
g
be the quadratic-time machine computing
g
. Clearly, an (efficient)
52
