Secure multiparty computation can be illustrated by the following example: Ten honest, but suspicious, university presidents wish to know their average (that is, mean) salary, but without revealing their salaries to each other. This is trivially solved if there is a trusted third party to whom they tell their secret salaries, and this third party computes the mean and tells them all. If we want security against an eavesdropper, we need cryptography, and if we have to deal with an aggressive attacker, who may attempt to forge messages, we may need more cryptography; nevertheless, the actual computation is still trivial.

Two major players in this field have edited this book on the subject, including some of their own papers and some from a number of other contributors. There are two introductory chapters by Oded Goldreich, a third by Ran Canetti, and then five more detailed chapters. Unfortunately, the content is grouped into two parts, each divided into relatively numbered sections, so a reference to “section 2,” for example, is actually ambiguous.

The book is intended to consider questions such as whether we can emulate the mean salary calculation, while retaining the secrecy of the individual salaries, in the absence of the third party. Clearly, we cannot do this if N=2, since if I know my salary and the average, I know yours. But this is true whether we use a protocol from this book or a trusted third party, and one of the themes of this book is that asking for “a protocol [that is] as good as having a trusted third party” is a suitable way of framing our security and privacy needs. A common claim (such as is made at the bottom of page 87, and in precise statements in the last chapter) is that this is possible even if some (less than one-third) of the parties are corrupt, or if less than one-half are “honest but curious,” that is, they follow the protocol but want to know each others’ salaries. As far as I can tell, this book addresses the case where the function is defined by an arithmetic circuit (such as computing the mean).

This area of cryptography is particularly prone to the following problem: Proving that P is a secure protocol and that Q is a secure protocol does not imply that P is secure in the presence of Q. In fact, P and Q may be the same protocol. In other words, the security of concurrent execution is not an immediate consequence of the security of single execution. Pages 21 to 22 offer a particularly telling example of this.

The construction of many of these proofs is based on the counterintuitive concept of zero-knowledge proofs, themselves often based on “commitment schemes.” A zero-knowledge proof is a (generally interactive) process that convinces you that I know a certain fact, for example, a 3-coloring of a certain graph; however, accepting this fact tells you nothing more about this coloring than you knew at the beginning, other than the fact that it exists. Hence, it is useful that Goldreich’s second chapter is in fact a tutorial on zero-knowledge proofs.

I caution readers new to this field about an issue that is not emphasized in this book. When the authors say that the protocol works in the presence of less than one-third of corrupted participants, they mean that it will work in the same sense as the trusted third party will work; that is, it will correctly compute the mean of the inputs, including the less than one-third of false ones. In particular, if one university president says that his salary is $1 million dollars, this will completely invalidate the mean. This is a difficulty with the problem as stated, not with the protocol, and one might wish to get around this difficulty by asking instead for the median salary. One rogue answer does not disturb that value as much. Unfortunately, the median cannot be computed, as far as we know, by an arithmetic circuit.

The editors state that they hope “this book, while neither a textbook nor an encyclopedia, would prove to be an excellent guide.” It is certainly not a textbook: there is no clear statement of prerequisites (admittedly this would be difficult). The editors explicitly state that the chapters can be read independently. I am not completely convinced of this for the later chapters, but would, for example, actually recommend starting with chapter 3 rather than chapter 1.

In sum, this book is not for the faint-hearted, but offers a wealth of information and challenges for the diligent. Theoreticians, whether or not they are cryptographers, may be intrigued by the last chapter on the complexity of multiparty computation.