Cryptography is concerned with the construction of schemes that should be able to withstand any abuse. Such schemes are constructed so as to maintain a desired functionality, even under malicious attempts aimed at making them deviate from their prescribed functionality.

The design of cryptographic schemes is a very difficult task. One cannot rely on intuitions regarding the typical state of the environment in which a system will operate. For sure, an adversary attacking the system will try to manipulate the environment into untypical states. Nor can one be content with countermeasures designed to withstand specific attacks, because the adversary (who will act after the design of the system has been completed) will try to attack the schemes in ways that typically will be different from the ones the designer envisioned. Although the validity of the foregoing assertions seems self-evident, still some people hope that, in practice, ignoring these tautologies will not result in actual damage. Experience shows that such hopes are rarely met; cryptographic schemes based on make-believe are broken, typically sooner rather than later.

In view of the foregoing, we believe that it makes little sense to make assumptions regarding the specific strategy that an adversary may use. The only assumptions that can be justified refer to the computational abilities of the adversary.

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 book (Section 1.3). Likewise, this chapter contains a section presenting some elementary background from probability theory that is used extensively in the book (Section 1.2).

Finally, we motivate the rigorous approach employed throughout this book 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.

Cryptography: Main Topics

Historically, the term “cryptography” has been associated with the problem of designing and analyzing encryption schemes (i.e., schemes that provide secret communication 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, cryptography can be viewed as concerned with the design of any system that needs to withstand malicious attempts to abuse it.

In this chapter we discuss pseudorandom generators. Loosely speaking, these are efficient deterministic programs that expand short, randomly selected seeds into much longer “pseudorandom” bit sequences (see illustration in Figure 3.1). Pseudorandom sequences are defined as computationally indistinguishable from truly random sequences by efficient algorithms. Hence the notion of computational indistinguishability (i.e., indistinguishability by efficient procedures) plays a pivotal role in our discussion. Furthermore, the notion of computational indistinguishability plays a key role also in subsequent chapters, in particular in the discussions of secure encryption, zero-knowledge proofs, and cryptographic protocols.

The theory of pseudorandomness is also applied to functions, resulting in the notion of pseudorandom functions, which is a useful tool for many cryptographic applications.

In addition to definitions of pseudorandom distributions, pseudorandom generators, and pseudorandom functions, this chapter contains constructions of pseudorandom generators (and pseudorandom functions) based on various types of one-way functions. In particular, very simple and efficient pseudorandom generators are constructed based on the existence of one-way permutations. We highlight the hybrid technique, which plays a central role in many of the proofs. (For the first use and further discussion of this technique, see Section 3.2.3.)

Organization. Basic discussions, definitions, and constructions of pseudorandom generators appear in Sections 3.1–3.4: We start with a motivating discussion (Section 3.1), proceed with a general definition of computational indistinguishability (Section 3.2) next present and discuss definitions of pseudorandom generators (Section 3.3), and finally present some simple constructions (Section 3.4). More general constructions are discussed in Section 3.5.

We introduce the three main characters in public key cryptography. As in many books on the subject, it is assumed that Alice and Bob wish to perform some form of communication whilst Eve is an eavesdropper who wishes to spy on (or tamper with) the communications between Alice and Bob. Of course there is no assumption that Alice and Bob (or Eve) are actually human. They may (and probably will) be computers on some network such as the Internet.

Modern cryptography, as applied in the commercial world, is concerned with a number of problems. The most important of these are:

1. Confidentiality: A message sent from Alice to Bob cannot be read by anyone else.

2. Authenticity: Bob knows that only Alice could have sent the message he has just received.

3. Integrity: Bob knows that the message from Alice has not been tampered with in transit.

4. Non-repudiation: It is impossible for Alice to turn around later and say she did not send the message.

To see why all four properties are important consider the following scenario. Alice wishes to buy some item over the Internet from Bob. She sends her instruction to Bob which contains her credit card number and payment details. She requires that this communication be confidential, since she wants other people to know neither her credit card details nor what she is buying.

Much attention has recently been focused on the use of elliptic curves in public key cryptography, first proposed in the work of Koblitz [62] and Miller [103]. The motivation for this is the fact that there is no known sub-exponential algorithm to solve the discrete logarithm problem on a general elliptic curve. In addition, as will be discussed in Chapter I, the standard protocols in cryptography which make use of the discrete logarithm problem in finite fields, such as Diffie–Hellman key exchange, ElGamal encryption and digital signature, Massey–Omura encryption and the Digital Signature Algorithm (DSA), all have analogues in the elliptic curve case.

Cryptosystems based on elliptic curves are an exciting technology because for the same level of security as systems such as RS A [134], using the current knowledge of algorithms in the two cases, they offer the benefits of smaller key sizes and hence of smaller memory and processor requirements. This makes them ideal for use in smart cards and other environments where resources such as storage, time, or power are at a premium.

Some researchers have expressed concern that the basic problem on which elliptic curve systems are based has not been looked at in as much detail as, say, the factoring problem, on which systems such as RSA are based.