Cryptography Reference
In-Depth Information
Figure 2.1
A one-way function.
Definition 2.1 (One-way function)
A function
f
:
X
→
Y
is
one way
if
f
(
x
)
can
X
,but
f
−
1
(
y
)
cannot be computed efficiently for
be computed efficiently for all
x
∈
y
∈
R
Y
.
In this definition,
X
represents the domain of the function
f
,
Y
represents the
range, and the expression
y
∈
R
Y
stands for “a
y
that is randomly chosen from
Y
.” Consequently, it must be possible to efficiently compute
f
(
x
) for all
x
X
,
whereas it must not—or only with a negligible probability—be possible to compute
f
−
1
(
y
) for a randomly chosen
y
∈
Y
. To be more precise, one must say that it may
be possible to compute
f
−
1
(
y
), but that the entity that wants to do the computation
does not know how to actually do it. In either case, Definition 2.1 is not precise in
a mathematically strong sense, because we have not yet defined what an efficient
computation really is. This must be postponed to somewhere after Chapter 6, when
we have introduced the fundamentals and basic principles of complexity theory. In
the meantime, it is sufficient to know that a computation is said to be efficient, if the
(expected) running time of the algorithm that does the computation is bounded by a
polynomial in the length of the input. The algorithm itself may be probabilistic.
Otherwise (i.e., if the expected running time is not bounded by a polynomial),
the algorithm requires super-polynomial (e.g., exponential) time and is said to be
inefficient. This notion of efficiency (and the distinction between polynomial and
super-polynomial running time algorithms) is fairly broad. It is, however, the best
we have at hand to work with.
An everyday example of a one-way function is a telephone book. Using
such a topic, the function that assigns a telephone number to a name is easy to
compute (because the names are sorted alphabetically) but hard to invert (because
the telephone numbers are not sorted numerically). Furthermore, many physical
processes are inherently one way. If, for example, we smash a bottle into pieces,
it is generally infeasible (or at least prohibitively difficult) to put the pieces together
and reconstruct the bottle. Similarly, if we drop a bottle from a bridge, it falls down.
∈
