Ebook: Secure Multi-Party Computation

Thirty years have passed since the concept of ‘secure computation’, now known as ‘secure multiparty computation’, first appeared in the computing literature. The proposal that any function which involves inputs held privately by different parties can be computed securely without revealing much about the inputs, must have seemed unlikely or even paradoxical to some. One of the examples given, nick-named the ‘millionaires’ problem', where two rich people wish to find out who is richer without giving out clues on their actual worth, stood as a faithful representative whose solution still seems to bemuse newcomers to the field today.

In the three decades since, many brilliant scientists have contributed to the development of secure multiparty computation, turning it into an active research area and often an important showcase for modern cryptography and complexity theory, with no sign of abating anytime soon.

The current book, edited by two leading researchers Manoj Prabhakaran and Amit Sahai, does a wonderful job of weaving a compelling story out of the subject matter. The collection features writings by a galaxy of intellectual luminaries who have made landmark contributions in moving this field forward. The eight chapters cover foundational material in multiparty computation and related topics, leading to more advanced discussions on selected topics and special techniques, culminating in some novel approaches at the current frontier. There is no doubt that this monograph will become a definitive work which will prove equally valuable as a textbook for the novices and as a reference for the experts.

Nothing lives in a vacuum. The birth and development of secure multiparty computation was influenced heavily by two revolutionary trends which emerged in the late 1970's. The first was the transition from single stand-alone computing hardware to the networked computing paradigm. The second was the realization that cryptography would play a vital role in the future networked world and, to meet this challenge, cryptography must suitably integrate the dual pillars of information science – Shannon's information theory and Turing's complexity theory. These two trends powered the tremendous developments in a multitude of information sciences and technologies, both theoretical and practical. Indeed, one can sense that the intellectual depth and breadth of these trends have provided the fertile soil from which secure multiparty computation has blossomed as a scientific field.

Despite all the impressive advances, we are still far from having a complete understanding of cryptography in general, and secure multiparty computation in particular. We comprehend secure computation very well in the case of standalone computation, but the highly interactive environments still remains somewhat elusive. To get a complete grasp on the latter may require a thorough scientific understanding of the concept of information and how it is transmitted and propagated. In this regard, the phenomenal successes achieved by Shannon's information theory may have inadvertently left information scientists more complacent than justified. Great challenges still await the ambitious. I believe that future great sciences will flow from various sources such as a fuller integration of information theory and complexity theory, further expeditions of highly interactive environments, and from new frontiers such as quantum information theory. The present book serves very well as a great starting point for an adventure into this wonderful world.

Finally, I would like to thank the editors Manoj Prabhakaran and Amit Sahai for inviting me to write this Foreword. Grateful to be regarded by some as the initiator of the secure multiparty computation area, I have taken great pleasure in reading through this book and finding inspirations chapter after chapter. I trust that many readers will be similarly enlightened by this outstanding book.

Andrew Chi-Chih Yao

July 2012, Beijing

We survey basic definitions and results concerning secure multi-party computations, where the two-party case is an important special case. In a nutshell, these results assert that, under a variety of reasonable settings and/or assumptions, it is possible to construct protocols for securely computing any desirable multi-party functionality. Confining ourselves to the very basics of this vast area of study, we focus on the stand-alone setting, while leaving the survey of the study of the security of concurrent executions to other surveys.

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proved. Their direct applications in cryptography are numerous, where they are typically used to force malicious parties to behave according to a predetermined protocol. In addition, zero-knowledge proofs serve as an excellent bench-mark for the study of various problems regarding cryptographic protocols.

The first part of this tutorial reviews the basic definitional approach and its variants as well as the main results regarding the power of zero-knowledge proofs. The second part reviews several advanced topics including (1) the composeability of zero-knowledge proofs and (2) the use of the adversary's program within the proof of security (i.e., non-black-box simulation).

What does it mean for a cryptographic protocol to be “secure”? Capturing security properties of cryptographic protocols in a meaningful way is a slippery business: On the one hand, we want to guarantee that a security property holds in face of “all feasible attacks” against a protocol. On the other hand, we want our formalism to not be overly restrictive; that is, we want to accept those protocols that do not succumb to “feasible attacks”.

This chapter surveys a general methodology for defining security of cryptographic protocols. The methodology, often dubbed the “trusted party paradigm”, allows for defining the security requirements of practically any cryptographic task in a unified and natural way. We first review a basic formulation that captures security in isolation from other protocol instances. Next we address the secure composition problem, namely the vulnerabilities resulting from the interactions among different protocol instances that run alongside each other in the same system. We demonstrate the limitations of the basic formalism and review a formalism that guarantees security of protocols even in general composite systems.

This chapter overlaps the previous one in some of the material. There is however a difference in stress: The stress here is more on the definitional aspects and in particular on the challenge in capturing security properties of individual protocols within more complex environments.

