Secure Multiparty Computation

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.

Overview

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

Covered Topics

Feasability Theorems

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
    • for \(t \lt n/2\), every functionality can be securely computed with perfect security [BGW88, CCD88]
    • for \(t \lt n\), assuming oblivious transfer (OT), every functionality can be securely computed with computational security [GMW87]
  • 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.

Sources

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

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

A nice survey to the current (2018) state of MPC research is the mini-book [EKR18].

Literature