Research on Secure Multi-Party Computation


General Introduction

Distributed computing considers the scenario where a number of distinct, yet connected, computing devices (or parties) wish to carry out a joint computation of some function. For example, these devices may be servers who hold a distributed database system, and the function to be computed may be a database update of some kind. The aim of secure multi-party computation is to enable parties to carry out such distributed computing tasks in a secure manner. Whereas distributed computing classically deals with questions of computing under the threat of machine crashes and other inadvertent faults, secure multi-party computation is concerned with the possibility of deliberately malicious behaviour by some adversarial entity. That is, it is assumed that a protocol execution may come under "attack" by an external entity, or even by a subset of the participating parties. The aim of this attack may be to learn private information or cause the result of the computation to be incorrect. Thus, two important requirements on any secure computation protocol are privacy and correctness. The privacy requirement states that nothing should be learned beyond what is absolutely necessary; more exactly, parties should learn their output and nothing else. The correctness requirement states that each party should receive its correct output. Therefore, the adversary must not be able to cause the result of the computation to deviate from the function that the parties had set out to compute.

The setting of secure multi-party computation encompasses tasks as simple as coin-tossing and broadcast, and as complex as electronic voting, electronic auctions, electronic cash schemes, contract signing, anonymous transactions, and private information retrieval schemes. Consider for a moment the tasks of voting and auctions. The privacy requirement for an election protocol ensures that no parties learn anything about the individual votes of other parties, and the correctness requirement ensures that no coalition of parties can influence the outcome of the election beyond just voting for their preferred candidate. Likewise, in an auction protocol, the privacy requirement ensures that only the winning bid is revealed (this may be desired), and the correctness requirement ensures that the highest bidder is indeed the party to win (and so the auctioneer, or any other party, cannot bias the outcome).

Due to its generality, the setting of secure multi-party computation can model almost every, if not every, cryptographic problem (including the classic tasks of encryption and authentication). Therefore, questions of feasibility and infeasibility for secure multi-party computation are fundamental to the theory and practice of cryptography.

Click here to view the powerpoint slides of a tutorial on topic of secure multiparty computation. This paper on Secure Multiparty Computation for Privacy-Preserving Data Mining also serves as a good introductory tutorial to the field of secure computation.


My Contributions

One question of importance with respect to protocol construction is efficiency. Arguably, the most important measure of efficiency is the round complexity, or the number of rounds of communication required to complete the protocol. (This is not to say that bandwidth and local computation are not important; however, they are arguably secondary concerns.) We presented the first constant-round protocol for securely computing any two-party functionality, where security is achieved against malicious, static adversaries. Subsequent to this work, constant round protocols for securely computing any multi-party (rather than just two-party) functionality were presented at Eurocrypt 2003 (by Katz, Ostrovsky and Smith), and STOC 2004 (by Pass). Furthermore, the exact round complexity for general two-party computation with black-box proofs of security was determined to be five rounds (see Katz and Ostrovksy, Crypto 2004).

The novelty of the above work is in providing a constant-round protocol that is secure in the presence of malicious adversaries who may deviate arbitrarily from the protocol specification. Our result relies on Yao's constant-round protocol (FOCS 1986) that provides security in the presence of semi-honest adversaries (such adversaries follow the protocol instructions but may try to learn more information than just their output). Unfortunately, despite its importance, to the best of our knowledge a full proof of Yao's protocol was never published. In an attempt to correct this state of affairs, we have written a full description and proof of Yao's two-party protocol.

Following the above, we also presented an efficient way of transforming Yao's protocol into one that is secure against malicious adversary. Our protocol is far more efficient than one obtained by applying the generic compiler of Goldreich, Micali and Wigderson to Yao's protocol.

Another question of importance for secure protocol construction relates to the question of what setup or network assumptions are needed. It was widespread folklore that a broadcast channel is necessary for achieving secure computation. In the case that strictly less than a 1/3 of the participating parties may be corrupted, broadcast can be securely implemented via Byzantine agreement. However, when 1/3 or more of the parties may be corrupted, either a physical broadcast channel or an authenticated Byzantine agreement protocol must be used. A physical broadcast channel is often not available and authenticated Byzantine agreement requires a public-key infrastructure (increasing the setup) and, in addition, poses an obstacle to protocol composition (as shown in [LLR02]). By slightly relaxing the standard definition of secure computation, we have shown that despite this widely held belief, secure protocols can be constructed in a standard point-to-point network and without any reliance on Byzantine agreement protocols. This work has ramifications on protocol composition (as mentioned above) and protocol efficiency (since our protocols do not need Byzantine agreement they are significantly more efficient).

