Paper 2018/580

Secure MPC: Laziness Leads to GOD

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

Abstract

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 $p{k}_i$ can be "expanded" so that the resulting ciphertext is encrypted with respect to a set of public keys $(p{k}_1,..,p{k}_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 $s{k}_i$ (corresponding to the public key $p{k}_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 $$ out of $$). 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.