Research on Secure Multi-Party Computation
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
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.
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).
Parallel Coin-Tossing and Constant-Round Secure Two-Party
In the Journal of Cryptology, 16(3):143-184, 2003.
An extended abstract appeared in Crypto 2001, Springer-Verlag (LNCS 2139), pages 171-189, 2001.
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.
Y. Lindell and B. Pinkas.
An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries.
In Eurocrypt 2007, Springer-Verlag (LNCS 4515), pages 52-78, 2007. Full version available.
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).
S. Goldwasser and Y. Lindell.
Secure Computation Without Agreement.
In the Journal of Cryptology, 18(3):247-287, 2005.
An extended abstract appeared in the 16th DISC, Springer-Verlag (LNCS 2508), pages 17-32, 2002.
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.
B. Barak, R. Canetti, Y. Lindell, R. Pass and T. Rabin.
Secure Computation Without Authentication.
In CRYPTO 2005, Springer-Verlag (LNCS 3621), pages
361-377, 2005. Full version available.
Abstract, Conference version:
gzipped Postscript, Full version: PDF.
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.
Y. Ishai, E. Kushilevitz, Y. Lindell and E. Petrank.
Black-Box Constructions for Secure Computation.
In the 38th STOC, pages 99-108, 2006.
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).
S.D. Gordon, C. Hazay, J. Katz and Y. Lindell. Complete Fairness in Secure Two-Party Computation. In the 40th STOC, pages 413-422, 2008. Full version available.
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:
Y. Lindell and B. Pinkas.
Privacy Preserving Data Mining.
In the Journal of Cryptology, 15(3):177-206, 2002.
An extended abstract appeared
in Crypto 2000, Springer-Verlag (LNCS 1880), pages 36-54, 2000.
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.
Y. Lindell and B. Pinkas. Secure Multiparty Computation for Privacy-Preserving Data Mining. To appear in the Journal of Privacy and Confidentiality.
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".
Y. Aumann and Y. Lindell.
Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries.
To appear in the Journal of Cryptology. An extended abstract appeared in TCC 2007, Springer-Verlag (LNCS 4392), pages 137-156, 2007.
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.
C. Hazay and Y. Lindell.
Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries.
In TCC 2008, Springer-Verlag (LNCS 4948) pages 155-175, 2008. Full version available.
C. Hazay and Y. Lindell. Constructions of Truly Practical Secure Protocols using Standard Smartcards. In the 15th ACM Conference on Computer and Communications Security (ACM CCS), pages 491-500, 2008. Full version available.
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