Closely related work appears in Eurocrypt 2002 (by Fitzi, Gisin, Maurer and Vot Rotz) and in PODC 2002 (by Fitzi, Gottesman, Hirt, Holenstein and Smith).

Continuing in the above line of research that attempts to understand what setup assumptions are truly needed for obtaining secure protocols, we note that all known protocols assume that all parties are connected via authenticated point-to-point channels. Such channels ensure that messages sent between honest parties are not maliciously modified by an adversary. We have shown that meaningful secure computation can be achieved even in a completely unauthenticated network (although the guarantees are weaker than when authenticated channels are assumed). Beyond the theoretical question of what can be obtained with no setup assumptions whatsoever, this result has a number of applications. For just one example, we show that in a partially authenticated network (like the Internet today where servers typically have certificates for digital signatures, but clients do not), it is possible to carry out secure computation while obtaining a meaningful security guarantee.

An interesting theoretical question relating to secure computation is due to the fact that all known protocols use the underlying cryptographic primitive (e.g., enhanced trapdoor permutation) in a nonblack-box way. Specifically, in order to obtain security in the presence of malicious adversaries, general NP-proofs are used, and these refer to the circuit computing the primitive. There has been much interest in the question of black-box versus nonblack-box reductions, and we consider whether or not constructions of general protocols for secure computation must really be nonblack-box. We answer the question by constructing a protocol that uses only black-box access to a "low-level" primitive (specifically, a family of enhanced trapdoor permutations or a homomorphic public-key encryption scheme). We actually obtain a "fully black-box" reduction. As we describe in the paper, black-box constructions in this context actually have significant efficiency advantages as well.

An important property in secure protocols is that of fairness; loosely speaking, this means that if any party receives output then all parties receive output. Unfortunately, in 1986 it was shown by Cleve that it is impossible to achieve fairness in general without an honest majority. Specifically, Cleve showed that it is impossible for two parties to toss a fair coin (essentially, because one party can always abort early). Since Cleve's fundamental result, it was widely believed that only "trivial functions" can be securely computed with fairness without an honest majority. In this paper, we show that this belief is false. Indeed, although there are limitation, some very interesting functions can be securely computed with fairness (including Yao's original millionaires' problem over a polynomial-size domain).

As we have mentioned above, secure multi-party computation has broad applicability to many different fields. One particular application that has gained much interest recently is that of privacy preserving data mining. A classic example of a problem of this kind is two hospitals who wish to jointly mine their data, but are prevented from pooling it by privacy law. We presented a highly efficient protocol for securely computing the ID3 decision tree algorithm over distributed databases, where security is achieved against semi-honest adversaries.

Subsequent to the above paper, much work has been carried out on this topic. One list of pointers to work on privacy preserving data mining can be found here. The following tutorial paper on secure multiparty computation for privacy-preserving data mining focuses on the basic paradigms of secure computation and their relevance to privacy-preserving data mining: The above work on privacy-preserving data mining presents a protocol in the semi-honest adversary model. This provides relatively weak security guarantees and the construction of secure protocols that provide stronger guarantees is of great interest. Unfortunately, almost all of the work on privacy-preserving data mining is in the semi-honest model and this seems to be due to the difficulty of constructing highly efficient protocol in the malicious adversary model. We present a new adversary model called security in the presence of covert adversaries that captures the notion that in many real-world settings, parties are willing to cheat but do not wish to be caught. We also present efficient (general) protocols that meet our new definition. The next step in this line of work is to construct protocols for specific problems of interest that are highly efficient and secure against covert adversaries. We constructed such a protocol for the important problem of set intersection. In addition, we present protocols that are secure against malicious adversaries, but for a weaker definition called "one-sided simulatability". In the above paper, we achieve high efficiency by considering a relaxed notion of security. An alternative way of achieving this is to introduce realistic assumptions regarding the resources the parties can use. In the paper below, we use standard smartcards and standard smartcard infrastructure to construct protocols for secure set intersection and oblivious database and document search that are orders of magnitude more efficient than anything previously known. Our protocols are secure in the presence of malicious adversaries, with full simulation, under the assumption that the smartcards are tamper proof.

Protocol composition. Much of my research on the topic of secure computation has been in the context of protocol composition. This work is discussed here.

Note: In some places above, we have provided references to work (of others) that is highly relevant. In no way is this supposed to be a complete or current list. We hope, however, that it will be helpful in understanding the current state of knowledge on some of the topics discussed here.

Back Home