International Association for Cryptologic Research

International Association
for Cryptologic Research


Secure Massively Parallel Computation for Dishonest Majority

Rex Fernando
Ilan Komargodski
Yanyi Liu
Elaine Shi
Search ePrint
Search Google
Abstract: This work concerns secure protocols in the massively parallel computation (MPC) model, which is one of the most widely-accepted models for capturing the challenges of writing protocols for the types of parallel computing clusters which have become commonplace today (MapReduce, Hadoop, Spark, etc.). Recently, the work of Chan et al. (ITCS ’20) initiated this study, giving a way to compile any MPC protocol into a secure one in the common random string model, achieving the standard secure multi-party computation definition of security with up to 1/3 of the parties being corrupt. We are interested in achieving security for much more than 1/3 corruptions. To that end, we give two compilers for MPC protocols, which assume a simple public-key infrastructure, and achieve semi-honest security for all-but-one corruptions. Our first compiler assumes hardness of the learning-with-errors (LWE) problem, and works for any MPC protocol with “short” output—that is, where the output of the protocol can fit into the storage space of one machine, for instance protocols that output a trained machine learning model. Our second compiler works for any MPC protocol (even ones with a long output, such as sorting) but assumes, in addition to LWE, indistinguishability obfuscation and a circular secure variant of threshold FHE.
Video from TCC 2020
  title={Secure Massively Parallel Computation for Dishonest Majority},
  booktitle={Theory of Cryptography},
  author={Rex Fernando and Ilan Komargodski and Yanyi Liu and Elaine Shi},