main-content

The first part of this book covers the key concepts of cryptography on an undergraduate level, from encryption and digital signatures to cryptographic protocols. Essential techniques are demonstrated in protocols for key exchange, user identification, electronic elections and digital cash. In the second part, more advanced topics are addressed, such as the bit security of one-way functions and computationally perfect pseudorandom bit generators. The security of cryptographic schemes is a central topic. Typical examples of provably secure encryption and signature schemes and their security proofs are given. Though particular attention is given to the mathematical foundations, no special background in mathematics is presumed. The necessary algebra, number theory and probability theory are included in the appendix. Each chapter closes with a collection of exercises.

In the second edition the authors added a complete description of the AES, an extended section on cryptographic hash functions, and new sections on random oracle proofs and public-key encryption schemes that are provably secure against adaptively-chosen-ciphertext attacks. The third edition is a further substantive extension, with new topics added, including: elliptic curve cryptography; Paillier encryption; quantum cryptography; the new SHA-3 standard for cryptographic hash functions; a considerably extended section on electronic elections and Internet voting; mix nets; and zero-knowledge proofs of shuffles.

The book is appropriate for undergraduate and graduate students in computer science, mathematics, and engineering.

1. Introduction

Abstract
Cryptography is the science of keeping secrets secret. Assume a sender, referred to here and in what follows as Alice (as is commonly used), wants to send a message m to a receiver, referred to as Bob. She uses an insecure communication channel. For example, the channel could be a computer network or a telephone line. There is a problem if the message contains confidential information. The message could be intercepted and read by an eavesdropper. Or, even worse, the adversary, as usual referred to here as Eve, might be able to modify the message during transmission in such a way that the legitimate recipient Bob does not detect the manipulation.
Hans Delfs, Helmut Knebl

2. Symmetric-Key Cryptography

Abstract
In this chapter, we give an introduction to basic methods of symmetric-key cryptography. At first, we consider symmetric-key encryption.We explain the notions of stream and block ciphers. The operation modes of block ciphers are studied and, as prominent examples for block ciphers, DES and AES are described. Later, we introduce cryptographic hash functions. Methods for the construction of cryptographic hash functions, such as Merkle–Damg˚ard’s method and the sponge construction, are explained in detail. As an application of hash functions, we get message authentication codes, MACs for short. MACs are the standard symmetric-key technique to guarantee the integrity and authenticity of messages.
Hans Delfs, Helmut Knebl

3. Public-Key Cryptography

Abstract
The basic idea of public-key cryptography are public keys. Each person’s key is separated into two parts: a public key for encryption available to everyone and a secret key for decryption which is kept secret by the owner. In this chapter we introduce the concept of public-key cryptography. Then we discuss some of the most important examples of public-key cryptosystems, such as the RSA, ElGamal and Rabin cryptosystems. These all provide encryption and digital signatures.
Hans Delfs, Helmut Knebl

4. Cryptographic Protocols

Abstract
One of the major contributions of modern cryptography is the development of advanced protocols providing high-level cryptographic services, such as secure user identification, voting schemes and digital cash. Cryptographic protocols use cryptographic mechanisms – such as encryption algorithms and digital signature schemes – as basic components.
Hans Delfs, Helmut Knebl

5. Probabilistic Algorithms

Abstract
Probabilistic algorithms are important in cryptography. On the one hand, the algorithms used in encryption and digital signature schemes often include random choices (as in Vernam’s one-time pad or the DSA) and therefore are probabilistic. On the other hand, when studying the security of cryptographic schemes, adversaries are usually modeled as probabilistic algorithms. The subsequent chapters, which deal with provable security properties, require a thorough understanding of this notion. Therefore, we clarify what is meant precisely by a probabilistic algorithm, and discuss the underlying probabilistic model.
Hans Delfs, Helmut Knebl

6. One-Way Functions and the Basic Assumptions

Abstract
In Chapter 3 we introduced the notion of one-way functions. As the examples of RSA encryption and Rabin signatures show, one-way functions play the key role in asymmetric cryptography.
Hans Delfs, Helmut Knebl

7. Bit Security of One-Way Functions

Abstract
Let $$f:X\rightarrow Y$$ be a bijective one-way function and let $$x\in X$$. Sometimes it is possible to compute some bits of x from $$f(x)$$ without inverting f. A function f does not necessarily hide everything about x, even if f is one way. Let b be a bit of x. We call b a secure bit of f if it is as difficult to compute b from $$f(x)$$ as it is to compute x from $$f(x)$$. We prove that the most-significant bit of x is a secure bit of Exp, and that the least-significant bit is a secure bit of RSA and Square.
Hans Delfs, Helmut Knebl

8. One-Way Functions and Pseudorandomness

Abstract
There is a close relationship between encryption and randomness. The security of encryption algorithms usually depends on the random choice of keys and bit sequences. A famous example is Shannon’s result. Ciphers with perfect secrecy require randomly chosen key strings that are of the same length as the encrypted message. In Chapter 9, we will study the classical Shannon approach to provable security, together with more recent notions of security. One main problem is that truly random bit sequences of sufficient length are not available in most practical situations. Therefore, one works with pseudorandom bit sequences. They appear to be random, but actually they are generated by an algorithm.
Hans Delfs, Helmut Knebl

9. Provably Secure Encryption

Abstract
This chapter deals with provable security. It is desirable that mathematical proofs show that a given cryptosystem resists certain types of attacks. The security of cryptographic schemes and randomness are closely related. An encryption method provides secrecy only if the ciphertexts appear sufficiently random to the adversary. Therefore, probabilistic encryption algorithms are required. The pioneering work of Shannon on provable security, based on his information theory, is discussed in Section 9.1. For example, we prove that Vernam’s one-time pad is a perfectly secret encryption. Shannon’s notion of perfect secrecy may be interpreted in terms of probabilistic attacking algorithms that try to distinguish between two candidate plaintexts (Section 9.2).
Hans Delfs, Helmut Knebl

10. Unconditional Security of Cryptosystems

Abstract
The security of many currently used cryptosystems, in particular that of all public-key cryptosystems, is based on the hardness of an underlying computational problem, such as factoring integers or computing discrete logarithms. Security proofs for these systems show that the ability of an adversary to perform a successful attack contradicts the assumed difficulty of the computational problem. Security proofs of this type were presented in Chapter 9. For example, we proved that public-key one-time pads induced by one-way permutations with a hard-core predicate are ciphertext-indistinguishable. The security of the encryption scheme is reduced to the one-way feature of function families, such as the RSA or modular squaring families, and the one-way feature of these families is, in turn, based on the assumed hardness of inverting modular exponentiation or factoring a large integer (see Chapter 6). The security proof is conditional, and there is some risk that in the future, the underlying condition will turn out to be false.
Hans Delfs, Helmut Knebl

11. Provably Secure Digital Signatures

Abstract
In previous sections, we discussed signature schemes (Full-Domain-Hash RSA signatures and PSS in Section 3.3.5; the Fiat–Shamir signature scheme in Section 4.2.5) that include a hash function h and whose security can be proven in the random oracle model. It is assumed that the hash function h is a random oracle, i.e., it behaves like a perfectly random function (see Sections 2.2.4 and 3.3.5).
Hans Delfs, Helmut Knebl