You are here

Complexity and Cryptography: An Introduction

John Talbot and Dominic Welsh
Cambridge University Press
Publication Date: 
Number of Pages: 
[Reviewed by
Darren Glass
, on

There are many aspects of cryptography that mathematicians are extremely well positioned to study — branches of mathematics from number theory to group theory to knot theory are moving further and further into the center of the design of (and the attacks on) cryptosystems.  But most mathematicians I know — and I count myself at the front of this group — are not particularly well-versed in the study of algorithms.  A month ago I could have bluffed my way through a description of P-vs-NP, but despite a deep interest in cryptography my knowledge ended there. 

John Talbot and Dominic Welsh have written a book that has changed all that, and that will be quite useful to mathematicians wishing to learn some complexity theory.   Their book, Complexity and Cryptography: An Introduction, opens with a very brief chapter introducing some of the ideas of modern cryptography and then quickly jumps into a lengthy discussion of complexity.  They start from scratch and develop the ideas of deterministic Turing machines, complexity of functions, non-deterministic Turing machines, NP-completeness, probabilistic Turing machines, and many others.  Their exposition is very clear, and they give a large number of examples throughout this discussion that made the book very readable even to those of us whose interests tend far more towards the theoretical than the algorithmic. 

The second half of the book is a tour through the major ideas of cryptography, starting with symmetric cryptosystems and one-way functions and including public key cryptosystems such as RSA and Elgamal.  They also discuss signature schemes and key agreement protocols, concluding with discussions of pseudorandom generators and zero-knowledge proofs.  Throughout the book the authors emphasize the algorithmic side of the story and they work out many explicit examples.  There are also a large number of exercises, many of which have hints or full-blown solutions worked out in an appendix.  Other appendices give crash courses in graph theory, number theory, algebra, and probability theory.  These serve as a good reference, but I cannot imagine a reader getting enough out of them to follow the book if they have not already been introduced to these topics.

In addition to being a good reference for mathematicians wishing to learn about the way that our computer scientist colleagues approach the field of cryptography, Talbot and Welsh have written a book that could easily be used in an undergraduate course (albeit one more computer science-y than some of us may choose to teach).  The book does not cover as much depth or breadth as many other introductions to cryptography (such as the books by Stinson, Schreier, Goldreich, et al), but its brevity and clarity make it much easier to jump into.  Furthermore, the authors conclude every chapter with a section of 'Further Notes', many of which have references to other articles or books that found me running to the library.

Talbot and Welsh have written a niche book, but it is a very well-written book that fills its niche quite well, and it will make a welcome addition to any collection.

Darren Glass is an assistant professor at Gettysburg College whose mathematical interests include number theory, Galois theory, and cryptography.  He can be reached at

 1. Basics of cryptography; 2. Complexity theory; 3. Non-deterministic computation; 4. Probabilistic computation; 5. Symmetric cryptosystems; 6. One-way functions; 7. Public key cryptography; 8. Digital signatures; 9. Key establishment protocols; 10. Secure encryption; 11. Identification schemes; Appendix 1; Appendix 2; Appendix 3; Appendix 4; Appendix 5; Appendix 6; Bibliography; Index.