Secure multi-party computation

211:. 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 Oded Goldreich, Silvio Micali, and Avi 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 introduced an approach, known as GMW paradigm, for compiling a multi-party computation protocol which is secure against semi-honest adversaries to a protocol that is secure against malicious adversaries. 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 GMW paradigm was considered to be inefficient for years because of huge overheads that it brings to the base protocol. However, it is shown that it is possible to achieve efficient protocols, and it makes this line of research even more interesting from a practical perspective. 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 561:

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.

844:

authors only report on an implementation of the AES circuit, which has around 50,000 gates. On the other hand, the hardware required here is far more accessible, as similar devices may already be found in many people's desktop computers or games consoles. The authors obtain a timing of 2.7 seconds per AES block on a standard desktop, with a standard GPU. If they allow security to decrease to something akin to covert security, they obtain a run time of 0.30 seconds per AES block. In the passive security case there are reports of processing of circuits with 250 million gates, and at a rate of 75 million gates per second.

744:

a highly non-trivial task. The Fairplay system was the first tool designed to tackle this problem. Fairplay comprises two main components. The first of these is a compiler enabling users to write programs in a simple high-level language, and output these programs in a Boolean circuit representation. The second component can then garble the circuit and execute a protocol to securely evaluate the garbled circuit. As well as two-party computation based on Yao's protocol, Fairplay can also carry out multi-party protocols. This is done using the BMR protocol, which extends Yao's passively secure protocol to the active case.

581:

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.

491:

are not caught. For example, their reputation could be damaged, preventing future collaboration with other honest parties. Thus, protocols that are covertly secure provide mechanisms to ensure that, if some of the parties do not follow the instructions, then it will be noticed with high probability, say 75% or 90%. In a way, covert adversaries are active ones forced to act passively due to external non-cryptographic (e.g. business) concerns. This mechanism sets a bridge between both models in the hope of finding protocols which are efficient and secure enough in practice.

752:

behaviour, many garblings of the same circuit are sent from the constructor to the evaluator. Then around half of them (depending on the specific protocol) are opened to check consistency, and if so a vast majority of the unopened ones are correct with high probability. The output is the majority vote of all the evaluations. Here the majority output is needed. If there is disagreement on the outputs the receiver knows the sender is cheating, but he cannot complain as otherwise this would leak information on his input.

573:

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.

379:

contrast, in the real-world model, there is no trusted party and all the parties can do is to exchange messages with each other. A protocol is said to be secure if one can learn no more about each party's private inputs in the real world than one could learn in the ideal world. In the ideal world, no messages are exchanged between parties, so real-world exchanged messages cannot reveal any secret information.

171:, cryptographic work that simulates game playing/computational tasks over distances without requiring a trusted third party. 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. By the late 1980s, Michael Ben-Or, 36: 590:

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.

836:

is still being generated. The time to compute AES was reduced to 1.4 seconds per block in the active case, using a 512-node cluster machine, and 115 seconds using one node. Shelat and Shen improve this, using commodity hardware, to 0.52 seconds per block. The same paper reports on a throughput of 21 blocks per second, but with a latency of 48 seconds per block.

473:(i.e., when an honest majority is assumed) are different from those where no such assumption is made. This latter case includes the important case of two-party computation where one of the participants may be corrupted, and the general case where an unlimited number of participants are corrupted and collude to attack the honest participants. 569:

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.

482:

this level of security prevent inadvertent leakage of information between (otherwise collaborating) parties, and are thus useful if this is the only concern. In addition, protocols in the semi-honest model are quite efficient, and are often an important first step for achieving higher levels of security.

755:

