Cryptography Reference
In-Depth Information
arguments, then we cannot live with a constant
n
. Instead, we must make
n
variable,
and it must be possible to let
n
grow arbitrarily large. Consquently, we must work
with potentially infinite
families
1
of one-way functions
(i.e., at least one for each
n
).
The notion of a family of one-way functions is formally captured in Definition 7.3.
Definition 7.3 (Family of one-way function)
A family of functions
F
=
{
f
i
:
X
i
→
Y
i
}
i∈I
is a
family of one-way functions
if the following three conditions
are fulfilled:
•
I
is an infinite index set;
•
Every
i
∈
I
selects a function
f
i
:
X
i
→
Y
i
from the family;
•
Every
f
i
:
X
i
→
Y
i
is a one-way function according to Definition 7.1.
Y
i
}
i∈I
is a
family of one-way
permutations
if every
f
i
is a permutation over the domain
X
i
(i.e.,
Y
i
=
X
i
).
Furthermore, it is a
family of trapdoor functions
if every
f
i
is a trapdoor function
with trapdoor information
t
i
.
In this topic, we often talk about one-way functions and trapdoor functions
when we should actually be talking about families of such functions. We make
this simplification because we think that it is more appropriate and simpler to
understand. In either case, we want to emphasize that there is no function—or
family of functions—known to be one way (in a mathematically strong sense)
and that the current state of knowledge in complexity theory does not allow us to
prove the existence of one-way functions, even using more traditional assumptions
as
A family of one-way functions
{
f
i
:
X
i
→
. Hence, only a few functions are conjectured to be one way. These
candidate one-way functions are overviewed and discussed next.
P
=
NP
7.2
CANDIDATE ONE-WAY FUNCTIONS
There are a couple of functions that are conjectured to be one way. For example,
a symmetric encryption system that encrypts a fixed plaintext message yields such
a function.
2
For example, the use of DES in this construction can be shown to be
one way assuming that DES is a family of pseudorandom functions. Another simple
example is the integer multiplication function
f
:(
x, y
)
.As
discussed later in this chapter, no efficient algorithm is known to find the prime
factors of a large integer.
→
xy
for
x, y
∈
Z
1
In some literature, the terms “classes,” “collections,” or “ensembles” are used instead of “families.”
2
For example, UNIX systems use such a function to store the user passwords in protected form.
