An Introduction to Mathematical Cryptography (2nd ed.)

Description

This self-contained introduction to modern cryptography emphasizes the mathematics behind the theory of public key cryptosystems and digital signature schemes. The book focuses on these key topics while developing the mathematical tools needed for the construction and security analysis of diverse cryptosystems. Only basic linear algebra is required of the reader; techniques from algebra, number theory, and probability are introduced and developed as required. This text provides an ideal introduction for mathematics and computer science students to the mathematical foundations of modern cryptography. The book includes an extensive bibliography and index; supplementary materials are available online.

The book covers a variety of topics that are considered central to mathematical cryptography. Key topics include:

• classical cryptographic constructions, such as Diffie– Hellmann key exchange, discrete logarithm-based cryptosystems, the RSA cryptosystem, and digital signatures;

• fundamental mathematical tools for cryptography, including primality testing, factorization algorithms, probability theory, information theory, and collision algorithms;

• an in-depth treatment of important cryptographic innovations, such as elliptic curves, elliptic curve and pairing-based cryptography, lattices, lattice-based cryptography, and the NTRU cryptosystem.

The second edition of An Introduction

to Mathematical Cryptography includes a significant revision of the material on digital signatures, including an earlier introduction to RSA, Elgamal, and DSA signatures, and new material on lattice-based signatures and rejection sampling. Many sections have been rewritten or expanded for clarity, especially in the chapters on information theory, elliptic curves, and lattices, and the chapter of additional topics has been expanded to include sections on digital cash and homomorphic encryption. Numerous new exercises have been included.

MR2433856