This approach for active security was initiated by Lindell and Pinkas. This technique was implemented by Pinkas et al. in 2009, This provided the first actively secure two-party evaluation of the Advanced Encryption Standard (AES) circuit, regarded as a highly complex (consisting of around 30,000 AND

743:

One of the main issues when working with Yao-based protocols is that the function to be securely evaluated (which could be an arbitrary program) must be represented as a circuit, usually consisting of XOR and AND gates. Since most real-world programs contain loops and complex data structures, this is

589:

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

560:

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

237:

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

485:

Malicious (Active) Security: In this case, the adversary may arbitrarily deviate from the protocol execution in its attempt to cheat. Protocols that achieve security in this model provide a very high security guarantee. In the case of majority of misbehaving parties: The only thing that an adversary

374:

security verification based on the party knowledge and the protocol correctness. For MPC protocols, the environment in which the protocol operates is associated with the Real World/Ideal World Paradigm. The parties can't be said to learn nothing, since they need to learn the output of the operation,

355:

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

835:

function, whose circuit comprises almost 6 billion gates. To accomplish this they developed a custom, better optimized circuit compiler than Fairplay and several new optimizations such as pipelining, whereby transmission of the garbled circuit across the network begins while the rest of the circuit

789:

As many circuits are evaluated, the parties (including the receiver) need to commit to their inputs to ensure that in all the iterations the same values are used. The experiments of Pinkas et al. reported show that the bottleneck of the protocol lies in the consistency checks. They had to send over

568:

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

565:

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.

552:

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

522:

can be static, where the adversary chooses its victims before the start of the multi-party computation, or dynamic, where it chooses its victims during the course of execution of the multi-party computation making the defense harder. An adversary structure can be defined as a threshold structure or

481:

Semi-Honest (Passive) Security: In this case, it is assumed that corrupted parties merely cooperate to gather information out of the protocol, but do not deviate from the protocol specification. This is a naive adversary model, yielding weak security in real situations. However, protocols achieving

382:

The Real World/Ideal World Paradigm provides a simple abstraction of the complexities of MPC to allow the construction of an application under the pretense that the MPC protocol at its core is actually an ideal execution. If the application is secure in the ideal case, then it is also secure when a

238:

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

680:

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, which defines how to compute addition and multiplication on secret shares, is often used to

490:

Security against active adversaries typically leads to a reduction in efficiency. Covert security is an alternative that aims to allow greater efficiency in exchange for weakening the security definition; it is applicable to situations where active adversaries are willing to cheat but only if they

311:

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

580:

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

843:

to achieve similar levels of parallelism. They utilize oblivious transfer extensions and some other novel techniques to design their GPU-specific protocol. This approach seems to achieve comparable efficiency to the cluster computing implementation, using a similar number of cores. However, the

751:

The approach that so far seems to be the most fruitful in obtaining active security comes from a combination of the garbling technique and the "cut-and-choose" paradigm. This combination seems to render more efficient constructions. To avoid the aforementioned problems with respect to dishonest

747:

In the years following the introduction of Fairplay, many improvements to Yao's basic protocol have been created, in the form of both efficiency improvements and techniques for active security. These include techniques such as the free XOR method, which allows for much simpler evaluation of XOR

398:

Unlike traditional cryptographic applications, such as encryption or signature, one must assume that the adversary in an MPC protocol is one of the players engaged in the system (or controlling internal parties). That corrupted party or parties may collude in order to breach the security of the

386:

The security requirements on an MPC protocol are stringent. Nonetheless, in 1987 it was demonstrated that any function can be securely computed, with security for malicious adversaries and the other initial works mentioned before. Despite these publications, MPC was not designed to be efficient

576:

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

531:

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.)

300:

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:

564:

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

218:

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

572:

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

378:

The Real World/Ideal World Paradigm states two worlds: (i) In the ideal-world model, there exists an incorruptible trusted party to whom each protocol participant sends its input. This trusted party computes the function on its own and sends back the appropriate output to each party. (ii) In

360:

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

369:

A multi-party computation protocol must be secure to be effective. In modern cryptography, the security of a protocol is related to a security proof. The security proof is a mathematical proof where the security of a protocol is reduced to that of the security of its underlying primitives.

510:, where a message sent at a "tick" always arrives at the next "tick", or that a secure and reliable broadcast channel exists, or that a secure communication channel exists between every pair of participants where an adversary cannot read, modify or generate messages in the channel, etc. 351:

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

523:

as a more complex structure. In a threshold structure the adversary can corrupt or read the memory of a number of participants up to some threshold. Meanwhile, in a complex structure it can affect certain predefined subsets of participants, modeling different possible collusions.

219:

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.

476:

Adversaries faced by the different protocols can be categorized according to how willing they are to deviate from the protocol. There are essentially two types of adversaries, each giving rise to different forms of security (and each fits into different real world scenario):

790:

the net about 6,553,600 commitments to various values to evaluate the AES circuit. In recent results the efficiency of actively secure Yao-based implementations was improved even further, requiring only 40 circuits, and a much smaller number of commitments, to obtain

852:

One of the primary applications of secure multi-party computation is allowing analysis of data that is held by multiple parties, or blind analysis of data by third parties without allowing the data custodian to understand the kind of data analysis being performed.

155:

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

553:

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; although the papers do not actually contain what is now known as

502:

It can be computational (i.e. based on some mathematical problem, like factoring) or unconditional, namely relying on physical unavailability of messages on channels (usually with some probability of error which can be made arbitrarily

597:

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.

246:, which took place 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). 486:

can do in the case of dishonest majority is to cause the honest parties to "abort" having detected cheating. If the honest parties do obtain output, then they are guaranteed that it is correct. Their privacy is always preserved.

1802:— 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. 577:

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.

1796:— 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. 316:

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.

