Secure multiparty computation (MPC), also called secure function evaluation (SFE) is a family of cryptographic constructions in which multiple parties collectively compute a function, with the restriction that no party knows the input of the other parties. These constructions are extremely important, and more general than one might expect. MPC is used in a lot of application scenarios and it has a thriving community[TPMPCW]. In this series, we'll introduce secure multiparty computation to newcomers.
Can we compute on hidden or encrypted data? What may seem weird at first sight is a very important question, both for theoretical and applied cryptography. If we can solve this problem, we could delegate heavy computations to the cloud, without disclosing our data to untrusted compute servers.
It turns out that we can do it, we have the technology. There are essentially two different ways to approach the problem:
- Secure Multiparty Computation (MPC, SFE)
- Fully Homomorphic Encryption (FHE)
In MPC, we essentially share our data among a set of \(n\) compute servers, which will then collaboratively compute the result. Interestingly, we can do so in such a way that so long as fewer than \(t\) out of \(n\) servers collude, no server knows the inputs of the other servers. In other words, so long as a minority of servers collude, the compute servers don't get to know on what data they are actually computing.
In FHE, we encrypt our data, and send it to a single compute server. This server will then compute directly on the encrypted data, and returns an encrypted result. The server doesn't know what it was computing on.
The main difference between MPC and FHE is that in MPC, computations performed by the compute servers are fast, but communications overhead between them is very high. In FHE, computations are very slow, but at least, there is no communications overhead. Currently, the trade off between communications overhead and slowness of computation is in favor of MPC which is already being deployed in some commercial settings[D08], but FHE has been catching up recently by making huge strides forward in practical usability.
In this series, we'll focus on MPC. We start with a theoretical introduction to the field, so we can better appreciate the properties of the various MPC protocols that we will briefly show later. There, we'll also show some pratical application scenarios of MPC. Then, we'll follow a talk by Tal Rabin on MPC by showing how Shamir's Threshold Scheme of secret sharing can be leveraged to SFE-compute additions and multiplications, resulting in the famous BGW Protocol. Instead of algebraic computations, we could also perform SFE computations on Boolean data with Boolean gates. One way to do it is to encrypt the 0 and 1 on each wire of a circuit, and to scramble the truth tables of the gates. This is Yao's Protocol, also called Yao's Garbled Circuit. Another way to do it is the GMW Protocol. Both Yao and GMW use an extremely important cryptographic primitive: Oblivious Transfer (OT), which we'll introduce as well. We'll also learn about Oblivious RAM, where the access patterns to untrusted RAM are hidden from adversaries who would like to reverse-engineer software or cryptanalyze access to, say full-disk encryption schemes.
From a crypto-theoretical point of view, classifying these protocols is in order[LP08]. Depending on the kind of adversary (honest but curious vs. Byzantine/malicious compute servers, see theoretical introduction for these models), different feasability theorems apply (see below).
We'll defer FHE to another series.
Many of the algorithms shown here are essentially circuit-based. The assume that the function to be securely evaluated is already represented as a circuit of boolean or arithmetic gates. Then, they perform transformations on those circuits. While this is fine in theory, implementing this in practice is a little bit tricky. One idea is to leverage the LLVM framework, and do some work on the IR-LLVM intermediate language. An interesting approach is The Oblivious Machine[Keller15].
- Theory of Secure Multiparty Computation
- The Game of Like
- The Sum of Our Earnings
- How to Share a Secret
- The BGW Protocol
- Oblivious Transfer (OT) (work in progress)
- Yao's Garbled Circuit (work in progress)
- The BMR Protocol (work in progress)
- The GMW Protocol (work in progress)
- The TinyOT Protocol (not yet. see video1, video2, slides1, slides2, slides3)
- The SPDZ Protocol (not yet. see video1, video2, slides)
- Oblivious RAM (ORAM, OPRAM) (work in progress)
What kind of security can be achieved with MPC at all? One of the main achievements of cryptology research in the MPC arena was the following set of results[CH17]. Here, \(n\) is the number of parties involved in the MPC protocol (not including the adversary), and \(t \le n\) is the number of parties under the adversary's control:
- Semi-honest setting
- Malicious setting
- for \(t \lt n/3\), every functionality can be securely computed with perfect security [BGW88, CCD88]
- for \(t \lt n/2\), every functionality can be securely computed with statistical security [RB89]
- for \(t \lt n\), every functionality can be securely computed with abort with computational security [GMW87]
These theorems are the main results of theoretical secure multiparty computation. Of course, many more papers have been published since.
Writing this series on MPC has been initially motivated by an excellent and very entertaining 2 parts talk by IBM's Tal Rabin at Technion Computer Engineering 2014 summer school, introducing among others the BGW protocol and FHE. Part 1:
and part 2:
If Tal managed to whet your appetite, you can watch a whole series of talks on MPC at
- The 1st BIU Winter School on Cryptography which was dedicaded to Secure Computation and Efficiency
- The 5th BIU Winter School on Cryptography which was dedicated to Advances in Practical Multiparty Computation
Should you already know secure multiparty computation protocols, the following talk by Benny Pinkas "Set Intersection" (slides) at the The 5th BIU Winter School on Cryptography wraps up this series very nicely with a case study on a real (important) application: computing set intersection privatly.
A very useful collection of MPC resources like books, papers, and software implementations has been assembled by Dragoș Rotaru as
- awesome-mpc on github.com.
A nice survey to the current (2018) state of MPC research is the mini-book [EKR18].
- [TPMPCW] Theory and Practice of Multi-Party Computation Workshops (multipartycomputation.com)
- [BGW88] Michael Ben-Or, Shafi Goldwasser, Avi Wigderson: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (extended abstract), 1988. In STOC '88 Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 1-10. (acm.org (paywalled), full pdf)
- [CCD88] David Chaum, Claude Crépeau, Ivan Damgård: Multiparty Unconditionally Secure Protocols. In STOC '88 Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 11-19. (acm.org (paywalled), full pdf)
- [GMW87] Oded Goldreich, Silvio Micali, Avi Wigderson: How to Play Any Mental Game, or A Completeness Theorem for Protocols with Honest Majority (Extended Abstract). In STOC '87 Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 218-229. (acm.org (paywalled), full pdf via researchgate.net)
- [RB89] Tal Rabin, Michael Ben-Or: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (extended abstract). In STOC '89 Proceedings of the twenty-first annual ACM symposium on Theory of computing pages 73-85. (acm.org (paywalled), full pdf)
- [LP08] Yehuda Lindell, Benny Pinkas: Secure Multiparty Computation for Privacy-Preserving Data Mining (iacr.org, full pdf)
- [HL10] Carmit Hazay, Yehuda Lindell: Efficient Secure Two-Party Protocols, Techniques and Constructions. (springer.com, read with VPN via link.springer.com)
- [D08] Ivan Damgård et al.: Multiparty Computation Goes Live (iacr.org, full pdf)
- [CH17] Ran Cohen and Iftach Heitner: Seminar on Secure Multiparty Computation (intro slides, links to videos and papers)
- [Keller15] Marcel Keller: The Oblivious Machine, or: How to Put the C into MPC. (iacr.org 2015/467, full pdf)
- [EKR18] David Evans, Vladimir Kolesnikov, Mike Rosulek: A Pragmatic Introduction to Secure Multi-Party Computation. NOW Publishers, 2018.