Paper 2020/1157

Secure Massively Parallel Computation for Dishonest Majority

Rex Fernando, Ilan Komargodski, Yanyi Liu, and Elaine Shi


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. Both protocols allow the attacker to choose corrupted parties based on the trusted setup, an improvement over Chan et al., whose protocol requires that the CRS is chosen independently of the attacker's choices.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2020
secure computationmassively parallel computationdishonest majority
Contact author(s)
rex1fernando @ gmail com
ilan komargodski @ ntt-research com
yl2866 @ cornell edu
runting @ gmail com
2021-07-12: revised
2020-09-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rex Fernando and Ilan Komargodski and Yanyi Liu and Elaine Shi},
      title = {Secure Massively Parallel Computation for Dishonest Majority},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1157},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.