707:, 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. 613:

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

375:

and the output depends on the inputs. In addition, the output correctness is not guaranteed, since the correctness of the output depends on the parties’ inputs, and the inputs have to be assumed to be correct.

710:

A number of systems have implemented various forms of MPC with secret sharing schemes. The most popular is SPDZ, which implements MPC with additive secret shares and is secure against active adversaries.

361:

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.

1300:, Dan Lund Christensen, Ivan Damgård, Martin Geisler, Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielse, Jakob Pagter, Michael Schwartzbach and Tomas Toft (2008). 719:

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

215:

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.

249:

In 2020, a number of companies working with secure-multiparty computation founded the MPC alliance with the goal of "accelerate awareness, acceptance, and adoption of MPC technology."

1527:

Y. Lindell and B. Pinkas, "An efficient protocol for secure two-party computation in the presence of malicious adversaries," Eurocrypt 2007, vol. Springer LNCS 4515, pp. 52-78, 2007.

678: 645: 1422:

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.

1238:

Michael Ben-Or, Shafi Goldwasser, Avi Wigderson: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). STOC 1988: 1-10

831:

with many cores. Kreuter, et al. describe an implementation running on 512 cores of a powerful cluster computer. Using these resources they could evaluate the 4095-bit

593:

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;

1488: 1319: 471: 818: 784: 705: 344:. 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. 1332:

Moti Yung: From Mental Poker to Core Business: Why and How to Deploy Secure Computation Protocols? ACM Conference on Computer and Communications Security 2015: 1-2

53: 222:

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

1622: 437: 417: 1372:

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.

1572:

Y. Huang, J. Katz and D. Evans, "Efficient secure two-party computation using symmetric cut-and-choose.," CRYPTO, vol. Springer LNCS 8043, pp. 18-35, 2013.

1518:

B. Pinkas, T. Schneider, N. Smart and S. Williams, "Secure two-party computation is practical," Asiacrypt 2009, vol. Springer LNCS 5912, pp. 250–267, 2009.

1121:

Oded Goldreich, Silvio Micali, Avi Wigderson:How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. STOC 1987: 218-229

756:

and XOR gates), non-trivial function (also with some potential applications), taking around 20 minutes to compute and requiring 160 circuits to obtain a

1607: 1563:

T. Frederiksen and J. Nielsen, "Fast and maliciously secure two-party computation using the GPU, "ACNS 2013, vol. Springer LNCS 7954, pp. 339–356, 2013.

1382:

Ben-Or, Michael; Goldwasser, Shafi; Wigderson, Avi (1988-01-01). "Completeness theorems for non-cryptographic fault-tolerant distributed computation".

387:

enough to be used in practice at that time. Unconditionally or information-theoretically secure MPC is closely related and builds on to the problem of

1545:

B. Kreuter, a. shalet and C.-H. Shen, "Billion gate secure computation with malicious adversaries," USENIX Security Symposium 2012, pp. 285–300, 2012.

1038: 1762: 320:

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

1733:— A library written in C# and C++ that implements several building blocks required for implementing secure multi-party computation protocols. 681:

compute functions with Shamir secret shares. Additive secret sharing schemes can tolerate the adversary controlling all but one party, that is

1808:- project for development of a 'domain specific programming language for secure multiparty computation' and associated cryptographic runtime. 1536:

Y. Lindell, "Fast cut-and-choose based protocols for malicious and covert adversaries," Crypto 2013, vol. Springer LNCS 8043, pp. 1-17, 2013.

1189: 100: 72: 160:

is outside the system of participants (an eavesdropper on the sender and receiver), the cryptography in this model protects participants'

1168:

Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (2020-10-30).

356:

are guaranteed to compute the correct output (a "robust" protocol), or they abort if they find an error (an MPC protocol "with abort").

1399: 1023: 242:. The first large-scale and practical application of multi-party computation was the execution of an electronic double auction in the 79: 1135:, Stuart Haber, Moti Yung: Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model. CRYPTO 1987: 135-155 1085:

A. Shamir, R. Rivest, and L. Adleman, "Mental Poker", Technical Report LCS/TR-125, Massachusetts Institute of Technology, April 1979.

119: 1043: 204: 1832: 1504:

A. Ben-David, N. Nisan and B. Pinkas, "FairplayMP: a system for secure multi-party computation," ACM CCS 2008, pp. 257–266, 2008.

1771:; Secure Information Management and Processing (SIMAP) is a project sponsored by the Danish National Research Agency (archived). 1250:, Michael Ben-Or: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract). STOC 1989: 73-85 86: 1827: 1033: 1768: 1718: 1582: 1048: 199:

Special purpose protocols for specific tasks started in the late 1970s. Later, secure computation was formally introduced as

