Excerpted and reprinted with the author's permission
from SIGACT NEWS, Volume 23, Number 4
Cryptology Column -- New and Coming Books
Gilles Brassard
brassard(a)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.
