Oded Goldreich

Secure Multi-Party Computation


Files available:

First version posted in June 1998. Final revision posted October 2002.

A Warning: This is a draft. It is certainly full of various minor flaws, but is hoped and believed to contain no serious ones. A better exposition will appear in Volume 2 of Foundations of Cryptography.


Preface: More than ten years have elapsed since the first completeness theorems for two-party and multi-party fault-tolerant computation have been announced (by Yao and Goldreich, Micali and Wigderson, respectively). Analogous theorems have been proven in a variety of models, yet full proofs of the abovementioned basic results (i.e., for the ``computational model'' as well as for the ``private channel model'') are not to be found. This manuscript attempts to redeem this sour state of affairs, at least as far as the ``computational model'' goes.

Overview: A general framework for casting cryptographic (protocol) problems consists of specifying a random process which maps $m$ inputs to $m$ outputs. The inputs to the process are to be thought of as local inputs of $m$ parties, and the $m$ outputs are their corresponding local outputs. The random process describes the desired functionality. That is, if the $m$ parties were to trust each other (or trust some outside party), then they could each send their local input to the trusted party, who would compute the outcome of the process and send each party the corresponding output. The question addressed in this manuscript is to what extent can this trusted party be ``emulated'' by the mutually distrustful parties themselves.

In a nutshell, the results presented assert that any protocol problem (of the above type) is solveable in several natural models. Specifically, assuming the existence of trapdoor permutations, one may provide secure protocols for any two-party computation (allowing abort) as well as for any multi-party computations with honest majority. Thus, a host of cryptographic problems are solvable assuming the existence of trapdoor permutations. Specifically, any desired (input--output) functionality can be enforced, provided we are either willing to tolerate ``early abort'' or can rely on a majority of the parties to follow the protocol.

Aims and nature of the current manuscript: Our presentation is aimed at providing an accessible account of the most basic results regarding general secure multi-party computation. We focus on the ``computational model'', assuming the existence of trapdoor permutations. We provide almost full proofs for the abovementioned results: secure protocols for any two-party (and in fact multi-party) computation allowing abort, as well as for any multi-party computations with honest majority.

We do not attempt to provide the most general definitions and the most general tools. The aim is to present protocols which are secure with respect to a natural (althought not the strongest possible) model (i.e., the so-called ``static model''). The focus is on the protocols and the proofs of security, not on the choice of definitions.

Likewise, no attempt is made to present the most efficient versions possible for the said results. In contrary, in many cases we derive less efficient constructions due to our desire to present the material in a modular manner. This is best demonstrated in our non-optimized compilers~-- especially those used (on top of one another) in the multi-party case. As we view the general results presented here as mere claims of plausibility, we see little point in trying to optimize them.

Organization of the manuscript: Choices were made here too. In particular, we chose to present the two-party case first (see Chapter 2), and next to extend the ideas to the multi-party case (see Chapter 3). Thus, the reader interested in the multi-party case cannot skip Chapter 2. We hope that such a reader will appreciate that the two-party case is a good warm-up towards the $m$-party case, for general $m$. Actually, most ideas required for the latter can be presented in the case $m=2$, and such a presentation is less cumbersome and allows to focus on the essentials.

Within each chapter, we start with a treatment of the relatively easy case of semi-honest behavior, and next proceed to ``force'' general malicious parties to behave in a semi-honest manner. We believe that even a reader who views the semi-honest model as merely a mental experiment will appreciate the gain obtained by breaking the presentation in this way.


A Warning (repeated): This is a draft. It is certainly full of various minor flaws, but is hoped and believed to contain no serious ones. A better exposition is provided in Chapter 7 of (Volume 2 of) Foundations of Cryptography.


Back to Oded Goldreich's homepage or to Volume 2 of Foundations of Cryptography.