One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest this holds as long as t < n/2 parties are corrupted, and when the adversary is malicious this holds as long as t < n/3 parties are corrupted. In this chapter, we present a full description of the BGW protocol for the semi-honest and malicious settings, along with detailed explanations and intuition regarding the security of the protocols; full proofs can be found in [1].

Most of this book has considered two-party and multiparty computation with security with (unfair) abort. This security notion allows the adversary to force the honest parties to abort even depending on the outputs of corrupted parties. (Note, however, that the adversary is not allowed to bias the output of honest parties in any other manner.) This relaxation of security is necessary if one wishes to tolerate arbitrarily many corruptions. A further relaxation considers computational security, where the adversary is assumed to be computationally bounded, e.g., probabilistic polynomial time. In this setting, any circuit can be securely realized even when arbitrarily many parties are corrupted, as long as one is willing to sacrifice fairness and robustness.

In the current chapter, as in the previous chapter, we consider multiparty computation (MPC) with full security — i.e., with guaranteed output delivery. Further, this setting considers information-theoretic (i.t.) security, in which the security of protocols is guaranteed independent of computational assumptions, and no restriction on the adversary's computing power is assumed, which is why i.t. security is often referred to as unconditional security. As we shall see, this strong type of security can be achieved only when the choice of the sets of parties that can be corrupted at the same time is restricted, e.g., when a strict minority of the parties might be corrupted. Because of this limitation, this type of full security is interesting only in the setting of three or more parties.

This chapter offers an overview of the main results in feasibility of information-theoretically secure multi-party computation.

One of the most fundamental goals in cryptography is to design protocols that remain secure when adversarial participants can engage in arbitrary malicious behavior. In 1986, Goldreich, Micali, and Wigderson presented a powerful paradigm for designing such protocols: their approach reduced the task of designing secure protocols to designing protocols that only guarantee security against “honest-but-curious” participants. By making use of zero-knowledge proofs, the GMW paradigm enforces honest behavior without compromising secrecy. Over the past two decades, this approach has been the dominant paradigm for cryptographic protocol design.

In this chapter, we present a new general paradigm/protocol compiler for secure protocol design developed in 2008 by Ishai, Prabhakaran, and Sahai that departs considerably from the GMW framework. This new approach also reduces the task of designing secure protocols to designing protocols that only guarantee security against honest-but-curious participants. However, the new approach avoids the use of zero-knowledge proofs, and instead makes use of multi-party protocols in a much simpler setting – where the majority of participants are completely honest (such multi-party protocols can exist without requiring any computational assumptions). The IPS paradigm yields protocols that rely on Oblivious Transfer (OT) as a building block. This offers a number of advantages in generality and efficiency.

In contrast to the GMW paradigm, by avoiding the use of zero-knowledge proofs, the IPS paradigm is able to treat the semi-honest protocols as “black boxes”. This allows improvement over previous results in the area of secure computation. In particular, the IPS compiler yields applications such as:

• Conceptually simpler and more efficient ways for basing unconditionally secure cryptography on OT.

• More efficient protocols for generating a large number of OTs using a small number of OTs.

• Secure and efficient protocols which only make a black-box use of cryptographic primitives or underlying algebraic structures in settings where no such protocols were known before.

This chapter is loosely based on several invited talks that the second author has given on the IPS compiler.

To what extent can a computation be made “simpler” by settling for computing a randomized encoding of the output? Originating from Yao's seminal idea of garbled circuits, answers to this question have found applications in cryptography and elsewhere. We will survey the state of the art on different flavors of this question that are motivated by different problems in secure computation and correspond to different notions of simplicity.

The central objects of secure multiparty computation are the “multiparty functions” (or functionalities) that it seeks to securely realize. In this chapter we survey a set of results that constitute a Cryptographic Complexity Theory. This theory classifies and compares multiparty functions according to their secure computability and reducibility to each other. The basic questions studied, under various notions of security and reducibility, include:

• Which functionalities are securely realizable (or are “trivial” – i.e., can be reduced to any functionality)?

• Which functionalities are “complete” – i.e., those to which any functionality can be reduced?

• More generally, which functionalities are reducible to which? Outside of triviality and completeness, this question is relatively less explored.

Reductions yield relative measures of complexity among various functionalities. In the information-theoretic setting, absolute complexity measures have also been considered. In particular, we discuss results regarding which functions have t-private protocols (in which security is required against a passive adversary corrupting t out of n players) and how this set changes as t increases from 1 to n.

We treat separately the results on two-party functionalities, for which the cryptographic complexity is much better understood. In particular, we present unified combinatorial characterizations of completeness and triviality for secure function evaluation using notions of isomorphism and the common information functionality (called the kernel) of a given functionality. Beyond completeness and triviality, we also discuss results on general reducibility, and, in the computationally bounded setting, the connection between these reductions and computational hardness assumptions.

We briefly discuss results on reactive functionalities, which are much less studied than non-reactive (secure function evaluation) functionalities. Finally, we conclude with a selection of open problems.