Cryptography Reference
In-Depth Information
Chapter 7
One-Way Functions
As mentioned several times so far, one-way functions and trapdoor functions play
a fundamental role in modern cryptography. In this chapter, we elaborate on these
functions. More specifically, we introduce the topic in Section 7.1, overview and
discuss some candidate one-way functions in Section 7.2, elaborate on integer
factorization algorithms and algorithms to compute discrete logarithms in Sections
7.3 and 7.4, address hard-core predicates in Section 7.5, briefly introduce the notion
of elliptic curve cryptography in Section 7.6, and conclude with final remarks in
Section 7.7.
7.1
INTRODUCTION
In Section 2.1.1 and Definition 2.1, we introduced the notion of a one-way function.
More specifically, we said that a function
f
:
X
→
Y
is one way if
f
(
x
) can
be computed efficiently for all
x
∈
X
,but
f
−
1
(
y
) cannot be computed efficiently
for
y
∈
R
Y
(see Figure 2.1). We also noted that this definition is not precise in
a mathematically strong sense and that we must first introduce some complexity-
theoretic basics (mainly to define more precisely what we mean by saying that we
can or we cannot compute efficiently). Because we have done this in Chapter 6, we
are now ready to better understand and more precisely define the notion of a one-way
function. This is done in Definition 7.1.
Definition 7.1 (One-way function)
A function
f
:
X
→
Y
is
one way
if the
following two conditions are fulfilled:
•
The function
f
is easy to compute, meaning that
f
(
x
)
can be computed
efficiently for all
x
X
. Alternatively speaking, there is a probabilistic
polynomial-time (PPT) algorithm
A
that outputs
A
(
x
)=
f
(
x
)
for all
x
∈
∈
X
.
