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 $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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2020
- Keywords
- FHEMPCGuaranteed Output DeliveryCommunication EfficiencyNIZK
- Contact author(s)
-
sabadrin @ visa com
aayushjain @ cs ucla edu
nmanohar @ cs ucla edu
sahai @ cs ucla edu - History
- 2020-12-09: last of 3 revisions
- 2018-06-06: received
- See all versions
- Short URL
- https://ia.cr/2018/580
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/580, 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}, url = {https://eprint.iacr.org/2018/580} }