On the Composition of Secure Multi-Party Protocols

Ph.D. Thesis by Yehuda Lindell


In the setting of multi-party computation, sets of two or more parties with private inputs wish to jointly compute some (predetermined) function of their inputs. The computation should be such that the outputs received by the parties are correctly distributed, and furthermore, that the privacy of each party's input is preserved as much as possible. This encompasses any distributed computing task and includes computations as simple as coin-tossing and broadcast, and as complex as electronic voting, electronic auctions, electronic cash schemes and anonymous transactions. The feasibility (and infeasibility) of multi-party computation has been extensively studied, resulting in a seemingly comprehensive understanding of what can and cannot be securely computed, and under what assumptions. However, most of this research relates only to the stand-alone setting, where a single set of parties execute a single protocol in isolation. In contrast, in modern network settings, it is usually the case that many different sets of parties run many different protocol executions at the same time. Furthermore, an active adversary can try to utilize these many different executions in order to somehow ``break'' the security of the individual protocols. A protocol that is secure in such a multi-execution setting is said to remain secure under ``protocol composition''.

Unfortunately, protocols that are secure in the stand-alone setting do not necessarily remain secure under composition. In fact, as we show here, the situation is actually much worse. That is, in this work, we show that there exist multi-party tasks which have secure protocols for the stand-alone setting, but which cannot be solved by any protocol in the setting of composition. We demonstrate this fact on the important task of secure broadcast. Specifically, in the stand-alone model, it is known that a public-key infrastructure of digital signatures can be used in order to obtain broadcast that is secure for any number of corrupted parties. In contrast, we show that it is impossible to obtain a secure broadcast protocol that composes in parallel or concurrently (even assuming an infrastructure of digital signatures), unless one assumes that less than one third of the parties are corrupted. Thus, solving multi-party tasks when security under composition is required, is strictly harder than in the stand-alone model.

The above highlights the need for a renewed study, in the context of composition, of all the feasibility results that have been proven in the stand-alone setting. Specifically, many fundamental questions regarding the feasibility and infeasibility of obtaining security under composition have yet to be even considered. The study of these questions therefore constitutes an important and pressing research project.

A recent important step forward in this direction was made with the introduction of a new security definition called ``universal composability''. The importance of this definition is that protocols that are proven secure by it are guaranteed to remain secure in a very general setting of composition. In particular, it is guaranteed that such protocols will remain secure even when run concurrently with many other arbitrary protocols. This captures the security requirements of protocols in real settings, like that of the Internet. Previously, it has been shown that when a majority of the parties are assumed to be honest, universally composable protocols can be constructed for any multi-party task. (This result holds in the plain model, where no trusted setup phase is assumed.) It has also been shown that when no honest majority of parties is guaranteed (as is the case for the important two-party setting), there are important functions that cannot be securely realized in a universally composable way by any protocol in the plain model. Thus, an important open question is whether or not there exists a reasonable model in which universally composable multi-party computation of general functions can be achieved, when there is no honest majority. We show that in the common reference string model (where all parties have access to a common string that was generated in a trusted preprocessing phase), universally composable protocols exist for any two-party and multi-party function and for any number of corrupted parties. This result establishes the feasibility of obtaining secure two-party and multi-party computation (without an honest majority) under the most stringent security definition currently known. More importantly, it demonstrates that security in Internet-like settings can be achieved, at least in the common reference string model.

An additional result presented in this work is related to the fact that all known protocols for secure multi-party computation rely extensively on a broadcast channel, and implement this channel in a point-to-point network using a protocol for secure broadcast. Therefore, the impossibility of achieving broadcast under composition when a third or more parties are corrupted, implies that the above-mentioned multi-party protocols cannot be composed (again, when a third or more parties are corrupted). The use of broadcast therefore constitutes a serious obstacle to achieving protocol composition. In order to remove this obstacle, we first provide a new definition of secure multi-party computation that is a mild relaxation of previous definitions. Then, we show that under this definition, secure computation of any function can be achieved without broadcast by adapting known protocols. As a corollary we obtain secure multi-party protocols that compose (concurrently, when an honest majority is assumed, and in parallel when any number of parties may be corrupted). Another additional benefit of removing the need for broadcast is that we also remove the need for a public-key infrastructure of digital signatures. Thus, we reduce the assumptions required for obtaining secure computation, even in the stand-alone model.

The Thesis:
Postscript, gzipped Postscript.

The Introduction: (including an overview of the concept of protocol composition)
Postscript, gzipped Postscript.

Published Version:
A much improved version of this thesis (including a much expanded introduction) has been published as a monograph in the Lecture Notes in Computer Science Series (LNCS 2815), Springer-Verlag, 2003. Go here for details.

Back Home