A Crash Course on MPC, Part 0

Introduction

Daniel Escudero
Sep 7, 2020 · 3 min read
Nice view at Guarne — Antioquia, Colombia

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!

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store