Paper 2020/240

MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture

T-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin, and Elaine Shi


Massively Parallel Computation (MPC) is a model of computation widely believed to best capture realistic parallel computing architectures such as large-scale MapReduce and Hadoop clusters. Motivated by the fact that many data analytics tasks performed on these platforms involve sensitive user data, we initiate the theoretical exploration of how to leverage MPC architectures to enable efficient, privacy-preserving computation over massive data. Clearly if a computation task does not lend itself to an efficient implementation on MPC even without security, then we cannot hope to compute it efficiently on MPC with security. We show, on the other hand, that any task that can be efficiently computed on MPC can also be securely computed with comparable efficiency. Specifically, we show the following results: • any MPC algorithm can be compiled to a communication-oblivious counterpart while asymp- totically preserving its round and space complexity, where communication-obliviousness ensures that any network intermediary observing the communication patterns learn no information about the secret inputs; • assuming the existence of Fully Homomorphic Encryption with a suitable notion of compact- ness and other standard cryptographic assumptions, any MPC algorithm can be compiled to a secure counterpart that defends against an adversary who controls not only intermediate network routers but additionally up to 1/3 − η fraction of machines (for an arbitrarily small constant η) — moreover, this compilation preserves the round complexity tightly, and preserves the space complexity upto a multiplicative security parameter related blowup. As an initial exploration of this important direction, our work suggests new definitions and proposes novel protocols that blend algorithmic and cryptographic techniques.

Available format(s)
Publication info
Published elsewhere. MINOR revision.ITCS 2020
Massively Parallel ComputationMulti-Party Computation
Contact author(s)
runting @ gmail com
2020-02-25: received
Short URL
Creative Commons Attribution


      author = {T-H.  Hubert Chan and Kai-Min Chung and Wei-Kai Lin and Elaine Shi},
      title = {MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture},
      howpublished = {Cryptology ePrint Archive, Paper 2020/240},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.