When did cryptography, the creation of codes and ciphers, become part of mathematics? Two time periods—one near the beginning of the twentieth century and one near the end—come to mind. In 1929 L. S. Hill, a thirty-eight-year-old assistant professor of mathematics at Hunter College, published a short paper [Amer. Math. Monthly 36 (1929), no. 6, 306–312; MR1521759] that solved the problem of trigraphic substitution. (Hill extended those ideas in an address to the American Mathematical Society at a meeting in August, 1929, in Boulder, Colorado [Amer. Math. Monthly 38 (1931), no. 3, 135–154; MR1522201; JFM 57.0120.01].)
"Ever since [1854] Wheatstone's Playfair [cipher] showed how a digraphic substitution [substitution for two-letter strings] could be achieved compactly and without a lengthy list, other cryptographers … tried to extend his geometrical techniques to trigraphic substitutions. Nearly all … failed'' [D. Kahn, The codebreakers: the story of secret writing, Scribner's, New York, 1996 (p. 404)].
By the time of Hill's paper, mathematicians had already extended arithmetic from operations on individual numbers to sequences of numbers by the techniques of matrix algebra. Hill applied the same techniques to cryptography. (In 1772, F. J. Buck published similar ideas [see D. Kahn, op. cit. (p. 405); F. L. Bauer, Decrypted secrets, Fourth, revised and extended edition, Springer, Berlin, 2007; MR2274689 (p. 86)], and in 1926, nineteen-year-old Jack Levine (in a column in the detective magazine Flynn's Weekly) suggested using systems of linear equations to encrypt digraphs.) Hill extended substitution from simple substitution (substitution for a letter of another letter or symbol) to substitution for a string of n letters by using matrix techniques.
"Hill's ideas were taken up in 1941 by A. A. Albert in a wave of both patriotic and mathematical enthusiasm, in particular at a meeting of the American Mathematical Society'' [F. L. Bauer, op. cit. (p. 86)].
"We shall present here a mathematical formulation of a general theory of cryptology with detailed application to cryptography. In this we shall see that cryptography is more than a subject permitting mathematical formulation, for indeed it would not be an exaggeration to state that abstract cryptography is identical with abstract mathematics'' [A. A. Albert, "Some mathematical aspects of cryptography'', in Collected mathematical papers. Part 2, Edited by Richard E. Block, Nathan Jacobson, J. Marshall Osborn, David J. Saltman and Daniel Zelinsky, Amer. Math. Soc., Providence, RI, 1993; MR1213452 (p. 903)].
Although Albert's equating of abstract cryptography and abstract mathematics seems extreme, in his address to the American Mathematical Society Albert pointed out that cryptography can be thought of as a theory of nonsingular mappings, and he expressed many classical ciphers in those terms.
During World War II mathematicians and mathematics played an important role in cryptology.
"By [the time of Albert's address to the AMS], Hill's ideas had already had their impact on W. F. Friedman in the USA and on Werner Kunz in the German Auswärtiges Amt. The importance of Hill's [cipher] stems from the fact that since then the value of mathematical methods in cryptology has been unchallenged. Consequently, in the early 1930s mathematicians entered the cipher bureaus …'' [F. L. Bauer, op. cit. (pp. 86–87)].
Then, in 1976, another paper cemented the ties between cryptography and mathematics—the paper "New directions in cryptography'' [IEEE Trans. Information Theory IT-22 (1976), no. 6, 644–654; MR0437208] by W. Diffie and M. E. Hellman that introduced the idea of public key cryptography. Public key cryptography encrypts using mathematical functions that are trapdoor functions—functions that are one-way but reversible by a person who has some private information.
It is the public key aspect of mathematical cryptography that is the focus of the book under review.
We should begin by saying that this is an excellent book. The exposition is outstanding. But we should note that this book is published as an undergraduate cryptography text, and we question whether this book would be a good choice for such a course.
One problem with writing a text for an undergraduate cryptography course is that, unlike calculus, there is no standard cryptography course. Cryptology (cryptology consists of two areas: cryptography and cryptanalysis; cryptography studies the construction of codes and ciphers while cryptanalysis studies the "breaking'' of codes and ciphers) is a blend of disciplines, and authors tend to focus on their particular interest. In this case, Hoffstein, Pipher and Silverman have chosen to focus on public key cryptography. (A better title for their book would probably be An introduction to the mathematical aspects of public key cryptography.) They very narrowly focus on Diffie-Hellman key exchange, ElGamal, RSA, ECC and NTRU and the mathematical aspects of those algorithms. (In Diffie-Hellman key exchange, the usual cryptographic characters, Alice and Bob, exchange a key by selecting a field Z p for a large prime p and a nonzero g. Alice and Bob each select an exponent: a for Alice and b for Bob. Alice sends Bob A =g a mod p , and Bob sends Alice B =g b mod p. They now share the secret g a b mod p , which can be used as a key. The security of the key exchange is based upon the interloper Eve not being able to solve for the exponents [W. Diffie and M. E. Hellman, op. cit.]. ElGamal is the 1985 encryption algorithm by T. ElGamal [IEEE Trans. Inform. Theory 31 (1985), no. 4, 469–472; MR0798552] that is similar to Diffie-Hellman key exchange. RSA is the 1978 encryption algorithm by Rivest, Shamir and Adleman the security of which is based upon not being able to factor integers that are the products of two large primes [R. L. Rivest, A. Shamir and L. Adleman, Comm. ACM 21 (1978), no. 2, 120–126; MR0700103; M. Gardner, "A new kind of cipher that would take millions of years to break'', Sci. Amer. 237 (1977), no. 2, 120–124; per revr., available at www.fortunecity.com/emachines/e11/86/cipher1.html]. ECC [elliptic curve cryptography] is essentially the ElGamal algorithm done over the points of an elliptic curve rather than Z p [N. I. Koblitz, Math. Comp. 48 (1987), no. 177, 203–209; MR0866109; V. S. Miller, in Advances in cryptology—CRYPTO '85 (Santa Barbara, Calif., 1985), 417–426, Lecture Notes in Comput. Sci., 218, Springer, Berlin, 1986; MR0851432]. Hoffstein, Pipher and Silverman are the developers of the lattice-based cryptosystem NTRU [in Algorithmic number theory (Portland, OR, 1998), 267–288, Lecture Notes in Comput. Sci., 1423, Springer, Berlin, 1998; MR1726077].)
The discussion by Hoffstein, Pipher and Silverman of the cryptographic and mathematical aspects of these algorithms is excellent. Not only do they write in a precise, correct, and interesting way, but they write in a way that gives their readers a correct "feeling'' for the cryptography. The latter is often missing from books that deal seriously with the mathematical aspects of cryptography.
What is mostly missing from this book is classical cryptography, cryptanalysis, modern symmetric key block ciphers, modern cryptanalysis of the symmetric key block ciphers (techniques of modern cryptanalysis such as differential cryptanalysis [E. Biham and A. Shamir, in Advances in cryptology—CRYPTO '90, 2–21, Lecture Notes in Comput. Sci., 537, Springer, Berlin, 1991; Zbl 0787.94014; see also J. Cryptology 4 (1991), no. 1, 3–72; MR1202786], linear cryptanalysis [M. Matsui, in Advances in cryptology—EUROCRYPT '93, 386–397, Lecture Notes in Comput. Sci., 765, Springer, Berlin, 1994; Zbl 0951.94519] and algebraic cryptanalysis [M. Albrecht, Cryptologia 32 (2008), no. 3, 220–276] also involve interesting mathematics), and post-quantum cryptography.
Post-quantum cryptography focuses on four types of cryptographic systems that may be able to resist attacks by quantum computers: hash-based cryptography, code-based cryptography, lattice-based cryptography, and multivariate public key cryptography [J. Ding, J. E. Gower and D. S. Schmidt, Multivariate public key cryptosystems, Springer, New York, 2006; MR2244659]. NTRU is an example of lattice-based cryptography. Like public key cryptography, post-quantum cryptography uses interesting mathematics in interesting ways. Post-quantum cryptography. First International Workshop PQCrypto 2006 [Springer, Berlin, 2009; Zbl 1155.81007] is a good introduction to post-quantum cryptography.
The authors give a bit of an apology for the missing topics by including a last chapter that provides two- or three-page discussions of each of ten topics that they were not able to discuss in detail. Again, their exposition of these additional topics is excellent, but much could be said on each.
Because this is a textbook, several other things should be mentioned.
First, what should the prerequisite be for a course based upon this book? According to the authors: "The formal prerequisites are few, beyond a facility with high school algebra and … analytic geometry. Elementary calculus is used here and there in a minor way, but it is not essential, and linear algebra is used in a small way …. No previous knowledge is assumed for mathematical topics such as number theory, abstract algebra, and probability theory that play a fundamental role in modern cryptography'' (p. xiii). Such claims seem never to be true, and they are not really true for this book either. (The reader will find, for example, twenty pages about Weil pairings in Chapter 5, and there is still a third of the book after that.) But the authors have done very well with their exposition; this book comes as close to satisfying that claim as is probably possible. (The authors' claim that this would be a good choice for a text for an introduction-to-proofs course should be regarded as hype.) An interested reader with such a background could get a lot out of this book. But, in fact, the reader who would benefit most from this book is a person who has a background in number theory, abstract algebra, and probability theory and wants to see from a cryptographic viewpoint how these areas are used in public key cryptography. Readers without such a background are likely to miss much of the careful exposition. This book would not be a very good choice for an engineer or computer scientist who does not have the mathematical background.
The book contains eight chapters: An introduction to cryptography (pp. 1–58); Discrete logarithms and Diffie-Hellman (pp. 59–112); Integer factorization and RSA (pp. 113–187); Combinatorics, probability, and information theory (pp. 189–277); Elliptic curves and cryptography (pp. 279–348); Lattices and cryptography (pp. 349–435); Digital signatures (pp. 437–463); and Additional topics in cryptography (pp. 465–487).
The last chapter has no exercises and the seventh has 20. The other chapters each have more than 40 exercises. The exercises are well designed and interesting. They are also often challenging; assigning more than a few exercises from each chapter would probably overtax the typical undergraduate cryptology student. The exercises and text would make an excellent course for undergraduate independent study.
The authors include a comprehensive list of 137 references that are appropriately mentioned in the text.
This is an excellent book. Hoffstein, Pipher and Silverman have written as good a book as is possible to explain public key cryptography. Other books typically get the mathematics correct or the cryptography correct, but not both. Both the mathematics and the cryptography "feel'' correct in this book. Unfortunately the narrow focus of the book makes this not a good choice for a first undergraduate cryptography course. This book would probably be best suited for a graduate course that focused on public key cryptography, for undergraduate independent study, or for the mathematician who wants to see how mathematics is used in public key cryptography. Reviewed by Jintai Ding and Chris Christensen

MR3289167

The book under review is the second edition to [J. Hoffstein, J. C. Pipher and J. H. Silverman, An introduction to mathematical cryptography, Undergrad. Texts Math., Springer, New York, 2008; MR2433856].
The chapters in the second edition are as follows: Chapter 1. An Introduction to Cryptography; Chapter 2. Discrete Logarithms and Diffie-Hellman; Chapter 3. Integer Factorization and RSA; Chapter 4. Digital Signatures; Chapter 5. Combinatorics, Probability, and Information Theory; Chapter 6. Elliptic Curves and Cryptography; Chapter 7. Lattices and Cryptography; Chapter 8. Additional Topics in Cryptography. The authors note five changes in the second edition, namely that the chapter on digital signatures has been moved, numerous exercises have been included, numerous typographical and minor mathematical errors have been corrected and notation has been made consistent from chapter to chapter, various explanations have been rewritten or expanded for clarity (especially in Chapters 5–7), and new sections on digital cash/bitcoin (section 8.8) and on homomorphic encryption (section 8.9) have been added to the additional topics in Chapter 8.
On first count (with respect to the disclaimer that there are three kinds of mathematicians—those that can count and those that cannot), there appear to be about 26 (out of 313) new exercises (2.50, 3.41, 3.43, 1.11, 7.60, 5.49, and 5.59 in Chapters 1, 2, 3, 4, 5, 6, and 7, respectively), as compared to the exercises in the first edition. Notably some exercises from the first edition appear to be solved within the book under review (e.g. Exercise 7.11 in the first edition appears to be solved in section 6.4.3 on page 321 of the second edition under review). A selection of these new exercises is presented below.

∙

Chapter 1, 1.14: Let a and b be integers with b >0. We've been using the "obvious fact" that a divided by b has a unique quotient and remainder. In this exercise you will give a proof.

∙

Chapter 2, 2.31: Let R and S be rings. A function ϕ :R → S is called a ring homomorphism if it satisfies ϕ(a +b)=ϕ(a)+ϕ(b) and ϕ(a ∗ a)=ϕ(a)∗ ϕ(a), for all real numbers a ,b. (a) Prove that ϕ(0 R)=0 S , ϕ(1 R)=1 S , ϕ(− a)=− ϕ(a), and ϕ(a −1)=ϕ(a)−1 for all a in R that have a multiplicative inverse. (b) Let p be a prime, and let R be a ring with the property that p a =0 for every a in R. Prove that the (Frobenius) map ϕ :R → R , ϕ(a)=a p , is a ring homomorphism.

∙

Chapter 3, 3.41(a): Let a and b be cubic residues modulo p. Prove that a b is a cubic residue modulo p.

∙

Chapter 4, 4.4: Suppose that Alice and Bob communicate using the RSA PKC. Explain why verification works, and why it would be difficult for anyone other than Alice to send Bob a validly signed message.

∙

Chapter 5, 5.44(f): Explain what happens if you run Pollard's ρ algorithm with f(x)=x 2 and any initial values for x 0.

∙

Chapter 6, 6.49(b): Suppose that Eve knows how to solve the elliptic curve Diffie-Helman problem in E(F q), as described on page 318. Show that she can decrypt all ciphertexts.

∙

Chapter 7, 7.54: We proved that the LLL algorithm terminates and has polynomial running time under the assumption that L is a subset of Z n ; see Theorem 7.71. Show that this assumption is not necessary by proving that LLL terminates in polynomial time for any lattice L contained in R n.

There also appear to be 13 new references accounting for some of the development in cryptology spanning the years since the publication of the first edition. In particular, note the references on bitcoin [S. Nakamoto, "Bitcoin: a peer-to-peer electronic cash system'', 2009], which may revolutionize internet commerce, and homomorphic encryption [C. Gentry, A fully homomorphic encryption scheme, Ph.D. thesis, Stanford Univ., 2009], which solves a central open problem (posed by Rivest et al. in 1978) in cryptology.
Besides including more detail (and numerous exercises) on homomorphic encryption in Chapter 8, it may have been of interest to undergraduate students to include a section (and numerous exercises) in Chapter 1 (following the section on "cryptography before the computer age'' when Polish cryptographers are mentioned) on Marian Rejewski [Wiadom. Mat. (2) 23 (1980), no. 1, i–ii (1 plate); MR0615716], and the mathematics of cryptology underlying Rejewski's Method [J. Lawrence, Cryptologia 28 (2004), no. 2, 149–152, doi:10.1080/0161-110491892836; Cryptologia 29 (2005), no. 3, 233–247, doi:10.1080/01611190508951300]. Reviewed by Robert Juricevic