57: 1153:, Jeroen van de Graaf: Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result. 87-119 68: 1752: 827:

More recently, there has been a focus on highly parallel implementations based on garbled circuits, designed to be run on

239: 1554:

A. Shelat and C.-H. Shen, "Fast two-party secure computation with minimal assumptions," ACM CCS 2013, pp. 523–534, 2013.

541: 200: 1261:

Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung: Perfectly Secure Message Transmission. J. ACM 40(1): 17-47 (1993)

594: 46: 392: 243: 207:, a specific problem which is a Boolean predicate), and in generality (for any feasible computation) in 1986 by 1629: 1008: 840: 507: 231: 227: 157: 828: 223: 93: 1608:"BPC Partners with Allegheny County on New Privacy-Preserving Data Project | Bipartisan Policy Center" 347:

Informally speaking, the most basic properties that a multi-party computation protocol aims to ensure are:

1018: 495: 371: 1659: 650: 617: 519: 1482: 1313: 191:, had published papers showing "how to securely compute any function in the secure channels setting". 1790:— JavascriptMPC A golang MPC framework that can compile Javascript files into garbled circuits. 1053: 1073: 340:

are distinct), that their input is not equal to the maximum, and that the maximum held is equal to

270: 1405: 1345: 1195: 1107:

Andrew Chi-Chih Yao:How to Generate and Exchange Secrets (Extended Abstract). FOCS 1986: 162-167

1028: 212: 1136: 1395: 1185: 1154: 821: 748:

gates, and garbled row reduction, reducing the size of garbled tables with two inputs by 25%.

442: 184: 793: 759: 514:

The set of honest parties that can execute a computational task is related to the concept of

167:

The foundation for secure multi-party computation started in the late 1970s with the work on

17: 1712: 1387: 1177: 1013: 684: 515: 172: 1756: 1170:"Is the Classical GMW Paradigm Practical? The Case of Non-Interactive Actively Secure 2PC" 554: 547: 439:

the number of parties who can be adversarial. The protocols and solutions for the case of

1348:." In Theory of Cryptography Conference, pp. 336-354. Springer, Berlin, Heidelberg, 2004. 1272:

Rafail Ostrovsky, Moti Yung: How to Withstand Mobile Virus Attacks. PODC 1991. pp. 51-59

1150: 188: 1814:- JavaCard Applet implementing Secure Multiparty Key Generation, Signing and Decryption. 1176:. CCS '20. Virtual Event, USA: Association for Computing Machinery. pp. 1591–1605. 1333: 1297: 422: 402: 388: 285:. Participants want to compute the value of a public function on that private data: F(d 1224:

D. Chaum, C. Crepeau & I. Damgard. "Multiparty unconditionally secure protocols".

1821: 1409: 1199: 1174:

Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security

832: 176: 1273: 1262: 1384:

Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88

1095: 168: 152: 1284: 1251: 1213: 1122: 820:

cheating probability. The improvements come from new methodologies for performing

1742: 1793: 1146: 180: 35: 1774: 1108: 839:

Meanwhile, another group of researchers has investigated using consumer-grade

208: 1799: 1811: 1759:). Open-source package for MPC using a customized type of Python coroutines. 1247: 1181: 1132: 1787: 1463: 1212:

Joe Kilian: Founding Cryptography on Oblivious Transfer. STOC 1988: 20-31

1169: 724: 1391: 1433: 720: 395:(VSS), which many secure MPC protocols use against active adversaries. 161: 1748: 723:

network or for fair lottery, and has been successfully implemented in

735:

Many advances have been made on 2PC and MPC systems in recent years.

498:, the security of an MPC protocol can rely on different assumptions: 1623:"Privacy-Preserved Data Sharing for Evidence-Based Policy Decisions" 1730: 1674:"SCAPI: The Secure Computation API Library | BIU Cyber Center" 1358:

Y. Aumann & Y. Lindell. "Security against covert adversaries".

601:

Secret sharing schemes can tolerate an adversary controlling up to

1301: 984: 1736: 1697: 1673: 1724: 1686: 848:

Implementations of secure multi-party computation data analyses

993:

40 protocol variants, focus on machine learning functionality

29: 981:

MP-SPDZ - A versatile framework for multi-party computation

1805: 1346:

A general composition theorem for secure reactive systems

942:

SEPIA - Security through Private Information Aggregation

370:

Nevertheless, it is not always possible to formalize the

312:

with each other, Alice, Bob, and Charlie can still learn

1344:

Michael Backes, Birgit Pfitzmann, and Michael Waidner. "

1713:

VMCrypt- A Java library for scalable secure computation

328:

