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.
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.
For example, suppose we have three parties Alice, Bob and Charlie, with respective inputs x, y and z denoting their salaries. They want to find out the highest of the three salaries, without revealing to each other how much each of them makes. Mathematically, this translates to them computing:
If there were some trusted outside party (say, they had a mutual friend Tony who they knew could keep a secret), they could each tell their salary to Tony, he could compute the maximum, and tell that number to all of them. The goal of MPC is to design a protocol, where, by exchanging messages only with each other, Alice, Bob, and Charlie can still learn F(x, y, z) without revealing who makes what and without having to rely on Tony. They should learn no more by engaging in their protocol than they would learn by interacting with an incorruptible, perfectly trustworthy Tony.
In particular, all that the parties can learn is what they can learn from the output and their own input. So in the above example, if the output is z, then Charlie learns that his z is the maximum value, whereas Alice and Bob learn (if x, y and z are distinct), that their input is not equal to the maximum, and that the maximum held is equal to z. The basic scenario can be easily generalised to where the parties have several inputs and outputs, and the function outputs different values to different parties.
Informally speaking, the most basic properties that a multi-party computation protocol aims to ensure are:
There are a wide range of practical applications, varying from simple tasks such as coin tossing to more complex ones like electronic auctions (e.g. compute the market clearing price), electronic voting, or privacy-preserving data mining. A classical example is the Millionaire's Problem: two millionaires want to know who is richer, in such a way that neither of them learns the net worth of the other. A solution to this situation is essentially to securely evaluate the comparison function.
A key question to ask is; when is such a multiparty computation protocol secure? In modern cryptography, a protocol can only be deemed to be secure if it comes equipped with a "security proof". This is a mathematical proof that the security of the protocol reduces to that of the security of the underlying primitives. But this means we need a definition of what it means for a protocol to be secure. This is hard to formalize, in the case of MPC, since we cannot say that the parties should "learn nothing" since they need to learn the output and this depends on the inputs. In addition, we cannot just say that the output must be "correct" since the correct output depends on the parties’ inputs, and we do not know what inputs corrupted parties will use. A formal mathematical definition of security for MPC protocols follows the ideal-real-world paradigm, described below.
...
Wikipedia