Editing Secure multi-party computation (section)

== Definition and overview ==
{{unreferenced section|date=October 2024}}

In an MPC, a given number of participants,  p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>N</sub>, each have [[information privacy|private data]], respectively d<sub>1</sub>, d<sub>2</sub>, ..., d<sub>N</sub>. Participants want to compute the value of a public function on that private data: F(d<sub>1</sub>, d<sub>2</sub>, ..., d<sub>N</sub>) 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:
: {{math|F(x, y, z) {{=}} max(x, y, z)}}

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 {{math|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 {{Mvar|z}}, then Charlie learns that his {{Mvar|z}} is the maximum value, whereas Alice and Bob learn (if {{Mvar|x}}, {{Mvar|y}} and {{Mvar|z}} are distinct), that their input is not equal to the maximum, and that the maximum held is equal to {{Mvar|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:
* Input privacy: No information about the private data held by the parties can be inferred from the messages sent during the execution of the protocol. The only information that can be inferred about the private data is whatever could be inferred from seeing the output of the function alone.
* Correctness: Any proper subset of adversarial colluding parties willing to share information or deviate from the instructions during the protocol execution should not be able to force honest parties to output an incorrect result. This correctness goal comes in two flavours: either the honest parties are guaranteed to compute the correct output (a "robust" protocol), or they abort if they find an error (an MPC protocol "with abort").

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 Millionaires' 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.