A few lessons from the history of multiparty computation
As part of my Ph.D. qualifying exam, I gave a survey talk on some of the recent progress in practical multi-party computation (MPC). After the talk, Omer Reingold asked me why so much progress on MPC happened in the last decade or so, given that the main theoretical groundwork for multiparty computation was laid out in the 1980s. Omer’s question got me interested, so I looked at some MPC papers from over the years and talked to a few people who have been working on MPC for some time now. In this post, I want to share some of what I’ve learned about the history of the progress of MPC, a few answers to Omer’s question, and potentially a few takeaways on progress in science more broadly.
To give a bit of background, MPC is one of the most fundamental problems in cryptography. In particular, MPC protocols allow a set of parties, each of which holds its private input, to compute a joint function over their inputs, in a way that protects the confidentiality and integrity of the computation from an adversary that controls a subset of the parties and the communication channels. Defining this precisely requires a lot of care, yet for now, you can think of an MPC protocol as being secure, if the adversary can only cause as much damage as it can in an “ideal world” in which the computation is performed with the aid of a trusted incorruptible party. Intuitively, in such an ideal world, the adversary cannot do much more than choose its inputs, modify its output, or choose not to participate in the computation at all.
In the 1980s, a sequence of works initiated the study of multiparty computation and established very powerful and general results, showing the feasibility of constructing protocols for securely computing any multi-party functionality in a variety of settings. Those results were mostly theoretical. In contrast, the last 15 years saw a growing interest in MPC from a more practical perspective. To put this rising interest in context, consider the following two graphs (data for the graphs is here).
