Editing Secure multi-party computation (section)

== Protocols ==
{{More citations needed section|date=October 2024}}
There are major differences between the protocols proposed for two party computation (2PC) and multi-party computation (MPC). Also, often for special purpose protocols of importance a specialized protocol that deviates from the generic ones has to be designed (voting, auctions, payments, etc.)

=== Two-party computation ===
{{Main|Secure two-party computation}}
{{See also|Garbled circuit}}
The two party setting is particularly interesting, not only from an applications perspective but also because special techniques can be applied in the two party setting which do not apply in the multi-party case. Indeed, secure multi-party computation (in fact the restricted case of secure function evaluation, where only a single function is evaluated) was first presented in the two-party setting. The original work is often cited as being from one of the two papers of Yao;<ref name="Yao86">Andrew C. Yao, "How to generate and exchange secrets," SFCS '86 Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pp. 162-167, 1986.</ref> although the papers do not actually contain what is now known as [[Garbled circuit|Yao's garbled circuit protocol]].

Yao's basic protocol is secure against semi-honest adversaries and is extremely efficient in terms of number of rounds, which is constant, and independent of the target function being evaluated. The function is viewed as a Boolean circuit, with inputs in binary of fixed length. A Boolean circuit is a collection of gates connected with three different types of wires: circuit-input wires, circuit-output wires and intermediate wires. Each gate receives two input wires and it has a single output wire which might be fan-out (i.e. be passed to multiple gates at the next level). Plain evaluation of the circuit is done by evaluating each gate in turn; assuming the gates have been topologically ordered. The gate is represented as a truth table such that for each possible pair of bits (those coming from the input wires' gate) the table assigns a unique output bit; which is the value of the output wire of the gate. The results of the evaluation are the bits obtained in the circuit-output wires.

Yao explained how to garble a circuit (hide its structure) so that two parties, sender and receiver, can learn the output of the circuit and nothing else. At a high level, the sender prepares the garbled circuit and sends it to the receiver, who obliviously evaluates the circuit, learning the encodings corresponding to both his and the sender's output. He then just sends back the sender's encodings, allowing the sender to compute his part of the output. The sender sends the mapping from the receivers output encodings to bits to the receiver, allowing the receiver to obtain their output.

In more detail, the garbled circuit is computed as follows. The main ingredient is a double-keyed symmetric encryption scheme. Given a gate of the circuit, each possible value of its input wires (either 0 or 1) is encoded with a random number (label). The values resulting from the evaluation of the gate at each of the four possible pair of input bits are also replaced with random labels. The garbled truth table of the gate consists of encryptions of each output label using its inputs labels as keys. The position of these four encryptions in the truth table is randomized so no information on the gate is leaked.

To correctly evaluate each garbled gate the encryption scheme has the following two properties. Firstly, the ranges of the encryption function under any two distinct keys are disjoint (with overwhelming probability). The second property says that it can be checked efficiently whether a given ciphertext has been encrypted under a given key. With these two properties the receiver, after obtaining the labels for all circuit-input wires, can evaluate each gate by first finding out which of the four ciphertexts has been encrypted with his label keys, and then decrypting to obtain the label of the output wire. This is done obliviously as all the receiver learns during the evaluation are encodings of the bits.

The sender's (i.e. circuit creators) input bits can be just sent as encodings to the evaluator; whereas the receiver's (i.e. circuit evaluators) encodings corresponding to his input bits are obtained via a 1-out-of-2 oblivious transfer (OT) protocol. A 1-out-of-2 OT protocol enables the sender possessing of two values C1 and C2 to send the one requested by the receiver (b a value in {1,2}) in such a way that the sender does not know what value has been transferred, and the receiver only learns the queried value.

If one is considering malicious adversaries, further mechanisms to ensure correct behavior of both parties need to be provided. By construction it is easy to show security for the sender if the OT protocol is already secure against malicious adversary, as all the receiver can do is to evaluate a garbled circuit that would fail to reach the circuit-output wires if he deviated from the instructions. The situation is very different on the sender's side. For example, he may send an incorrect garbled circuit that computes a function revealing the receiver's input. This would mean that privacy no longer holds, but since the circuit is garbled the receiver would not be able to detect this. However, it is possible to efficiently apply Zero-Knowledge proofs to make this protocol secure against malicious adversaries with a small overhead comparing to the semi-honest protocol.<ref name=":0" />

=== Multi-party protocols ===
Most MPC protocols, as opposed to 2PC protocols and especially under the unconditional setting of private channels, make use of secret sharing. In the secret sharing based methods, the parties do not play special roles (as in Yao, of creator and evaluator). Instead, the data associated with each wire is shared amongst the parties, and a protocol is then used to evaluate each gate. The function is now defined as a "circuit" over a finite field, as opposed to the binary circuits used for Yao. Such a circuit is called an arithmetic circuit in the literature, and it consists of addition and multiplication "gates" where the values operated on are defined over a finite field.

Secret sharing allows one to distribute a secret among a number of parties by distributing shares to each party. Two types of secret sharing schemes are commonly used; [[Shamir's Secret Sharing|Shamir secret sharing]] and additive secret sharing. In both cases the shares are random elements of a finite field that add up to the secret in the field; intuitively, security is achieved because any non-qualifying set of shares looks randomly distributed.

Secret sharing schemes can tolerate an adversary controlling up to ''t'' parties out of ''n'' total parties, where ''t'' varies based on the scheme, the adversary can be passive or active, and different assumptions are made on the power of the adversary. The Shamir secret sharing scheme is secure against a passive adversary when <math>t < \frac{n}{2}</math> and an active adversary when <math>t < \frac{n}{3}</math> while achieving information-theoretic security, meaning that even if the adversary has unbounded computational power, they cannot learn any information about the secret underlying a share. The BGW protocol,<ref>{{Cite book|last1=Ben-Or|first1=Michael|last2=Goldwasser|first2=Shafi|last3=Wigderson|first3=Avi|title=Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 |chapter=Completeness theorems for non-cryptographic fault-tolerant distributed computation |date=1988-01-01|publisher=ACM|pages=1–10|doi=10.1145/62212.62213|isbn=978-0897912648|s2cid=207554159}}</ref> which defines how to compute addition and multiplication on secret shares, is often used to compute functions with Shamir secret shares. Additive secret sharing schemes can tolerate the adversary controlling all but one party, that is <math>t < n</math>, while maintaining security against a passive and active adversary with unbounded computational power. Some protocols require a setup phase, which may only be secure against a computationally bounded adversary.

A number of systems have implemented various forms of MPC with secret sharing schemes. The most popular is SPDZ,<ref name="SPDZ">I. Damgård, V. Pastro, N. Smart and S. Zakarias, "Multiparty computation from somewhat homomorphic encryption," Crypto 2012, vol. Springer LNCS 7417, pp. 643-662, 2012.</ref> which implements MPC with additive secret shares and is secure against active adversaries.

=== Other protocols ===

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, and has been successfully implemented in [[Ethereum]].<ref>{{cite journal|author1=Iddo Bentov, Ranjit Kumaresan|title=How to Use Bitcoin to Design Fair Protocols|journal=Cryptology e Print|date=2014|issue=129|pages=1–38|url=https://eprint.iacr.org/2014/129.pdf|access-date=9 October 2014}}</ref><ref>{{cite journal|author1=Mikhail Kalinin, Danny Ryan, Vitalik Buterin|title=EIP-3675: Upgrade consensus to Proof-of-Stake|journal=Ethereum Improvement Proposals|date=2021|url=https://eips.ethereum.org/EIPS/eip-3675|access-date=16 October 2023}}</ref>