Cases for the cipher sleuths

Security is a hot topic these days, not least the security of electronic data and computer systems. Much effort in academia, government and industry is spent on developing systems that satisfy our ever-increasing demands for service and functionality while also achieving security in the face of ever more sophisticated adversaries.

The ancient art of cryptography (literally, "secret writing") has a significant role to play in the development of such systems.

Historically, cryptography was concerned solely with the problem of privacy (sending secret messages). Since the 1970s, the subject has grown to include data integrity and authenticity as well as entity authentication.

Cryptology is now an extremely active interdisciplinary academic subject with strands in mathematics, computer science and electrical engineering.

Quite apart from real-world applications, the subject has advantages in an educational context, namely that students find it attractive. Hence, cryptography is often used as a means of teaching moderately advanced mathematics to undergraduates by stealth. For these reasons, cryptography courses are widely offered in academic departments, and there is a solid market for the various books in the area.

The two under review here are written by mathematicians and, although they are accessible to computer science and engineering students, their contents reflect a relatively mathematical view of the subject. Happily, both books present not only the constructive applications of mathematics in cryptography, but also the destructive ones (better known as cryptanalysis). Cryptanalysis is not only an important part of the subject, it is also where some of the more interesting mathematics appears.

As reflected in the title, the text by John Talbot and Dominic Welsh covers not just cryptography but also the theory of computational complexity. Cryptography is used as motivation, illustration and application of the concepts of complexity.

The book is beautifully structured and elegantly written in a compact yet accessible style. It is based on a course taught by the authors and has numerous problems, many provided with hints and/or solutions. For these reasons, it is ideally suited for an advanced undergraduate or postgraduate course.

The book gives precise definitions of Turing machines and complexity classes such as P, NP, PSPACE and so on. Cook's theorem is proved and some less common topics, such as circuit complexity, are presented. Excellent motivation is given for why an understanding of complexity is a crucial prerequisite for the study of cryptography. The discussion of cryptography is skewed to mathematical topics, such as primality testing, linear feedback shift registers, public key cryptography, birthday attacks, secret sharing and so on. In all cases, the mathematics is precise and rigorous.

As stated in the preface, the book is not a comprehensive text, and it does not provide a complete foundation for study in cryptography.

Douglas Stinson's book, now in its third edition, is one of the canonical texts in the subject. It is concerned purely with cryptography and presents an incredibly wide range of topics. Indeed, a student with a good understanding of its contents would be able to read much of the research literature in cryptography and would be very well prepared for PhD study. Even so, there are a few notable omissions, such as triple DES and any real-world stream ciphers.

Unlike Talbot and Welsh, Stinson assumes some familiarity with algorithms and complexity. On the other hand, he demands fewer mathematical prerequisites and introduces the necessary mathematics "on the fly". For these reasons, his book may be more suitable for computer science and engineering students.

The third edition differs from its predecessor mainly in that it contains seven new chapters covering advanced topics such as pseudorandom generation, key distribution/agreement, public key infrastructures and secret sharing schemes.

I use Stinson's book as a supplementary text for an advanced course in cryptography at Royal Holloway, University of London. The chapters are relatively independent so there is no need to follow the book linearly. Indeed, it covers many topics of minor interest and importance so, unlike the text of Talbot and Welsh, it is not recommended for use as a course blueprint.

To summarise, the Talbot and Welsh book is self-contained and particularly suitable for a mathematics course, while Stinson's text is more appropriate for computer science students or beginning researchers in cryptography. Certainly, both books are excellent tools for teaching some interesting and advanced mathematics by stealth.

Steven Galbraith is reader in pure mathematics, Royal Holloway, University of London.