Computational Difficulty - Foundations of Cryptography: Basic Tools - page 30

CHAPTER 2
Computational Difficulty
In this chapter we define and study one-way functions. One-way functions capture
our notion of “useful” computational difficulty and serve as a basis for most of the
results presented in this topic. Loosely speaking, a one-way function is a function that
is easy to evaluate but hard to invert (in an average-case sense). (See the illustration
in Figure 2.1.) In particular, we define strong and weak one-way functions and prove
that the existence of weak one-way functions implies the existence of strong ones. The
proof provides a good example of a reducibility argument , which is a strong type of
“reduction” used to establish most of the results in the area. Furthermore, the proof
provides a simple example of a case where a computational statement is much harder
to prove than its “information-theoretic analogue.”
In addition, we define hard-core predicates and prove that every one-way function
has a hard-core predicate. Hard-core predicates will play an important role in almost
all subsequent chapters (the chapter on signature scheme being the exception).
Organization. In Section 2.1 we motivate the definition of one-way functions by argu-
ing informally that it is implicit in various natural cryptographic primitives. The basic
definitions are given in Section 2.2, and in Section 2.3 we show that weak one-way
functions can be used to construct strong ones. A more efficient construction (for certain
restricted cases) is postponed to Section 2.6. In Section 2.4 we view one-way functions
as uniform collections of finite functions and consider various additional properties
that such collections may have. In Section 2.5 we define hard-core predicates and show
how to construct them from one-way functions.
Teaching Tip. As stated earlier, the proof that the existence of weak one-way functions
implies the existence of strong ones (see Section 2.3) is instructive for the rest of the
material. Thus, if you choose to skip this proof, do incorporate a discussion of the
reducibility argument in the first place you use it (e.g., when showing how to construct
hard-core predicates from one-way functions).
30