Secure multi-party computation: Difference between revisions

Revision as of 12:28, 14 February 2024

Latest revision as of 12:11, 5 August 2025

(37 intermediate revisions by 19 users not shown)

Line 1:

{{short description|Subfield of  cryptography}}

'''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.<ref>{{cite web |last1=Evans |first1=David |last2=Kolesnikov |first2=Vladimir |last3=Rosulek |first3=Mike |title=A Pragmatic Introduction to Secure Multi-Party Computation |url=https://securecomputation.org/docs/pragmaticmpc.pdf |website=securecomputation.org |access-date=19 October 2024 |language=en-us |date=2018|archive-url=https://web.archive.org/web/20240812213844/https://securecomputation.org/docs/pragmaticmpc.pdf|archive-date=2024-08-12}}</ref> Unlike traditional cryptographic tasks, where cryptography assures security and integrity of communication or storage and the [[Adversary (cryptography)|adversary]] is outside the system of participants (an eavesdropper on the sender and receiver), the cryptography in this model protects participants' [[privacy]] from each other.

The foundation for secure multi-party computation started in the late 1970s with the work on [[mental poker]], 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]], [[Shafi Goldwasser]] and [[Avi Wigderson]], and independently [[David Chaum]], [[Claude Crépeau]], and [[Ivan Damgård]], had published papers showing "how to securely compute any function in the secure channels setting".<ref>Ran Canetti, et al., "[http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-682.pdf Adaptively Secure Multi-party]", TOC/CIS groups, LCS, MIT (1996), p. 1.</ref>

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

Line 13:

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

Line 20:

== Definition and overview ==

{{unreferenced section|date=October 2024}}

In an MPC, a given number of participants, p₁, p₂, ..., p_N, each have [[information privacy|private data]], respectively d₁, d₂, ..., d_N. Participants want to compute the value of a public function on that private data: F(d₁, d₂, ..., d_N) while keeping their own inputs secret.

Line 36 ⟶ 38:

== Security definitions ==

{{More citations needed section|date=October 2024}}

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. Nevertheless, it is not always possible to formalize the [[cryptographic protocol]] 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.<ref name="BPW">Michael Backes, Birgit Pfitzmann, and Michael Waidner. "[https://link.springer.com/chapter/10.1007/978-3-540-24638-1_19 A general composition theorem for secure reactive systems]." In Theory of Cryptography Conference, pp. 336-354. Springer, Berlin, Heidelberg, 2004.</ref> The parties can't be said to learn nothing, since they need to learn the output of the operation, 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.

Line 61 ⟶ 63:

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

Line 125 ⟶ 128:

! Still in use?

|-

|Boston Women's Workforce Council Report<ref name=BWW_1>{{cite web| title=Boston Women's Workforce Council Report| url=https://www.boston.gov/sites/default/files/document-file-09-2017/bwwcr-2016-new-report.pdf| {{Barepublisher=Boston URLWomen's PDFWorkforce Council| date=SeptemberJanuary 2017| access-date=14 February 20222024}}</ref>

|Boston-area employers

|Boston University

Line 132 ⟶ 135:

|

|-

|Allegheny County Datasets<ref>{{cite web | url=https://bipartisanpolicy.org/press-release/bpc-partners-with-allegheny-county-on-new-privacy-preserving-data-project/ | title=BPC Partners with Allegheny County on New Privacy-Preserving Data Project &#124; Bipartisan Policy Center }}</ref><ref name=PPD_1>{{cite web| title=Privacy-Preserved Data Sharing for Evidence-Based Policy Decisions| author1=Hart, N.R.| author2=Archer, D.W.| author3=Dalton, E.| url=https://bipartisanpolicy.org/wp-content/uploads/2019/06/Privacy-Preserved-Data-Sharing-for-Evidence-Based-Policy-Decisions.pdf {{Bare| URLpublisher=[[Bipartisan PDFPolicy Center]]| date=SeptemberMarch 2019| access-date=14 February 20222024}}</ref><ref>Galois 2018 Technical Report</ref><ref>{{cite web | url=https://gcn.com/articles/2019/05/31/secure-multiparty-computation.aspx | title=Route Fifty | date=25 August 2023 }}</ref>

|Multiple datasets from different county offices

|Galois and the Bipartisan Policy Center

Line 153 ⟶ 156:

|

|-

| SCAPI - Secure Computation API<ref>{{cite web | url=https://cyber.biu.ac.il/scapi/ | title=SCAPI: The Secure Computation API Library &#124; BIU Cyber Center | access-date=2022-09-29 | archive-date=2023-06-04 | archive-url=https://web.archive.org/web/20230604033408/https://cyber.biu.ac.il/scapi/ | url-status=dead }}</ref>

|

|

Line 159 ⟶ 162:

|

|-

| PALISADE - Homomorphic Encryption Library<ref>{{Cite web | title=PALISADE / PALISADE Release · GitLab | url=https://palisade-crypto.org/ | access-date=2025-01-07 | website=palisade-crypto.org}}</ref>

|

|

Line 165 ⟶ 168:

|

|-

| MP-SPDZ - A versatile framework for multi-party computation <ref>{{Cite web | title=Welcome to MP-SPDZ's documentation! — MP-SPDZ documentation | url=https://mp-spdz.readthedocs.io | access-date=2025-01-07 | website=mp-spdz.readthedocs.io}}</ref>

| [[CSIRO]]'s Data61

| 2018

| 40 protocol variants, focus on machine learning functionality

| As of 2023

|}

=== Hardware implementations ===

{| class="sortable wikitable" style="text-align: left"

|-

! Name

! Developer

! Year Introduced

! Notes

! Still maintained?

|-

| Trident MPC

|[https://www.i4p.com/products/trident-mpc/ i4p informatics ltd.]

| 2019

|the first [[Common Criteria]] EAL4+ certified, physical [[Hardware security module|Hardware Security Module]] on the market designed to apply Secure Multi-party Computation (SMPC) for Cryptographic Key Management.

|As of 2024

|}

Line 206 ⟶ 193:

-->

== ExternalFurther linksreading ==

* [https://web.archive.org/web/20140512222113/http://www.cs.ut.ee/~lipmaa/crypto/link/mpc/ Helger Lipmaa's links about multiparty computation]

* [http://www.lior.ca/publications/VMCrypt_Manual_Rev1.0.pdf VMCrypt]- A Java library for scalable secure computation.] By Lior Malka.

* {{webarchive |url=https://web.archive.org/web/20061230075325/http://www.theiia.org/ITAudit/index.cfm?act=itaudit.archive&fid=216 |date=December 30, 2006 |title=Nick Szabo, "The God Protocols" }}

* [https://github.com/czielinski/secmultipartycomp/blob/master/slides/sec_multi_party_comp.pdf Introduction to SMC] onChristian GitHubZielinski.

* [https://github.com/emp-toolkit EMP-toolkit] &mdash; Efficient Multi-Party computation Toolkit. Includes implementation of basic MPC primitives as well as protocols with semi-honest security and malicious security.

* [http://www.sepia.ee.ethz.ch/ SEPIA] A java library for SMC using secret sharing. Basic operations are optimized for large numbers of parallel invocations (code available under the [[LGPL]]).

* [https://github.com/sjehan/JavascriptMPC JavascriptMPC] &mdash; JavascriptMPC A golang MPC framework that can compile Javascript files into garbled circuits.

* [https://github.com/mahdiz/mpclib MPCLib: Multi-Party Computation Library] &mdash; A library written in C# and C++ that implements several building blocks required for implementing secure multi-party computation protocols. MPCLib has a discrete-event simulation engine that can be used for simulating MPC protocols in virtual networks.

* [https://github.com/emp-toolkit EMP-toolkit] &mdash; Efficient Multi-Party computation Toolkit. Includes implementation of basic MPC primitives as well as protocols with semi-honest security and malicious security.

* [https://doi.org/10.1007%2F978-3-642-02617-1_42 Virtual Parties in SMC] A protocol for Virtual Parties in SMC (Secure Multi Party computation).

* [https://www.win.tue.nl/~berry/mpyc/ MPyC]: Secure Multiparty Computation] in [[Python (programming language)|Python]] (and [[Project Jupyter|Jupyter notebooks]]) &mdash;. Open-source package for MPC using a customized type of Python coroutines, supporting advanced applications such as ID3 decision trees, linear programming, CNN/MLP neural networks, AES, one-way hash chains, and many more. Launched in May 2018.

* {{webarchive |url=[https://web.archive.org/web/20061230075325/http://www.theiia.org/ITAudit/index.cfm?act=itaudit.archive&fid=216 |date=DecemberThe 30,God 2006Protocols] |title=Nick Szabo, "The God Protocols" }}(archived).

* [https://web.archive.org/web/20110105121420/http://alexandra.dk/uk/Projects/Pages/SIMAP.aspx The SIMAP project]; Secure Information Management and Processing (SIMAP) is a project sponsored by the Danish National Research Agency aimed implementing Secure Multiparty Computation(archived).

* [https://www.zellic.io/blog/mpc-from-scratch/ MPC From Scratch: Everyone Can Do it!] By Stephen Tong.

== External links ==

* [https://github.com/sjehan/JavascriptMPC JavascriptMPC] &mdash; JavascriptMPC A golang MPC framework that can compile JavascriptJavaScript files into garbled circuits.

* [http://www.cs.fit.edu/~msilaghi/pages/secure/ Secure distributed CSP (DisCSP) solvers] &mdash; 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.

* [http://www.lior.ca/publications/VMCrypt_Manual_Rev1.0.pdf VMCrypt] A Java library for scalable secure computation. By Lior Malka.

* [http://www.cs.huji.ac.il/project/Fairplay/ The Fairplay Project] &mdash; 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.

* [https://web.archive.org/web/20110105121420/http://alexandra.dk/uk/Projects/Pages/SIMAP.aspx The SIMAP project]; Secure Information Management and Processing (SIMAP) is a project sponsored by the Danish National Research Agency aimed implementing Secure Multiparty Computation.

* [http://www.brics.dk/SMCL/ Secure Multiparty Computation Language] - project for development of a '___domain specific programming language for secure multiparty computation' and associated cryptographic runtime.

* [https://www.win.tue.nl/~berry/mpyc/ MPyC]: Secure Multiparty Computation in [[Python (programming language)|Python]] (and [[Project Jupyter|Jupyter notebooks]]) &mdash; Open-source package for MPC using a customized type of Python coroutines, supporting advanced applications such as ID3 decision trees, linear programming, CNN/MLP neural networks, AES, one-way hash chains, and many more. Launched in May 2018.

* [https://sharemind.cyber.ee/ Sharemind: analyze confidential data without compromising privacy] &mdash; A distributed virtual machine with the capability to run privacy-preserving operations. Has a privacy-preserving programming language for data mining tools. Includes developer tools.

* [https://github.com/mahdiz/mpclib MPCLib: Multi-Party Computation Library] &mdash; A library written in C# and C++ that implements several building blocks required for implementing secure multi-party computation protocols. MPCLib has a discrete-event simulation engine that can be used for simulating MPC protocols in virtual networks.

* [https://doi.org/10.1007%2F978-3-642-02617-1_42 Virtual Parties in SMC] A protocol for Virtual Parties in SMC (Secure Multi Party computation)

* [http://www.sepia.ee.ethz.ch/ SEPIA] A java library for SMC using secret sharing. Basic operations are optimized for large numbers of parallel invocations (code available under the [[LGPL]]).

* [https://github.com/czielinski/secmultipartycomp/blob/master/slides/sec_multi_party_comp.pdf Introduction to SMC] on GitHub

* [https://github.com/OpenCryptoProject/Myst Myst Project] - JavaCard Applet implementing Secure Multiparty Key Generation, Signing and Decryption.

* Essential bibliography [https://web.archive.org/web/20070610082513/http://privacy.cs.cmu.edu/dataprivacy/papers/multipartycomputation/index.html Secure Multiparty Computation]

{{DEFAULTSORT:Secure Multi-Party Computation}}