Secure multiparty computation
Encyclopedia
Secure multi-party computation (also known as secure computation or multi-party computation (MPC)) is a sub field of cryptography
. The goal of methods for secure multi-party computation is to 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., and was later named the millionaire problem
.
The concept is important in the field of cryptography
and is closely related to the idea of zero-knowledgeness. 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. 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 (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. 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 dubbed 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 protocol
s, 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.
Secure MPC provides solutions 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.
(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?'
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. The goal of methods for secure multi-party computation is to 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
Andrew Yao
Andrew Chi-Chih Yao is a prominent computer scientist and computational theorist. Yao used the minimax theorem to prove what is now known as Yao's Principle.Yao was born in Shanghai, China...
in a 1982 paper., and was later named the millionaire problem
Yao's Millionaires' Problem
Yao's Millionaires' problem is a secure multiparty communication problem which was introduced by Andrew Yao, a prominent computer scientist and computational theorist...
.
The concept is important in the field of cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
and is closely related to the idea of zero-knowledgeness. 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. 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 (incidentally, the first recipient of the Knuth Prize
Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...
) as secure two-party computation
Secure two-party computation
Secure two-party computation is sub-problem of secure multi-party computation that has received special attention by researchers because of its close relation to many cryptographic tasks...
.
The millionaire problem and its solution gave way to a generalization to multi-party protocols. 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 dubbed 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 protocol
Cryptographic protocol
A security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...
s, 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 in which the scheme is described might assume that participants use a synchronized network (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 (an adversary cannot read, modify or generate messages in the channel), etc.
- The centrally controlled adversary considered can be passive (only allowed to read the data of a certain number of participants) or active (can corrupt the execution protocol or a certain number of participants).
- An adversary can be static (chooses its victims before the start of the multi-party computation) or dynamic (can choose 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 (it can affect certain predefined subsets of participants, modeling different possible collusions). These structures are commonly referred to as adversary structures. The opposite set consisting of the sets of honest parties that can still execute a computational task is related to the concept of access structureAccess structureAccess structures are used in the study of security system where multiple parties need to work together to obtain a resource. Groups of parties that are granted access are called qualified. In set theoretic terms they are referred to as qualified sets. In turn, the set of all such qualified sets is...
s.
An important primitive in MPC is oblivious transfer
Oblivious transfer
In cryptography, an oblivious transfer protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece has been transferred....
.
Unconditionally or information-theoretically secure MPC is closely related to the problem of secret sharing
Secret sharing
Secret sharing refers to method for distributing a secret amongst a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares are combined together; individual shares are of no use on their own.More formally, in a...
, and more specifically verifiable secret sharing
Verifiable secret sharing
In cryptography, a secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent. More formally, verifiable secret sharing ensures that even if the dealer is malicious there is a well-defined secret that the players can later...
(VSS); many secure MPC protocols that protect against active adversaries use VSS.
Secure MPC provides solutions to various real-life problems such as distributed voting, private bidding and auctions, sharing of signature or decryption functions, private information retrieval
Private information retrieval
In cryptography, a private information retrieval protocol allows a user to retrieve an item from a server in possession of a database without revealing which item they are retrieving...
, etc. The first large-scale and practical application of multiparty computation took place in Denmark in January 2008, as described by Bogetoft et al.
Two-party computation
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 computationSecure two-party computation
Secure two-party computation is sub-problem of secure multi-party computation that has received special attention by researchers because of its close relation to many cryptographic tasks...
(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
Virtual Party Protocol is an SMC protocol which uses virtual parties and complex mathematics to hide the identity of the parties.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"
- 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.
- 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