Secure multi-party computation

From Wikipedia, the free encyclopedia - View original article

Jump to: navigation, search

Secure multi-party computation (also known as secure computation or multi-party computation (MPC)) is a subfield of cryptography. The goal of this field is to create methods that enable parties to jointly compute a function over their inputs, while at the same time keeping these inputs private. For example, two millionaires can compute which one is richer, but without revealing their net worth. In fact, this very example was initially suggested by Andrew C. Yao in a 1982 paper.,[1] and was later named the millionaire problem. An excellent review of MPC is provided by Rashid Sheikh et al. in [2].

The concept is important in the field of cryptography and is closely related to the idea of zero knowledge. In general it refers to computational systems in which multiple parties wish to jointly compute some value based on individually held secret bits of information, but do not wish to reveal their secrets to one another in the process. For example, two individuals who each possess some secret information—x and y, respectively—may wish to jointly compute some function f(x,y) without revealing any information about x and y other than what can be reasonably deduced by knowing the actual value of f(x,y), where "reasonably deduced" is often interpreted as equivalent to computation within polynomial time. The primary motivation for studying methods of secure computation is to design systems that allow for maximum utility of information without compromising user privacy.

Secure computation was formally introduced in 1982 by A. Yao [3] (incidentally, the first recipient of the Knuth Prize) as secure two-party computation.

The millionaire problem and its solution gave way to a generalization to multi-party protocols.[4] In an MPC, a given number of participants p1, p2, ..., pN each have a private data, respectively d1, d2, ..., dN. The participants want to compute the value of a public function F on N variables at the point (d1, d2, ..., dN). An MPC protocol is secure if no participant can learn more from the description of the public function and the result of the global calculation than what he/she can learn from his/her own entry — under particular conditions depending on the model used.

Like many cryptographic protocols, the security of an MPC protocol can rely on different assumptions:

An important primitive in MPC is oblivious transfer.

Unconditionally or information-theoretically secure MPC is closely related to the problem of secret sharing, and more specifically verifiable secret sharing (VSS); many secure MPC protocols that protect against active adversaries use VSS.

Performing a computation using MPC protocols is still orders of magnitude slower than performing the computation using a trusted third party. However, more and more efficient protocols for MPC have been proposed, and MPC can be now used as a practical solution[5] to various real-life problems such as distributed voting, private bidding and auctions, sharing of signature or decryption functions, private information retrieval, etc. The first large-scale and practical application of multiparty computation took place in Denmark in January 2008, as described by Bogetoft et al.[6]

Two-party computation[edit]

The sub-problem of MPC that has received special attention by researchers because of its close relation to many cryptographic tasks is referred to as secure two-party computation (2PC) or just as Secure function evaluation (SFE). This area of research is concerned with the question: 'Can two party computation be achieved more efficiently and under weaker security assumptions than general MPC?'

Virtual Party Protocol[edit]

Virtual Party Protocol is an SMC protocol which uses virtual parties and complex mathematics to hide the identity of the parties.[7]

Secure sum protocols[edit]

Secure sum protocols allow multiple cooperating parties to compute some function of their individual data without revealing the data to one another. Rashid Sheikh et al. proposed many secure sum protocols. [8]

See also[edit]


  1. ^ Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164
  2. ^ Sheikh, R., Mishra, D. K. & Kumar, B. (2011). Secure Multiparty Computation: From Millionaires Problem to Anonymizer.. Information Security Journal: A Global Perspective, 20, 25-33.
  3. ^ Andrew C. Yao, Protocols for secure computations (extended abstract)
  4. ^ O. Goldreich, S. Micali, and A. Wigderson. How to play ANY mental game. In Proceedings of the nineteenth annual ACM conference on Theory of computing, pages 218-229. ACM Press, 1987.
  5. ^ Claudio Orlandi: Is multiparty computation any good in practice?, ICASSP 2011
  6. ^ Peter Bogetoft and Dan Lund Christensen and Ivan Damgård and Martin Geisler and Thomas Jakobsen and Mikkel Krøigaard and Janus Dam Nielsen and Jesper Buus Nielsen and Kurt Nielsen and Jakob Pagter and Michael Schwartzbach and Tomas Toft: Multiparty Computation Goes Live, Cryptology ePrint Archive: Report 2008/068
  7. ^ Pathak Rohit, Joshi Satyadhar, Advances in Information Security and Assurance, Springer Berlin / Heidelberg, ISSN 0302-9743 (Print) 1611-3349 (Online), ISBN 978-3-642-02616-4, DOI 10.1007/978-3-642-02617-1
  8. ^ Rashid Sheikh, Brijesh Kumar and Durgesh Kumar Mishra, Privacy Preserving k-secure sum protocols, International Journal of Computer Science and Information Security, ISSN 1947-5500 (Online),Vol.6, No.2, Nov. 2009

External links[edit]