Paper 2018/580

Secure MPC: Laziness Leads to GOD

Saikrishna Badrinarayanan, Aayush Jain, Nathan Manohar, and Amit Sahai


Motivated by what we call "honest but lazy‚" parties in the context of secure multi party computation, we revisit the notion of multi-key FHE schemes (MFHE). In MFHE, any message encrypted using a public key $pk_i$ can be "expanded" so that the resulting ciphertext is encrypted with respect to a set of public keys $(pk_1,..,pk_n)$. Such expanded ciphertexts can be homomorphically evaluated with respect to any circuit to generate a ciphertext $ct$. Then, this ciphertext $ct$ can be partially decrypted using a secret key $sk_i$ (corresponding to the public key $pk_i$) to produce a partial decryption $p_i$. Finally, these partial decryptions $\{p_{i}\}_{i\in [n]}$ can be combined to recover the output. However, this definition of MFHE works only for $n$-out-of-$n$ access structures and, thus, each node in the system is a point of failure. In the context of "honest but lazy‚" parties, it is necessary to be able to decrypt even when only given a subset of partial decryptions (say $t$ out of $n$). In order to solve this problem, we introduce a new notion of multi-key FHE designed to handle arbitrary access patterns that can reconstruct the output. We call it a threshold multi-key FHE scheme (TMFHE). \\ Our main contributions are the following: We formally define and construct TMFHE for any access structure given by a monotone boolean formula, assuming LWE. We construct the first simulation-extractable multi-string NIZK from polynomially hard LWE. We use TMFHE and our multi-string NIZK to obtain the first round-optimal (three round) MPC protocol in the plain model with guaranteed output delivery secure against malicious adversaries or, more generally, mixed adversaries (which supports "honest but lazy‚" parties), assuming LWE. Our MPC protocols simultaneously achieve security against the maximum number of corruptions under which guaranteed output delivery is achievable, depth-proportional communication complexity, and reusability.

Note: Added a new result on multi-string NIZKs from LWE, enabling us to obtain our round-optimal MPC result from only LWE.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2020
FHEMPCGuaranteed Output DeliveryCommunication EfficiencyNIZK
Contact author(s)
sabadrin @ visa com
aayushjain @ cs ucla edu
nmanohar @ cs ucla edu
sahai @ cs ucla edu
2020-12-09: last of 3 revisions
2018-06-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Saikrishna Badrinarayanan and Aayush Jain and Nathan Manohar and Amit Sahai},
      title = {Secure MPC: Laziness Leads to GOD},
      howpublished = {Cryptology ePrint Archive, Paper 2018/580},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.