Eran Tromer's Book Reviews 
Oded Goldreich

Foundations of Cryptography: Basic Tools

Cambridge University Press, 2001

DISCLOSURE: AT THE TIME OF WRITING, THE REVIEWER IS A GRADUATE STUDENT AT THE RESEARCH INSTITUTE WHERE THE AUTHOR HOLDS PROFESSORSHIP. THE REVIEWER  HAS TAKEN COURSES GIVEN BY THE AUTHOR IN WHICH DRAFTS OF THIS BOOK SERVED AS A TEXTBOOK, AND IS CURRENTLY A TEACHING ASSISTANT IN SUCH A COURSE.

We all know what it means for an algorithm to compute a function, but what does it mean for an encryption scheme to be secure? Traditionally, cryptographic schemes were suggested and attacked based on ad-hoc criterias, for lack of a proper theoretical setting. The last two decades have seen enormous progress in this respect. New notions were devised to harness the computational difficulty of problems in a constructive way to achieve security (in various senses) against all adversaries. This enabled the definition of a host of well-defined cryptographic "objects" and investigation of their existence and relations.

For every probabilistic polynomial-time algorithm A', every positive polynomial p( · ), and all sufficiently large n's,
  [bound on probability of finding a preimage]
(from the definition of one-way functions, p. 33)

The planned 3-volume series aims to provide a thorough presentation of the theory, written by a dominant figure in the field. This first volume introduces the basic notions: one-way functions, pseudorandom generators, various zero-knowledge proof systems and related concepts. Curiously, common cryptographic objects such as encryption schemes and signature schemes are only briefly discussed in an appendix -- the author has chosen to postpone these to the Volume 2 in the interest of in-depth discussion of the simpler objects. Hence this volume does not stand well on its own, and until Volume 2 is published the impatient reader may be disappointed. Fortunately, drafts of Volume 2 are available on-line: http://www.wisdom.weizmann.ac.il/~oded/foc-vol2.html

The presentation style is a tour de force of didactic sensitivity. The subject material is often problematic, because the mental gymnastics required are not quite like any other field. The author is fully aware of this, and provides ample intuitive discussion and motivation to help the reader through the more technical parts (without compromising rigorousness). Clearly, an effort is made to present, or at least mention and reference, all interesting results pertaining to the discussion. This makes the book invaluable as a reference, though it could have been overwhelming had not the author taken care to separate these excursions from the main discussion. The exercises are usually well-considered and rewarding, and unlike some textbooks you won't find important results disguised as an optional exercise. The discussion uses standard notions from computer science, as well as basic results in probability and number theory — these are reviewed at some length, but prior familiarity can be helpful.

Those interested primarily in practical applications of cryptography may well find this book too abstract and irrelevant, as the relation between this book and Bruce Schneier's Applied Cryptography is roughly like that between organic chemistry and cooking. However, for those taking academic interest in the field or trying to devise novel cryptographic schemes, this book is an effective way to get a solid grasp on the theory, and a delightful way to understand this exciting branch of computer science.

[Home] 
© 2001 Eran Tromer.    Feedback to