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]
Related papers¶
- this paper follow up of Multi-Key Homomorphic Encryption from TFHE — follow-up listed for scheme "Multi-key TFHE"
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