is the maximum value, whereas Alice and Bob learn (if

1462:

Mikhail Kalinin, Danny Ryan, Vitalik Buterin (2021).

796: 762: 687: 653: 620: 445: 425: 405: 1334:

https://dl.acm.org/citation.cfm?doid=2810103.2812701

1621:Hart, N.R.; Archer, D.W.; Dalton, E. (March 2019). 60:. Unsourced material may be challenged and removed. 812: 778: 699: 672: 639: 465: 431: 411: 1588:. Boston Women's Workforce Council. January 2017 905:Multiple datasets from different county offices 1464:"EIP-3675: Upgrade consensus to Proof-of-Stake" 1285:Is multiparty computation any good in practice? 506:The model might assume that participants use a 1117: 1115: 1434:"How to Use Bitcoin to Design Fair Protocols" 419:be the number of parties in the protocol and 257:In an MPC, a given number of participants, p 8: 1727:A java library for SMC using secret sharing. 1487:: CS1 maint: multiple names: authors list ( 1318:: CS1 maint: multiple names: authors list ( 1500: 1498: 1739:Efficient Multi-Party computation Toolkit. 968:PALISADE - Homomorphic Encryption Library 921: 860: 1583:"Boston Women's Workforce Council Report" 1076:", TOC/CIS groups, LCS, MIT (1996), p. 1. 1039:Privacy-preserving computational geometry 908:Galois and the Bipartisan Policy Center 801: 795: 767: 761: 686: 660: 652: 627: 619: 455: 444: 424: 404: 297:) while keeping their own inputs secret. 120:Learn how and when to remove this message 884:Boston Women's Workforce Council Report 1794:Secure distributed CSP (DisCSP) solvers 1731:MPCLib: Multi-Party Computation Library 1514: 1512: 1510: 1065: 1806:Secure Multiparty Computation Language 1745:A protocol for Virtual Parties in SMC. 1480: 1432:Iddo Bentov, Ranjit Kumaresan (2014). 1311: 1775:MPC From Scratch: Everyone Can Do it! 7: 1163: 1161: 857:Demonstration and Production Systems 58:adding citations to reliable sources 1749:MPyC: Secure Multiparty Computation 673:{\displaystyle t<{\frac {n}{3}}} 640:{\displaystyle t<{\frac {n}{2}}} 1302:"Multiparty Computation Goes Live" 1024:Multi-party fair exchange protocol 25: 1096:Protocols for secure computations 203:(2PC) in 1982 (for the so-called 69:"Secure multi-party computation" 34: 1034:Oblivious Pseudorandom Function 955:SCAPI - Secure Computation API 324:, then Charlie learns that his 45:needs additional citations for 1698:https://mp-spdz.readthedocs.io 1468:Ethereum Improvement Proposals 1049:Privacy-enhancing technologies 555:Yao's garbled circuit protocol 383:real protocol is run instead. 149:privacy-preserving computation 133:Secure multi-party computation 1: 1074:Adaptively Secure Multi-party 824:on the transmitted circuits. 647:and an active adversary when 240:private information retrieval 18:Secure multiparty computation 1687:https://palisade-crypto.org/ 1649:Galois 2018 Technical Report 542:Secure two-party computation 201:secure two-party computation 1044:Yao's Millionaires' Problem 1849: 902:Allegheny County Datasets 545: 539: 1306:Cryptology ePrint Archive 393:verifiable secret sharing 306:F(x, y, z) = max(x, y, z) 244:Danish Sugar Beet Auction 1630:Bipartisan Policy Center 1009:Private set intersection 466:{\displaystyle t<n/2} 391:, and more specifically 232:proactive secret sharing 27:Subfield of cryptography 1833:Cryptographic protocols 1182:10.1145/3372297.3423366 813:{\displaystyle 2^{-40}} 779:{\displaystyle 2^{-40}} 496:cryptographic protocols 253:Definition and overview 224:universal composability 141:multi-party computation 1828:Theory of cryptography 1765:Nick Szabo (archived). 1743:Virtual Parties in SMC 1386:. ACM. pp. 1–10. 1072:Ran Canetti, et al., " 1019:Homomorphic encryption 887:Boston-area employers 814: 786:cheating probability. 780: 701: 700:{\displaystyle t<n} 674: 641: 467: 433: 413: 372:cryptographic protocol 815: 781: 731:Practical MPC systems 702: 675: 642: 609:total parties, where 595:Shamir secret sharing 585:Multi-party protocols 536:Two-party computation 468: 434: 414: 205:Millionaires' Problem 1800:The Fairplay Project 1721:Christian Zielinski. 1054:Differential Privacy 870:Technology Provider 794: 760: 685: 651: 618: 520:Adversary structures 508:synchronized network 443: 423: 403: 365:Security definitions 179:, and independently 54:improve this article 1719:Introduction to SMC 1392:10.1145/62212.62213 1098:(extended abstract) 739:Yao-based protocols 151:) is a subfield of 1441:Cryptology e Print 1308:(Report 2008/068). 1029:Oblivious transfer 937:Still maintained? 918:Software Libraries 890:Boston University 810: 776: 697: 670: 637: 463: 429: 409: 213:oblivious transfer 137:secure computation 1769:The SIMAP project 1763:The God Protocols 1757:Jupyter notebooks 1662:. 25 August 2023. 1283:Claudio Orlandi: 1191:978-1-4503-7089-9 1000: 999: 915: 914: 668: 635: 432:{\displaystyle t} 412:{\displaystyle n} 164:from each other. 130: 129: 122: 104: 16:(Redirected from 1840: 1777:By Stephen Tong. 1700: 1695: 1689: 1684: 1678: 1677: 1670: 1664: 1663: 1656: 1650: 1647: 1641: 1640: 1638: 1636: 1627: 1618: 1612: 1611: 1604: 1598: 1597: 1595: 1593: 1587: 1579: 1573: 1570: 1564: 1561: 1555: 1552: 1546: 1543: 1537: 1534: 1528: 1525: 1519: 1516: 1505: 1502: 1493: 1492: 1486: 1478: 1476: 1474: 1459: 1453: 1452: 1450: 1448: 1438: 1429: 1423: 1420: 1414: 1413: 1379: 1373: 1370: 1364: 1363: 1355: 1349: 1342: 1336: 1330: 1324: 1323: 1317: 1309: 1294: 1288: 1281: 1275: 1270: 1264: 1259: 1253: 1245: 1239: 1236: 1230: 1229: 1221: 1215: 1210: 1204: 1203: 1165: 1156: 1144: 1138: 1130: 1124: 1119: 1110: 1105: 1099: 1092: 1086: 1083: 1077: 1070: 1014:Digital currency 931:Year Introduced 922: 873:Year Introduced 867:Data Custodians 861: 819: 817: 816: 811: 809: 808: 785: 783: 782: 777: 775: 774: 706: 704: 703: 698: 679: 677: 676: 671: 669: 661: 646: 644: 643: 638: 636: 628: 516:access structure 472: 470: 469: 464: 459: 438: 436: 435: 430: 418: 416: 415: 410: 343: 339: 335: 331: 327: 323: 315: 307: 273:, respectively d 228:mobile adversary 173:Shafi Goldwasser 125: 118: 114: 111: 105: 103: 62: 38: 30: 21: 1848: 1847: 1843: 1842: 1841: 1839: 1838: 1837: 1818: 1817: 1784: 1709: 1707:Further reading 1704: 1703: 1696: 1692: 1685: 1681: 1672: 1671: 1667: 1658: 1657: 1653: 1648: 1644: 1634: 1632: 1625: 1620: 1619: 1615: 1606: 1605: 1601: 1591: 1589: 1585: 1581: 1580: 1576: 1571: 1567: 1562: 1558: 1553: 1549: 1544: 1540: 1535: 1531: 1526: 1522: 1517: 1508: 1503: 1496: 1479: 1472: 1470: 1461: 1460: 1456: 1446: 1444: 1436: 1431: 1430: 1426: 1421: 1417: 1402: 1381: 1380: 1376: 1371: 1367: 1357: 1356: 1352: 1343: 1339: 1331: 1327: 1310: 1296: 1295: 1291: 1282: 1278: 1271: 1267: 1260: 1256: 1246: 1242: 1237: 1233: 1223: 1222: 1218: 1211: 1207: 1192: 1167: 1166: 1159: 1145: 1141: 1131: 1127: 1120: 1113: 1106: 1102: 1094:Andrew C. Yao, 1093: 1089: 1084: 1080: 1071: 1067: 1062: 1005: 920: 859: 850: 797: 792: 791: 763: 758: 757: 741: 733: 717: 715:Other protocols 683: 682: 649: 648: 616: 615: 605:parties out of 587: 550: 548:Garbled circuit 544: 538: 529: 441: 440: 421: 420: 401: 400: 367: 341: 337: 333: 329: 325: 321: 313: 305: 296: 292: 288: 284: 280: 276: 268: 264: 260: 255: 197: 135:(also known as 126: 115: 109: 106: 63: 61: 51: 39: 28: 23: 22: 15: 12: 11: 5: 1846: 1844: 1836: 1835: 1830: 1820: 1819: 1816: 1815: 1809: 1803: 1797: 1791: 1783: 1782:External links 1780: 1779: 1778: 1772: 1766: 1760: 1746: 1740: 1734: 1728: 1722: 1716: 1708: 1705: 1702: 1701: 1690: 1679: 1665: 1651: 1642: 1613: 1599: 1574: 1565: 1556: 1547: 1538: 1529: 1520: 1506: 1494: 1454: 1424: 1415: 1401:978-0897912648 1400: 1374: 1365: 1350: 1337: 1325: 1298:Peter Bogetoft 1289: 1276: 1265: 1254: 1240: 1231: 1216: 1205: 1190: 1157: 1139: 1125: 1111: 1100: 1087: 1078: 1064: 1063: 1061: 1058: 1057: 1056: 1051: 1046: 1041: 1036: 1031: 1026: 1021: 1016: 1011: 1004: 1001: 998: 997: 994: 991: 988: 982: 978: 977: 975: 973: 971: 969: 965: 964: 962: 960: 958: 956: 952: 951: 949: 947: 945: 943: 939: 938: 935: 932: 929: 926: 919: 916: 913: 912: 909: 906: 903: 899: 898: 896: 894: 891: 888: 885: 881: 880: 879:Still in use? 877: 874: 871: 868: 865: 858: 855: 849: 846: 822:cut-and-choose 807: 804: 800: 773: 770: 766: 740: 737: 732: 729: 716: 713: 696: 693: 690: 667: 664: 659: 656: 634: 631: 626: 623: 586: 583: 540:Main article: 537: 534: 528: 525: 512: 511: 504: 488: 487: 483: 462: 458: 454: 451: 448: 428: 408: 399:protocol. Let 389:secret sharing 366: 363: 358: 357: 353: 309: 308: 294: 290: 286: 282: 278: 274: 266: 262: 258: 254: 251: 196: 193: 185:Claude Crépeau 128: 127: 42: 40: 33: 26: 24: 14: 13: 10: 9: 6: 4: 3: 2: 1845: 1834: 1831: 1829: 1826: 1825: 1823: 1813: 1810: 1807: 1804: 1801: 1798: 1795: 1792: 1789: 1788:JavascriptMPC 1786: 1785: 1781: 1776: 1773: 1770: 1767: 1764: 1761: 1758: 1754: 1750: 1747: 1744: 1741: 1738: 1735: 1732: 1729: 1726: 1723: 1720: 1717: 1714: 1711: 1710: 1706: 1699: 1694: 1691: 1688: 1683: 1680: 1675: 1669: 1666: 1661: 1660:"Route Fifty" 1655: 1652: 1646: 1643: 1631: 1624: 1617: 1614: 1609: 1603: 1600: 1584: 1578: 1575: 1569: 1566: 1560: 1557: 1551: 1548: 1542: 1539: 1533: 1530: 1524: 1521: 1515: 1513: 1511: 1507: 1501: 1499: 1495: 1490: 1484: 1469: 1465: 1458: 1455: 1442: 1435: 1428: 1425: 1419: 1416: 1411: 1407: 1403: 1397: 1393: 1389: 1385: 1378: 1375: 1369: 1366: 1361: 1354: 1351: 1347: 1341: 1338: 1335: 1329: 1326: 1321: 1315: 1307: 1303: 1299: 1293: 1290: 1287:, ICASSP 2011 1286: 1280: 1277: 1274: 1269: 1266: 1263: 1258: 1255: 1252: 1249: 1244: 1241: 1235: 1232: 1227: 1220: 1217: 1214: 1209: 1206: 1201: 1197: 1193: 1187: 1183: 1179: 1175: 1171: 1164: 1162: 1158: 1155: 1152: 1148: 1143: 1140: 1137: 1134: 1129: 1126: 1123: 1118: 1116: 1112: 1109: 1104: 1101: 1097: 1091: 1088: 1082: 1079: 1075: 1069: 1066: 1059: 1055: 1052: 1050: 1047: 1045: 1042: 1040: 1037: 1035: 1032: 1030: 1027: 1025: 1022: 1020: 1017: 1015: 1012: 1010: 1007: 1006: 1002: 995: 992: 989: 986: 983: 980: 979: 976: 974: 972: 970: 967: 966: 963: 961: 959: 957: 954: 953: 950: 948: 946: 944: 941: 940: 936: 933: 930: 927: 924: 923: 917: 910: 907: 904: 901: 900: 897: 895: 892: 889: 886: 883: 882: 878: 875: 872: 869: 866: 863: 862: 856: 854: 847: 845: 842: 837: 834: 833:edit distance 830: 825: 823: 805: 802: 798: 787: 771: 768: 764: 753: 749: 745: 738: 736: 730: 728: 726: 722: 714: 712: 708: 694: 691: 688: 665: 662: 657: 654: 632: 629: 624: 621: 612: 608: 604: 599: 596: 591: 584: 582: 578: 574: 570: 566: 562: 558: 556: 549: 543: 535: 533: 526: 524: 521: 517: 509: 505: 501: 500: 499: 497: 492: 484: 480: 479: 478: 474: 460: 456: 452: 449: 446: 426: 406: 396: 394: 390: 384: 380: 376: 373: 364: 362: 354: 350: 349: 348: 345: 318: 304: 303: 302: 298: 272: 252: 250: 247: 245: 241: 235: 233: 229: 225: 220: 216: 214: 210: 206: 202: 194: 192: 190: 186: 182: 178: 177:Avi Wigderson 174: 170: 165: 163: 159: 154: 150: 146: 142: 138: 134: 124: 121: 113: 110:February 2024 102: 99: 95: 92: 88: 85: 81: 78: 74: 71: – 70: 66: 65:Find sources: 59: 55: 49: 48: 43:This article 41: 37: 32: 31: 19: 1812:Myst Project 1693: 1682: 1668: 1654: 1645: 1633:. Retrieved 1616: 1602: 1590:. Retrieved 1577: 1568: 1559: 1550: 1541: 1532: 1523: 1483:cite journal 1471:. Retrieved 1467: 1457: 1445:. Retrieved 1440: 1427: 1418: 1383: 1377: 1368: 1359: 1353: 1340: 1328: 1314:cite journal 1305: 1292: 1279: 1268: 1257: 1243: 1234: 1225: 1219: 1208: 1173: 1151:Ivan Damgård 1142: 1128: 1103: 1090: 1081: 1068: 851: 838: 826: 788: 754: 750: 746: 742: 734: 718: 709: 610: 606: 602: 600: 592: 588: 579: 575: 571: 567: 563: 559: 551: 530: 513: 493: 489: 475: 397: 385: 381: 377: 368: 359: 346: 319: 310: 299: 271:private data 269:, each have 256: 248: 236: 221: 217: 198: 189:Ivan Damgård 169:mental poker 166: 153:cryptography 148: 144: 140: 136: 132: 131: 116: 107: 97: 90: 83: 76: 64: 52:Please help 47:verification 44: 1737:EMP-toolkit 1715:Lior Malka. 1635:14 February 1592:14 February 1443:(129): 1–38 1147:David Chaum 996:As of 2023 181:David Chaum 1822:Categories 1473:16 October 1060:References 987:'s Data61 928:Developer 546:See also: 494:Like many 314:F(x, y, z) 209:Andrew Yao 80:newspapers 1447:9 October 1410:207554159 1248:Tal Rabin 1226:Stoc 1988 1200:226228208 1133:Zvi Galil 864:Analysis 803:− 769:− 527:Protocols 158:adversary 1360:TCC 2007 1003:See also 725:Ethereum 293:, ..., d 281:, ..., d 265:, ..., p 721:Bitcoin 503:small). 195:History 162:privacy 94:scholar 1753:Python 1408: 1398: 1198: 1188: 934:Notes 876:Notes 352:alone. 230:as in 187:, and 96: 89: 82: 75: 67: 1755:(and 1725:SEPIA 1626:(PDF) 1586:(PDF) 1437:(PDF) 1406:S2CID 1196:S2CID 990:2018 985:CSIRO 925:Name 911:2018 893:2016 147:) or 101:JSTOR 87:books 1637:2024 1594:2024 1489:link 1475:2023 1449:2014 1396:ISBN 1320:link 1186:ISBN 841:GPUs 829:CPUs 692:< 658:< 625:< 450:< 336:and 175:and 73:news 1751:in 1388:doi 1178:doi 289:, d 277:, d 261:, p 226:or 145:MPC 56:by 1824:: 1628:. 1509:^ 1497:^ 1485:}} 1481:{{ 1466:. 1439:. 1404:. 1394:. 1316:}} 1312:{{ 1304:. 1194:. 1184:. 1172:. 1160:^ 1149:, 1114:^ 806:40 772:40 727:. 557:. 518:. 332:, 234:. 183:, 139:, 1676:. 1639:. 1610:. 1596:. 1491:) 1477:. 1451:. 1412:. 1390:: 1362:. 1322:) 1228:. 1202:. 1180:: 799:2 765:2 695:n 689:t 666:3 663:n 655:t 633:2 630:n 622:t 611:t 607:n 603:t 461:2 457:/ 453:n 447:t 427:t 407:n 342:z 338:z 334:y 330:x 326:z 322:z 295:N 291:2 287:1 283:N 279:2 275:1 267:N 263:2 259:1 143:( 123:) 117:( 112:) 108:( 98:· 91:· 84:· 77:· 50:. 20:)

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Knowledge (XXG)

Secure multi-party computation

Index