Paper 2018/580

Threshold Multi-Key FHE and Applications to Round-Optimal MPC

Saikrishna Badrinarayanan and Aayush Jain and Nathan Manohar and Amit Sahai

Abstract

In a multi-key FHE scheme (MFHE), first introduced by Lopez-Alt et al. (STOC '12), and constructed by Clear-Mcgoldrick (CRYPTO '15) and Mukherjee-Wichs (EUROCRYPT '16), 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 some cases, it may be useful 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). We give a formal definition and present a construction for any access structure given by a monotone boolean formula, assuming LWE. Using TMFHE, we present a new result for MPC. We revisit the threshold mixed adversary model with guaranteed output delivery proposed by Fitzi et al. (CRYPTO '98, ASIACRYPT '99) and present the first round-optimal (three-round) MPC protocol in this model, assuming LWE. Our protocol simultaneously achieves all of the following properties: - Security against the maximum number of corruptions under which guaranteed output delivery is achievable. - Communication complexity proportional only to the depth of the circuit being evaluated. - Reusability (given the transcript of the first two rounds, the third round can be repeated to compute an arbitrary number of functionalities on the parties' inputs). - Input fidelity (the functionality is computed with respect to the inputs of all parties that send messages in the first two rounds even if they abort in round 3). Along the way to obtaining the above MPC result, we also construct the first multi-string NIZK from LWE which may be of independent interest. Indeed, we also achieve a simulation-extractable multi-string NIZK from LWE.

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