Excerpted and reprinted with the author's permission from SIGACT NEWS, Volume 23, Number 4 Cryptology Column -- New and Coming Books Gilles Brassard brassard@iro.umontreal.CA Departement d'informatique et de R.O. Universite de Montreal C.P. 6128, Succ. ``A'' Canada H3C 3J7 31 October 1992 Research supported in part by the E.W.R. Steacie Memorial Fellowship (Canada's Nserc). 1 Introduction An outstanding book on cryptology has hit the market this year. Although the news may be stale to many of my readers, Gustavus J. Simmons has edited a 640-page mammoth of a masterpiece titled Contemporary Cryptology: The Science of Information Integrity, published by IEEE Press. In addition, other new and exciting books are expected to come out soon. 2 Simmons' Book Simmons' Contemporary Cryptology grew out of a special issue of the Proceedings of the IEEE, which he edited in May 1988. I remember how proud -- and rightly so! -- Simmons was concerning that issue: his favourite line was that ``this is an example where the whole is better than the sum of its parts''. As a consequence of the excellent reception of his special issue, he was commissioned by the IEEE to edit the book we are now discussing. Speaking of excellent reception, the first printing of Simmons' book was sold out in months. The second printing, which I have not seen yet, corrected all mistakes that had been found in the first. In addition, reference citations for publications that had appeared after the first printing went to press were completed, and a number of footnotes, notes added in proof and inserted paragraphs to update significant statements of fact that had occurred in the interim were made. It is amusing to note that the book's cover is very similar to that of the Proceedings, except that Simmons corrected an embarrassing mistake that I pointed out to him on the Proceedings cover (see if you can spot it!). The book is hard cover, pleasant to manipulate, and handsome. Unfortunately, I found the binding of my own copy to be slightly defective, but I was told that this problem was corrected with the second printing. Contemporary Cryptology is a collection of chapters, many of which written by top researchers in the field, which together span most of the exciting developments that have changed cryptology forever in the past twenty years. Simmons himself contributed the foreword and three chapters. His master plan -- the table of contents -- is well conceived as few important topics have been left out. (Nothing is perfect, though ... the book is lacking a chapter on quantum cryptography!) Unfortunately, even a good coach cannot enforce perfect coordination concerning who says what in a multi-author work. This book is no exception: it suffers from many repetitions of the same concepts across chapters. The main sections of the book are Cryptography, Authentication, Protocols, Cryptanalysis, and Applications. This is preceded by two essays on the theme ``Contemporary Cryptology'': a foreword by Simmons and an introduction by James L. Massey. Massey's introduction to cryptology is among the clearest and most useful I have ever seen that can fit on as few as 36 pages (although another particularly noteworthy concise introduction is Simmons' own entry in the Encyclopaedia Britannica). Massey's introduction covers some history, motivations, all the basic notation, secret key cryptography (both in theory and in practice, including a review of Shannon's information theory, the DES, stream ciphers and Ueli Maurer's recent bid to get around Shannon's discouraging theorem that the one-time-pad is the most economical system that can provide perfect secrecy), authentication (a section that I found particularly useful last time I taught on the subject), public key cryptography (including one-way functions, public key distribution, RSA and variations on the theme), and protocols. Massey even includes an enlightening discussion of secret versus open research in cryptology. One thing I learned from Massey's introduction is that the notion of one-wayness goes back to at least 1873! On the negative side, nothing is said about probabilistic encryption and zero-knowledge protocols, and digital signatures are not covered adequately. But then, Massey makes an explicit point that it was not his purpose to survey research in cryptology. Moreover, these topics are treated in other chapters of Simmons' book. After the foreword and introduction, the first section deals with cryptography. The topics covered are ``The DES: Past and Future'' by Miles E. Smid and Dennis K. Branstad, ``Stream Ciphers'' by Rainer A. Rueppel, ``The First Ten Years of Public Key Cryptography'' by Whitfield Diffie, ``Public Key Cryptography'' by James Nechvatal, and ``A Comparison of Practical Public Key Cryptosystems Based on Integer Factorization and Discrete Logarithms'' by Paul C. van Oorschot. The chapter on DES goes from the birth of the system to predictions concerning the coming decade, not forgetting to cover the controversy surrounding it and its many applications. New, post-DES algorithms are also discussed. However, the coverage of attacks against DES is far from complete; in particular, differential cryptanalysis is not even mentioned. Rueppel is a leading expert in stream ciphers, and the author of a well-known book on the topic; he was therefore the natural choice of author for Simmon's second chapter. After introducing all the relevant background, Rueppel covers information-theoretic, system-theoretic and complexity-theoretic approaches to stream ciphers. A large number of pseudo-random generators are described. The chapter also considers randomized stream ciphers, which can provide practical provable security in the presence of a large, publicly accessible, body of randomness. Diffie's chapter on the history of public key cryptography is a pure gem, which could only have been told so well by the horse's mouth. In my opinion, Simmons' book would be worth buying even if only for those 39 pages. Of particular interest is the story of how Ralph Merkle, then at Berkeley, invented as early as 1974 the concept of public key distribution, and how unsuccessful he was in explaining and publishing his idea. (Merkle told me that Bob Fabry, contrary to many others, had understood the idea and had encouraged him to seek fame and fortune with it!) Diffie goes on explaining the principles of public key cryptography and the early solutions, including RSA. An interesting section on key management, the main aspect that was sorely missing from the early papers on public-key cryptography, is provided. Diffie's chapter continues with applications, such as the secure phone system, and implementations. Finally, Diffie goes beyond what his title promised, as he tackles new directions for public key cryptography. The next chapter, by Nechvatal, is by far the longest in this book (120 pages). It was written as a stand alone piece, which is unfortunate in this context as it presents significant overlap with other chapters of the book. In my opinion, the author would have been better advised to transform his writing into a monograph of its own. Nevertheless, this chapter is well written and contains a wealth of valuable information. In the last chapter of the first section, van Oorschot reviews the currently best algorithms for extracting discrete logarithms (both in GF(2^n) and in elliptic curves) and for factoring, including a detailed analysis of their efficiency. This is used as the basis of a comparison between El Gamal's cryptosystem and RSA. Elliptic curve cryptosystems are also considered. Section 2 deals with authentication. It is composed of one chapter on ``Digital Signatures'' by Chris J. Mitchell, Fred Piper and Peter Wild, and ``A Survey of Information Authentication'' by Simmons. The chapter on digital signatures provides thorough coverage of the theory, practice and applications of signatures, including a section on hashing. Nonetheless, it is sad that David Chaum's elegant notion of Undeniable Signature did not find its way in that chapter even though it was published as early as 1989. The next chapter was written by the man I consider to be no less than ``the Shannon of authentication'', the book's editor himself. Indeed, Simmons developed in the 1980's a theory of authentication that parallels that of Shannon for privacy. This chapter shows a good balance between theory and practice, which could also be said about its author. I must admit, however, that I found Massey's exposition of Simmons' theories in the Introduction easier to follow than Simmons' own. Nevertheless, I read this chapter with particular interest and enjoyment. The next section deals with protocols. It consists of an ``Overview of Interactive Proof Systems and Zero-Knowledge'' by Joan Feigenbaum and ``An introduction to Shared Secret and/or Shared Control Schemes and Their Applications'' again by Simmons. It must be pointed out that the very important (in my opinion) topic of multi-party computation, also known as ``post-cold war cryptography'', is missing altogether from this section on protocols and indeed from the entire book as far as I can tell. I like Feigenbaum's succinct exposition of interactive proofs and zero-knowledge, even though it was written more from a computational complexity point of view than from a cryptographic point of view. For instance, the existence of an interactive proof system for the permanent is of considerable interest in complexity theory, as it lead the way to Shamir's proof that IP = PSPACE (see my column in Vol. 21, no. 1, 1990) but I fail to see its direct cryptographic significance. Turning now to the chapter on secret sharing, I can think of no one better suited than Simmons for writing it. After reviewing Shamir's and Blakley's (very different) original ideas, he addresses access structures more general than simple threshold schemes. Most of the schemes explained are based upon geometric considerations. An application to key distribution is provided. A comprehensive bibliography follows. The fourth section deals with cryptography's sister discipline: cryptanalysis. It consists of one chapter on ``Cryptanalysis: A Survey of Recent Results'' by Ernest F. Brickell and Andrew M. Odlyzko, and one chapter on ``Protocol Failures in Cryptosystems'' by Judy H. Moore. The chapter on cryptanalysis surveys recent cryptanalytic achievements. Particularly thorough treatment is given to the breaking of the knapsack and of linear congruential generators. Other cryptosystems and signature schemes are covered. Information is also provided on the state-of-the-art concerning the cryptanalysis of yet unbroken systems such as RSA, discrete exponentiation schemes, the McEliece cryptosystem, and the DES. Recent developments such as the number field sieve for factoring and the differential cryptanalysis technique are mentioned, but Biham and Shamir's attack on the full 16-round DES was achieved only after Simmons' book went to press. Moore's chapter on protocol failures addresses an interesting problem: it tells you how to cheat an application centered around a cryptosystem without in fact breaking the cryptosystem itself. In other words, even good cryptosystems are potentially vulnerable when improperly used, or when used according to a badly designed protocol. Guidelines are given to avoid such traps. (Perhaps the most spectacular protocol failure in history concerned the Enigma during World War II, but this is of course not treated in Moore's chapter!) The book closes with a section on applications. It contains one chapter on ``The Smart Card: A Standardized Security Device Dedicated to Public Cryptology'' by Louis C. Guillou, Michel Ugon and Jean-Jacques Quisquater, and a chapter on ``How to Insure That Data Acquired to Verify Treaty Compliance Are Trustworthy'', once more by Simmons. The chapter on smart cards describes what a smart card is and what it can do. The important issue of standardization is treated at length. Significant information is given on the technology behind smart cards. Naturally, most of the chapter is concerned with security issues and cryptographic applications, such as authentication. The book's final chapter deals with real life field work pioneered by the editor at Sandia National Laboratories, which is the result of nearly two decades of development. I prefer to say no more so as to keep your appetite whetted! In conclusion, this is a remarkable book, which I very strongly recommend as necessary addition to the library of any serious researcher in the field of cryptology. 3 Other books These are exciting times for cryptoreaders. In addition to Simmon's, other promising books are due to appear soon. Even though I prefer to wait until they have come out to review them in detail (despite the fact that I have seen preliminary versions), I cannot resist the temptation to give you an avant gout. Eli Biham and Adi Shamir have written up in great detail their differential cryptanalysis technique and how it applies to the full 16-round DES as well as to other cryptosystems and hashing functions. This is along the lines of Volume 4, number 1 of the Journal of Cryptology, only more of it and better. The preliminary title of their book is Differential Cryptanalysis of the Data Encryption Standard. It will be published by Springer-Verlag. Starting from notes taken by the students of a class he taught at the University of California, Berkeley, Mike Luby has written Pseudorandomness and Applications, which will be published by Princeton University Press. The book, now complete in the opinion of its author, is undergoing a review process. In it, Luby places pseudorandomness at the heart of cryptography. He explains how to produce cryptographically secure pseudorandomness and how to use it for various cryptographic purposes. As one of the researchers to whom we owe the proof that one-way functions are necessary and sufficient to obtain cryptographically strong pseudorandom generators, Luby was the logical author to write this authoritative book. In addition, allow me to indulge in mentioning that my own Springer-Verlag monograph Modern Cryptology: A Tutorial is expected to come out in French this November. It will be published by Masson under the title of Cryptologie Contemporaine. Contrary to the previous translation into Italian (also published by Masson), the French version (translated by Claude Goutier) was fully revised and updated by the author. For instance, the number of references went up from 250 to 366 (you better tackle them on a leap year if you cannot handle more than one per day!). Have you written something lately? If you have, I would appreciate hearing about it.