Secure multi-party computation

Secure multi-party computation (also known as secure computation, multi-party computation (MPC), or privacy-preserving computation) is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their inputs while keeping those inputs private. Unlike traditional cryptographic tasks, where cryptography assures security and integrity of communication or storage and the adversary is outside the system of participants (an eavesdropper on the sender and receiver), the cryptography in this model protects participants' privacy from each other. Secure multi-party computation (also known as secure computation, multi-party computation (MPC), or privacy-preserving computation) is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their inputs while keeping those inputs private. Unlike traditional cryptographic tasks, where cryptography assures security and integrity of communication or storage and the adversary is outside the system of participants (an eavesdropper on the sender and receiver), the cryptography in this model protects participants' privacy from each other. The foundation for secure multi-party computation started in the late 1970s with the work on mental poker, cryptographic work that simulates game playing/computational tasks over distances without requiring a trusted third party. Note that traditionally, cryptography was about concealing content, while this new type of computation and protocol is about concealing partial information about data while computing with the data from many sources, and correctly producing outputs. Special purpose protocols for specific tasks started in the late 1970s. Later, secure computation was formally introduced as secure two-party computation (2PC) in 1982 (for the so-called Millionaires' Problem, a specific problem which is a Boolean predicate), and in generality (for any feasible computation) in 1986 by Andrew Yao. The area is also referred to as Secure Function Evaluation (SFE). The two party case was followed by a generalization to the multi-party by Goldreich, Micali and Wigderson. The computation is based on secret sharing of all the inputs and zero-knowledge proofs for a potentially malicious case, where the majority of honest players in the malicious adversary case assure that bad behavior is detected and the computation continues with the dishonest person eliminated or his input revealed. This work suggested the very basic general scheme to be followed by essentially all future multi-party protocols for secure computing. This work was followed by the first robust secure protocol which tolerates faulty behavior graciously without revealing anyone's output via a work which invented for this purpose the often used `share of shares idea' and a protocol that allows one of the parties to hide its input unconditionally. The above results are in a model where the adversary is limited to polynomial time computations, and it observes all communications, and therefore the model is called the `computational model'. Further, the protocol of oblivious transfer was shown to be complete for these tasks. The above results established that it is possible under the above variations to achieve secure computation when the majority of users are honest. The next question to solve was the case of secure communication channels where the point-to-point communication is not available to the adversary; in this case it was shown that solutions can be achieved with up to 1/3 of the parties being misbehaving and malicious, and the solutions apply no cryptographic tools (since secure communication is available). Adding a broadcast channel allows the system to tolerate up to 1/2 misbehaving minority, whereas connectivity constraints on the communication graph were investigated in the book Perfectly Secure Message Transmission. Over the years, the notion of general purpose multi-party protocols became a fertile area to investigate basic and general protocol issues properties on, such as universal composability or mobile adversary as in proactive secret sharing. Since the late 2000s, and certainly since 2010 and on, the domain of general purpose protocols has moved to deal with efficiency improvements of the protocols with practical applications in mind. Increasingly efficient protocols for MPC have been proposed, and MPC can be now considered as a practical solution to various real-life problems (especially ones that only require linear sharing of the secrets and mainly local operations on the shares with not much interactions among the parties), such as distributed voting, private bidding and auctions, sharing of signature or decryption functions and private information retrieval. The first large-scale and practical application of multi-party computation (demonstrated on an actual auction problem) took place in Denmark in January 2008. Obviously, both theoretical notions and investigations, and applied constructions are needed (e.g., conditions for moving MPC into part of day by day business was advocated and presented in). In an MPC, a given number of participants, p1, p2, ..., pN, each have private data, respectively d1, d2, ..., dN. Participants want to compute the value of a public function on that private data: F(d1, d2, ..., dN) while keeping their own inputs secret.