Secure multi-party computation

Secure multi-party computation (also known as secure computation or multi-party computation (MPC)) is a subfield of cryptography with the goal to create methods for parties to jointly compute a function over their inputs, and keeping these inputs private.

Definition

In an MPC, a given number of participants p₁, p₂, ..., p_N each have private data, respectively d₁, d₂, ..., d_N. Participants want to compute the value of a public function F on N variables at the point (d₁, d₂, ..., d_N). 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.

Overview

The concept is closely related to the idea of zero knowledge. For example, two millionaires can compute which one is richer without revealing their net worth. This very example was used by Andrew C. Yao in a 1982 paper,^[1] which was later named Yao's Millionaires' Problem.^[2]

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— and , respectively—may wish to jointly compute some function without revealing any information about and other than what can be reasonably deduced by knowing the actual value of , where "reasonably deduced" is often interpreted as equivalent to computation within polynomial time (an additional interpretation is that no information can be leaked beyond what is implied by the output; for example with Yao's Millionaire's Problem, clearly, the output informs both participants which of the two is the richer, thus 'leaking' the information that either or ). The primary motivation for studying methods of secure computation is to design systems that allow for maximum utility of information without compromising user privacy.

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

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

History

Secure computation was formally introduced as secure two-party computation (2PC) in 1982 by Andrew Yao,^[5] the first recipient of the Knuth Prize. It is also referred to as Secure function evaluation (SFE), and is concerned with the question: 'Can two party computation be achieved more efficiently and under weaker security assumptions than general MPC?'

The millionaire problem solution gave way to a generalization to multi-party protocols.^[6]

Security assumptions

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

• It can be computational (i.e. based on some mathematical problem, like factoring) or unconditional (usually with some probability of error which can be made arbitrarily small).
• The model might assume that participants use a synchronized network, where a message sent at a "tick" always arrives at the next "tick", that a secure and reliable broadcast channel exists, that a secure communication channel exists between every pair of participants where an adversary cannot read, modify or generate messages in the channel, etc.

The set of honest parties that can execute a computational task is related to the concept of access structure. In contrast, "adversary structures" can consist of the following:

• The centrally controlled adversary can be passive, i.e. only allowed to read the data of a certain number of participants or active, i.e. able to corrupt the execution protocol or a certain number of participants.
• An adversary can be static, i.e. choosing its victims before the start of the multi-party computation or dynamic, i.e. choosing its victims during the course of execution of the multiparty computation. Attaining security against a dynamic adversary is often much harder than security against a static adversary.
• An adversary can be defined as a "threshold structure" meaning that it can corrupt or simply read the memory of a number of participants up to some threshold, or be defined as a more complex structure, where it can affect certain predefined subsets of participants, modeling different possible collusions.

Protocols used

An important primitive used in MPC is oblivious transfer.

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

Secure sum protocols allow multiple cooperating parties to compute sum function of their individual data without revealing the data to one another.^[8]

In 2014 a "model of fairness in secure computation in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty" has been described for the Bitcoin network or for fair lottery.^[9]

See also

• Multi-party fair exchange protocol
• Privacy-preserving computational geometry

References

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. ↑ Claudio Orlandi: Is multiparty computation any good in practice?, ICASSP 2011
4. ↑ Peter Bogetoft, Dan Lund Christensen, Ivan Damgård, Martin Geisler, Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielse, Jakob Pagter, Michael Schwartzbach and Tomas Toft (2008). "Multiparty Computation Goes Live". Cryptology ePrint Archive (Report 2008/068). 
5. ↑ Andrew C. Yao, Protocols for secure computations (extended abstract)
6. ↑ 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.
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
9. ↑ Iddo Bentov, Ranjit Kumaresan (2014). "How to Use Bitcoin to Design Fair Protocols". Cryptology e print (International Association for Cryptologic Research (IACR)) (129): 1–38. Retrieved 9 October 2014. 

External links

• Solution to the Millionaire's Problem A description of Yao's algorithm
• Helger Lipmaa's links about multiparty computation
• Nick Szabo, "The God Protocols" at the Wayback Machine (archived December 30, 2006)
• Secure distributed CSP (DisCSP) solvers — a web-application with an applet-interpreter to design and run your own full-fledged secure multiparty computation (based on the SMC declarative language). Uses secure arithmetic circuit evaluation and mix-nets.
• VMCrypt A Java library for scalable secure computation. By Lior Malka.
• The Fairplay Project — Includes a software package for secure two-party computation, where the function is defined using a high-level function description language, and evaluated using Yao's protocol for secure evaluation of boolean circuits.
• The SIMAP project; Secure Information Management and Processing (SIMAP) is a project sponsored by the Danish National Research Agency aimed implementing Secure Multiparty Computation.
• Secure Multiparty Computation Language - project for development of a 'domain specific programming language for secure multiparty computation' and associated cryptographic runtime.
• VIFF: Virtual Ideal Functionality Framework — Framework for asynchronous multi-party computations (code available under the LGPL). Offers arithmetic with secret shared values including secure comparison.
• Sharemind: a framework for privacy-preserving data mining — A distributed virtual machine with the capability to run privacy-preserving operations. Has a privacy-preserving programming language for data mining tools. Includes developer tools.
• MPCLib: Multi-Party Computation Library — A library written in C# and C++ that implements several building blocks required for implementing secure multi-party computation protocols. MPCLib has a discrete-event simulation engine that can be used for simulating MPC protocols in virtual networks.
• Virtual Parties in SMC A protocol for Virtual Parties in SMC (Secure Multi Party computation)
• MPC Java-based implementation A Java-based implementation of the MPC protocol based on Michael.B, Shafi.G and Avi.W's theorem ("Completeness theorems for non-cryptographic fault-tolerant distributed computation") with Welch-Berlekamp error correcting code algorithm to BCH codes. Supports multiple players and identification of "cheaters" with Byzantine protocol. By Erez Alon, Doron Friedland & Yael Smith.
• SEPIA A java library for SMC using secret sharing. Basic operations are optimized for large numbers of parallel invocations (code available under the LGPL).
• Essential bibliography Secure Multiparty Computation