MPC for Everyone

The age of internet of things, where each device and application double up as a source of data has led to an unprecedented influx of data and analyzing this data is becoming increasingly useful. Given its sensitive nature, there is a growing demand for better and more efficient data collection and computation techniques that respect privacy. Most existing techniques for privacy-preserving computations incur large overheads, limiting platforms that can be used for performing such heavy-duty computations. Moreover, using such platforms for all computations, accumulates power with organizations that own these platforms and creates central targets of failure. This necessitates the need for distributing work and power when computing on private data. Powerful and well-studied cryptographic notions such as secure multiparty computation (MPC) help distribute power by enabling privacy-preserving collaboration between mutually distrusting entities for complex computations on data. Unfortunately, modern MPC protocols have unaccommodating participation models. In general, parties participating in such protocols are required to perform large computations and are expected to stay active throughout the execution. However, unlike large organizations, not everyone might have the resources to carry out such large-scale and long-drawn computations. In this dissertation, our goal is to democratize such computations by designing MPC protocols that empower regular people and smaller organizations to emulate large-scale computations in a distributed manner. We make progress in two different directions. In the first part of this dissertation, we incentivize more participation in an MPC protocol by effectively “distributing” the work amongst parties. In most known protocols, computation and communication amongst parties increases as the number of participants increase. We propose a new MPC protocol, where the per-party work decreases as the number of parties increase. As a result, when run with a large number of parties, the burden on each individual participant is significantly reduced – enabling efficient large-scale MPC computations, involving hundreds and thousands of participants. Including more participants also dilutes the power of each individual party, which is highly desirable. In the second part of this dissertation, we introduce a new participation model called Fluid MPC. Unlike all existing protocols, where participants are required to remain online throughout the execution, in this model, one can design protocols that allow parties to leave and join the protocol execution as they wish. The minimum amount of work that a party is required to do in order to participate is extremely small in comparison to the size of the entire computation. This extreme flexibility allows parties – including those with low resources and limited time – to contribute according to their computational capacity and effectively yields a weighted, privacy-preserving, distributed computing system