Introduction - Foundations of Cryptography: Basic Tools - page 1

CHAPTER 1
Introduction
In this chapter we briefly discuss the goals of cryptography (Section 1.1). In particular,
we discuss the basic problems of secure encryption, digital signatures, and fault-tolerant
protocols. These problems lead to the notions of pseudorandom generators and zero-
knowledge proofs, which are discussed as well.
Our approach to cryptography is based on computational complexity. Hence, this
introductory chapter also contains a section presenting the computational models used
throughout the topic (Section 1.3). Likewise, this chapter contains a section presenting
some elementary background from probability theory that is used extensively in the
topic (Section 1.2).
Finally, we motivate the rigorous approach employed throughout this topic and
discuss some of its aspects (Section 1.4).
Teaching Tip. Parts of Section 1.4 may be more suitable for the last lecture (i.e., as
part of the concluding remarks) than for the first one (i.e., as part of the introductory
remarks). This refers specifically to Sections 1.4.2 and 1.4.3.
1.1. Cryptography: Main Topics
Historically, the term “cryptography” has been associated with the problem of design-
ing and analyzing encryption schemes (i.e., schemes that provide secret communica-
tion over insecure communication media). However, since the 1970s, problems such
as constructing unforgeable digital signatures and designing fault-tolerant protocols
have also been considered as falling within the domain of cryptography. In fact, cryptog-
raphy can be viewed as concerned with the design of any system that needs to withstand
malicious attempts to abuse it. Furthermore, cryptography as redefined here makes es-
sential use of some tools that need to be treated in a topic on the subject. Notable
examples include one-way functions, pseudorandom generators, and zero-knowledge
proofs. In this section we briefly discuss these terms.