Cryptography Reference
In-Depth Information
The reverse process does not frequently occur in the real world. Last but not least,
life is one way, and it is (currently) not known how to travel back in time.
In contrast to the real world, the idealized world of mathematics is less rich
with one-way functions. In fact, there are only a couple of functions conjectured
to be one way. As overviewed and discussed in Section 7.2, examples include
the discrete exponentiation function, the modular power function, and the modular
square function. But note that none of these functions has been shown to be one way
and that it is theoretically not even known whether one-way functions really exist.
These facts should be kept in mind when one discusses the usefulness and actual use
of one-way functions in cryptography.
There is a class of one-way functions that can be inverted efficiently if and—as
it is hoped—only if some extra information is known. This brings us to the notion
of a
trapdoor (one-way) function
as suggested in Definition 2.2.
Definition 2.2 (Trapdoor function)
A one-way function
f
:
X
Y
is a
trapdoor
function
(or a
trapdoor one-way function
, respectively) if there exists some extra
information (i.e., the
trapdoor
) with which
f
can be inverted efficiently (i.e.,
f
−
1
(
y
)
can be computed efficiently for
y
→
∈
R
Y
).
The mechanical analog of a trapdoor (one-way) function is a padlock. It can
be closed by everybody (if it is in an unlocked state), but it can be opened only
by somebody who holds or has access to the proper key. In this analogy, a padlock
without a keyhole would represent a one-way function (without trapdoor). This may
not be a very useful construct in the real world.
One-way functions and trapdoor functions are frequently used in public key
cryptography. In fact, they yield all kinds of asymmetric encryption systems, DSSs,
and key agreement protocols. They are further addressed in Chapter 7. We then also
explain why one has to consider families of such functions to be mathematically
correct (so a one-way or trapdoor function actually refers to a family of such
functions).
2.1.2
Cryptographic Hash Functions
Hash functions are frequently used and have many applications in computer science.
Informally speaking, a hash function is an efficiently computable function that takes
an arbitrarily sized input (string) and generates an output (string) of fixed size. This
idea is captured in Defintion 2.3.
Definition 2.3 (Hash function)
Let
Σ
in
be an input alphabet and
Σ
out
be an output
alphabet. Any function
h
:Σ
in
→
Σ
out
that can be computed efficiently is said to
be a
hash function
. It generates hash values of length
n
.
