Editing Secure multi-party computation (section)

== History ==
Special purpose protocols for specific tasks started in the late 1970s.<ref>A. Shamir, R. Rivest, and L. Adleman, "Mental Poker", Technical Report LCS/TR-125, Massachusetts Institute of Technology, April 1979.</ref> Later, secure computation was formally introduced as [[secure two-party computation]] (2PC) in 1982 (for the so-called [[Yao's Millionaires' Problem|Millionaires' Problem]], a specific problem which is a Boolean predicate), and in generality (for any feasible computation) in 1986 by [[Andrew Yao]].<ref name="Yao">Andrew C. Yao, [http://www.cs.wisc.edu/areas/sec/yao1982-ocr.pdf Protocols for secure computations] (extended abstract)</ref><ref>Andrew Chi-Chih Yao:How to Generate and Exchange Secrets (Extended Abstract). FOCS 1986: 162-167 [https://ieeexplore.ieee.org/document/4568207]</ref> 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.<ref name="goldreich_87">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 [http://dl.acm.org/citation.cfm?doid=28395.28420]</ref> 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'<ref>[[Zvi Galil]], Stuart Haber, Moti Yung: Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model. CRYPTO 1987: 135-155
[https://link.springer.com/chapter/10.1007%2F3-540-48184-2_10]</ref> and a protocol that allows one of the parties to hide its input unconditionally.<ref>[[David Chaum]], [[Ivan Damgård]], Jeroen van de Graaf: Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result. 87-119 [https://link.springer.com/chapter/10.1007%2F3-540-48184-2_7]</ref> 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,<ref name=":0">{{Cite book|last1=Abascal|first1=Jackson|last2=Faghihi Sereshgi|first2=Mohammad Hossein|last3=Hazay|first3=Carmit|last4=Ishai|first4=Yuval|last5=Venkitasubramaniam|first5=Muthuramakrishnan|title=Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security |chapter=Is the Classical GMW Paradigm Practical? The Case of Non-Interactive Actively Secure 2PC |date=2020-10-30|chapter-url=https://doi.org/10.1145/3372297.3423366|series=CCS '20|location=Virtual Event, USA|publisher=Association for Computing Machinery|pages=1591–1605|doi=10.1145/3372297.3423366|isbn=978-1-4503-7089-9|s2cid=226228208 }}</ref> 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 [[oblivious transfer]] was shown to be complete for these tasks.<ref>Joe Kilian: Founding Cryptography on Oblivious Transfer. STOC 1988: 20-31 [http://dl.acm.org/citation.cfm?doid=62212.62215]</ref>  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).<ref name="CCD">{{cite journal|author1=D. Chaum, C. Crepeau  |author2=I. Damgard |name-list-style=amp |title=Multiparty unconditionally secure protocols|journal=Stoc 1988}}</ref><ref>Michael Ben-Or, Shafi Goldwasser, Avi Wigderson:
Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). STOC 1988: 1-10</ref> Adding a broadcast channel allows the system to tolerate up to 1/2 misbehaving minority,<ref>[[Tal Rabin]], Michael Ben-Or: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract). STOC 1989: 73-85 [http://dl.acm.org/citation.cfm?doid=73007.73014]</ref> whereas connectivity constraints on the communication graph were investigated in the book Perfectly Secure Message Transmission.<ref>Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung: Perfectly Secure Message Transmission. J. ACM 40(1): 17-47 (1993)[http://dl.acm.org/citation.cfm?doid=138027.138036]</ref>

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 [[Adversary (cryptography)|mobile adversary]] as in [[proactive secret sharing]].<ref>Rafail Ostrovsky, Moti Yung: How to Withstand Mobile Virus Attacks. PODC 1991. pp. 51-59 [http://dl.acm.org/citation.cfm?doid=112600.112605]</ref>

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]].<ref>Claudio Orlandi: [https://web.archive.org/web/20141016035557/http://u.cs.biu.ac.il/~orlandi/icassp-draft.pdf Is multiparty computation any good in practice?], ICASSP 2011</ref> The first large-scale and practical application of multi-party computation was the execution of an electronic double auction in the [[Danish Sugar Beet Auction]], which took place in January 2008.<ref>{{cite journal|url=http://eprint.iacr.org/2008/068|author= [[Peter Bogetoft]], 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|title= Multiparty Computation Goes Live|journal= Cryptology ePrint Archive|issue= Report 2008/068|year=2008}}</ref> 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<ref>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
https://dl.acm.org/citation.cfm?doid=2810103.2812701</ref>).

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