Mathematics of Public Key Cryptography

Steven Galbraith

Cambridge University Press

Reviews

• Zentralblatt MATH, by Juan Tena Ayuso.

"the book gathers the main mathematical topics related to public key cryptography and provides an excellent source of information for both students and researchers interested in the field"

• MAA Reviews, by Darren Glass.

"I enjoy Galbraith's exposition, and am very happy to have a copy of this book on my shelf"

Bonus Material

Errata

• Section 5.2, page 73. Part 1 of Lemma 5.2.20: varphi_i^{-1}^* is not a k-algebra homomorphism (consider the sum of two polynomials of different total degree). Part 6 of Lemma 5.2.20: f should be homogeneous. Also proof of part 2 of Lemma 5.2.25: f should be homogeneous. (Error noticed by Parinaz Shahabi.)
• Section 7.7, page 113, Proof of Lemma 7.7.10 (second line): "\iota(P) = \iota(P) = " should just be "\iota(P) = ". (Error noticed by Parinaz Shahabi.)
• Section 8.1, page 122, Definition 8.1.6: A field F between phi^*( k( C_2 )) and k( C_1 ) with those properties does not necessarily exist if the extension is not normal. The treatment should be the other way around: k(C_1)/F purely inseparable and F/phi^*( k( C_2 )) separable. (Error noticed by Alexander Schiller.)
• Section 12.2.1, page 241, line -5: The standard definition of a Sophie Germain prime is a prime p such that 2p+1 is prime. The book defines 2p+1 to be the Sophie Germain prime, which is not standard. (Error noticed by Florian Weingarten.)
• Section 18.2, page 371, line 1: According to the definition used in the book, [7/2] = [3.5] = 4 and so the correct vector should be 4 b_1 + 2 b_2 = (10, 8, 6). But this ruins the moral of Example 18.2.4 (pages 372-373) that Babai nearest plane and Babai rounding can give different results (which is true in general, just not in this case). (Error noticed by Bart Coppens.)
• Section 25.2, page 523, line -3: It is not true that Phi_{ell}( j(E), j( tilde{E} ) = 0 implies there is an isogeny from E to tilde{E}, as the isogeny might be to a twist of tilde{E}. Correct wording would be to replace "cyclic kernel from E to tilde{E}" to "cyclic kernel from E to a twist of tilde{E}". (Error noticed by Drew Sutherland.)

Sample Chapters

NOTE: Most of these chapters are "extended versions" of chapters in the book and so have additional material. Chapter 19a is an additional chapter. Section/Theorem/Lemma/page numberings do not necessarily match those in the published version of the book.

Acknowledgements
1. Introduction

Part I: Background
2. Basic Algorithms
3. Hash Functions

Part II: Algebraic Groups
4. Preliminary remarks on Algebraic Groups
5. Varieties
6. Tori, LUC and XTR
7. Curves and Divisor Class Groups
8. Rational Maps on Curves and Divisors
9. Elliptic Curves
10. Hyperelliptic Curves

Part III: Exponentiation, Factoring and Discrete Logarithms
11. Basic Algorithms for Algebraic Groups
12. Primality Testing and Integer Factorisation using algebraic groups
13. Basic Discrete Logarithm Algorithms
14. Factoring and Discrete Logarithms Using Pseudorandom Walks
15. Factoring and Discrete Logarithms in Subexponential Time

Part IV: Lattices
16. Lattices
17. Lattice Reduction
18. Algorithms for the Closest and Shortest Vector Problem
19. Coppersmith's Method and Other Applications
19a. Cryptosystems Based on Lattices (does not appear in published version of book)

Part V: Cryptography Related to Discrete Logarithms
20. The Diffie-Hellman Problem and Cryptographic Applications
21. The Diffie-Hellman Problem
22. Digital Signatures Based on Discrete Logarithms
23. Public Key Encryption Based on Discrete Logarithms

Part VI: Cryptography Related to Integer Factorisation
24. The RSA and Rabin Cryptosystems

Part VII: Advanced Topics in Elliptic and Hyperelliptic Curves
25. Isogenies of elliptic curves
26. Pairings on elliptic curves

Appendices
A. Background Mathematics
References
Index