Skip to content

Two Round Multiparty Computation via Multi-Key FHE

Year: 2015

type: technique collection: schemes status: auto

Links: ePrint 2015/345

Summary

Auto-extracted summary (unreviewed)

Mukherjee and Wichs construct a general MPC protocol with the optimal two rounds of interaction in the common random string model, relying only on LWE for honest-but-curious security and additionally on NIZKs for fully malicious security, whereas prior work needed three rounds or indistinguishability obfuscation. The construction is a simplified LWE-based multi-key FHE built on GSW with a masking scheme, extended with a one-round threshold (distributed) decryption. Each party broadcasts an encryption of its input, everyone homomorphically evaluates the function on the multi-key ciphertext, and partial decryptions are broadcast and combined to recover the output.

Abstract

We construct a general multiparty computation (MPC) protocol with only two rounds of interaction in the common random string model, which is known to be optimal. In the honestbut-curious setting we only rely on the learning with errors (LWE) assumption, and in the fully malicious setting we additionally assume the existence of non-interactive zero knowledge arguments (NIZKs). Previously, Asharov et al. (EUROCRYPT ’12) showed how to achieve three rounds based on LWE and NIZKs, while Garg et al. (TCC ’14) showed how to achieve the optimal two rounds based on indistinguishability obfuscation, but it was unknown if two rounds were possible under standard assumptions without obfuscation. Our approach relies on multi-key fully homomorphic encryption (MFHE), introduced by Lopez-Alt et al. (STOC ’12), which enables homomorphic computation over data encrypted under different keys. We present a construction of MFHE based on LWE that significantly simplifies a recent scheme of Clear and McGoldrick (CRYPTO ’15). We then extend this construction to allow for a one-round distributed decryption of a multi-key ciphertext. Our entire MPC protocol consists of the following two rounds: 1. Each party individually encrypts its input under its own key and broadcasts the ciphertext. All parties can then homomorphically compute a multi-key encryption of the output. 2. Each party broadcasts a partial decryption of the output using its secret key. The partial decryptions can be combined to recover the output in plaintext. ∗University of California, Berkeley. E-mail: pratyay85@gmail.com. Research supported in part from DARPA Safeware Award W911NF15C0210, AFOSR Award FA9550-15-1-0274 and NSF CRII Award 1464397. The views expressed are those of the author and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, or the U.S. Government. Part of the work was done when this author was a PhD Fellow at Aarhus University supported by ERC starting grant 279447, the CTIC and CFEM research center (under the Sino-Danish grant no. 61061130540) †Northeastern University. E-mail: wichs@ccs.neu.edu. Research supported by NSF grants CNS-1347350, CNS- 1314722, CNS- 1413964. Contents
Source: pdf

Extracted details

Field Value Source Confidence
contribution two-round MPC in the CRS model from LWE (semi-honest) and LWE plus NIZKs (malicious) llm 0.85
contribution simplified construction of multi-key FHE from LWE based on GSW, simplifying Clear-McGoldrick llm 0.85
contribution GSW masking scheme (UniEnc / Extend) for extending ciphertexts to multiple keys llm 0.85
contribution one-round threshold decryption for multi-key ciphertexts with simulation security llm 0.85
contribution protocols secure against exactly N-1 corruptions and extended to arbitrarily many corruptions in the UC framework llm 0.85
schemes multi-key FHE llm 0.85
schemes GSW llm 0.85
schemes LWE llm 0.85
schemes NIZK llm 0.85
tasks general secure multiparty computation llm 0.85
threat model honest-but-curious (LWE only) and fully malicious (LWE + NIZK); static corruptions, UC framework, common random string model llm 0.85
interaction interactive (HE+MPC) llm 0.85
limitations requires the common random string model llm 0.85
limitations fully malicious security additionally assumes non-interactive zero-knowledge arguments llm 0.85
llm relevance low llm 0.85
key result round complexity: 2 rounds (optimal) (general MPC in the common random string model) llm 0.85
key result assumptions: LWE for semi-honest security; LWE + NIZK for malicious security (versus 3 rounds from LWE + NIZK (Asharov et al.) and 2 rounds from iO (Garg et al.)) llm 0.85

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: GSW 92 [p.2], MPC 58 [p.1], Threshold HE 33 [p.2], Multi-key HE 31 [p.1], Zero-knowledge proofs 4 [p.3], Oblivious transfer 2 [p.3]
  • technique: Malicious model 29 [p.2], Semi-honest model 11 [p.3], Bootstrapping 5 [p.2], Non-interactive 4 [p.1], Two-party computation 2 [p.30]
  • assumption: LWE 27 [p.1], Lattice-based 6 [p.9]
  • topic: Homomorphic encryption 61 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s38-1_eprint-2015-345.pdf schemes 33 473.3 KB 51023005e932

Database key: two-round-multiparty-computation-via-multi-key-fhe · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set two-round-multiparty-computation-via-multi-key-fhe COLUMN VALUE