A Crash Course on MPC, Part 0
Introduction
Multiparty Computation (MPC) is a very promising technology that enables multiple parties to jointly compute a function on private data, while revealing only the desired output. For example, two parties, Alejandra and Bonifacio (allow me to break the Alice and Bob trend here with two other cool names), may want to determine who has the largest income without leaking the individual amounts, or maybe the CEOs of multiple companies want to vote on some decision without leaking the individual opinions.
The mere fact that these problems can be solved without the need of a trusted third party that receives inputs and provides output, promising not to leak anything, is a surprising and rather paradoxical result. Since its discovery in the 80s, researchers have managed to develop all sorts of protocols with all kinds of security guarantees and efficiency considerations, allowing us to say today that MPC can be considered concretely practical for certain applications and use-cases.
Given the guarantees that MPC can provide, the wide range of applications enabled by this technology, and the large amount of excellent research articles in the field, it is not unreasonable to expect MPC protocols to be overly complex and understandable only by a small elite of researchers and practitioners. This is partially true: Designing an MPC protocol requires great care, security proofs are hard but necessary, and a correct implementation is difficult given the distributed nature of MPC. However, there are a handful of relevant constructions that can be quite easily explained using only ‘simple’ math! These would not be the ones that you want to deploy in practice most likely, but they are definitely robust enough to provide a solid basis to (1) understand some of the core ideas in MPC, and (2) dive deeper into more practical protocols later on.
The goal of this series of posts is to provide the reader with a general and rather solid background on MPC. I will discuss basic terminology that is widely use in the field, and also provide an overview of some of the main results known in the literature (e.g. for which settings MPC protocols with what properties can exist). Also, I will discuss several basic protocols that, as mentioned above, are easy to understand and serve as the basis for more practical constructions.
The ‘course’ is divided into multiple sections, time will determine if these correspond in a one-to-one way to posts:
- Basic terminology and essential results
- A simple protocol based on triples and linear secret-sharing
- Shamir secret-sharing
- A simple t<n/3 protocol with passive security
- Active security for the protocol above
- A simple honest-majority protocol
- Efficient MPC for 3 parties and 1 corruption
- A dishonest majority protocol using MACs
- Instantiating the offline phase in the dishonest majority setting
I think that, together, these topics provide a good overview of the field, and a good starting point for further research. However, I have to say that this does not constitute by any means a solid basis for all of MPC! For example, I am deliberately omitting the relevant topic of Garbled Circuits, and also Fully-Homomorphic Encryption, which are essential to understand other important parts of MPC. I may blog about these, and much more, later on in the future :)
See you all in the upcoming posts!
Update: Posts Published So Far
This is a list of the posts that have been written already. Hopefully, it will keep growing.
- Part 0, Introduction (this post)
- Part 1, Basic Terminology and Essential Results
- Part 2, Two-Party Computation using Beaver/Multiplication Triples
- Part 3, Shamir Secret-Sharing
- Part 4, Honest-Majority MPC with Passive Security
- Part 5, Error Detection and Error Correction
- Part 6: MPC with Active Security for t<n/3
- Part 7: Honest-Majority MPC with Active Security
- Part 8: Two-Party MPC with Active Security
