Multiparty Homomorphic Encryption from Ring-Learning-with-Errors¶
Authors: Mouchet, Troncoso-Pastoriza, Bossuat, Hubaux
Year: 2021
Venue: PETS 2021
type: scheme collection: catalogue, schemes status: auto
Links: ePrint 2020/304
Visual lesson: Multiparty HE (MHE) for BFV/CKKS · Scheme table row: Multiparty HE (MHE) for BFV/CKKS
Summary¶
Auto-extracted summary (unreviewed)
The paper introduces a multiparty version of the BFV cryptosystem (collective key generation, relinearization-key generation, public-key switching and collective bootstrapping) and uses it as a semi-honest, dishonest-majority MPC solution whose transcript is public, whose offline phase is compact and whose circuit evaluation is non-interactive, reducing per-party communication from quadratic to linear in the number of parties and enabling cloud-outsourced evaluation. Implemented in the open-source Lattigo library, private input selection among 8000 parties completes in 61.7 s with 1.31 MB per party, element-wise vector products with 8 parties run 8.6x faster with 39.3x less communication than the secret-sharing baseline, and Beaver-triple generation for 10 parties yields 20x more triples per second with 136x less communication than an OT-based approach.
Abstract¶
We propose and evaluate a secure-multipartycomputation (MPC) solution in the semi-honest model with dishonest majority that is based on multiparty homomorphic encryption (MHE). To support our solution, we introduce a multiparty version of the Brakerski-Fan-Vercauteren homomorphic cryptosystem and implement it in an open-source library. MHEbased MPC solutions have several advantages: Their transcript is public, their offline phase is compact, and their circuit-evaluation procedure is non-interactive. By exploiting these properties, the communication complexity of MPC tasks is reduced from quadratic to linear in the number of parties, thus enabling secure computation among potentially thousands of parties and in a broad variety of computing paradigms, from the traditional peer-to-peer setting to cloud-outsourcing and smart-contract technologies. MHE-based approaches can also outperform the state-of-the-art solutions, even for a small number of parties. We demonstrate this for three circuits: private input selection with application to private-information retrieval, component-wise vector multiplication with application to private-set intersection, and Beaver multiplication triples generation. For the first circuit, privately selecting one input among eight thousand parties’ (of 32 KB each) requires only 1.31 MB of communication per party and completes in 61.7 seconds. For the second circuit with eight parties, our approach is 8.6 times faster and requires 39.3 times less communication than the current methods. For the third circuit and ten parties, our approach generates 20 times more triples per second while requiring 136 times less communication per-triple than an approach based on oblivious transfer. We implemented our scheme in the Lattigo library and open-sourced the code at github.com/ldsec/lattigo.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | multiparty BFV scheme with collective key generation, relinearization, key switching and bootstrapping protocols | llm | 0.85 |
| contribution | MHE-based MPC in the semi-honest dishonest-majority model with linear communication and non-interactive evaluation | llm | 0.85 |
| contribution | support for peer-to-peer, cloud-outsourced and smart-contract settings with thousands of parties | llm | 0.85 |
| contribution | open-source implementation in the Lattigo library | llm | 0.85 |
| contribution | evaluation on private input selection (PIR), element-wise vector multiplication (PSI) and Beaver triple generation | llm | 0.85 |
| schemes | BFV | llm | 0.85 |
| schemes | multiparty (threshold) homomorphic encryption | llm | 0.85 |
| schemes | secret sharing | llm | 0.85 |
| libraries | Lattigo | llm | 0.85 |
| tasks | private information retrieval | llm | 0.85 |
| tasks | private set intersection | llm | 0.85 |
| tasks | Beaver multiplication triple generation | llm | 0.85 |
| security level | 128-bit | llm | 0.85 |
| threat model | semi-honest with dishonest majority; peer-to-peer or cloud-assisted settings | llm | 0.85 |
| interaction | interactive (HE+MPC) | llm | 0.85 |
| code url | http://github.com/ldsec/lattigo (URL found in the full text) | regex | 0.50 |
| code url | https://git.njit.edu/palisade/PALISADE (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/ldsec/lattigo | llm | 0.85 |
| limitations | rotation-key generation accounts for about 75% of setup cost | llm | 0.85 |
| limitations | for 2 parties the MHE setup costs more time and communication than the baseline's offline phase | llm | 0.85 |
| limitations | parameters depend on circuit depth and thus on the number of parties; large party counts need bigger parameters or collective bootstrapping | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | private input selection: 61.7 s, 1.31 MB communication per party (8000 parties, 32 KB input each) | llm | 0.85 |
| key result | element-wise vector product: 8.6x faster, 39.3x less communication (8 parties vs secret-sharing baseline) | llm | 0.85 |
| key result | Beaver triple generation: 20x more triples per second, 136x less communication per triple (10 parties vs OT-based approach) | llm | 0.85 |
| key result | input selection setup vs baseline offline phase: 5.2x faster, 2.4x less communication (8 parties) | llm | 0.85 |
| key result | plaintext throughput: 105.7 kB/s (baseline 9.0 kB/s), bandwidth 40x plaintext (baseline 3650x) (input selection, 8 parties) | llm | 0.85 |
| key result | end-to-end time: under 1 s (element-wise product, 32 parties) | llm | 0.85 |
Scheme card: Multiparty HE (MHE) for BFV/CKKS¶
| Group | 6. Multi-party FHE (threshold and multi-key) |
| Kind | Scheme |
| Hardness assumption | RLWE |
| Plaintext type | Approximate (CKKS) or exact (BFV) |
| SIMD packing | Yes |
| Bootstrapping | Yes, interactive or collective |
| Post-quantum | Yes |
| Status | Active SOTA |
| Fit for LLM inference | Practical threshold CKKS for jointly protecting data and model weights. |
| Follow-ups | Low-communication threshold FHE from Module-LWE (ASIACRYPT 2025, 2025/409); Shamir-based ThFHE (CCS 2026, 2026/1559); Ajax threshold FHEW (USENIX Security 2026, 2025/1834). |
| Libraries | Lattigo, OpenFHE |
| Follow-up papers in the archive | Low Communication Threshold FHE from Standard (Module-)LWE Revisiting Shamir Secret Sharing for Threshold Fully Homomorphic Encryption Ajax: Fast Threshold Fully Homomorphic Encryption without Noise Flooding |
System card: Threshold / multiparty CKKS (MHE)¶
| Group | 2. CKKS core and variants |
| Family | Threshold RLWE (CKKS/BFV) |
| Arithmetic | Approximate or exact |
| Interaction | Interactive key generation and decryption |
| Model scale | - |
| Status | Active |
| Relation to the SoK | Distributes the CKKS secret key across parties. |
| Note | Used in Lattigo and OpenFHE for federated and collaborative analytics. Fits double-blind model and data privacy. |
| Code | https://github.com/tuneinsight/lattigo |
| Systems page | Threshold / multiparty CKKS (MHE) |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: MPC 108 [p.1], Multiparty HE 102 [p.1], BFV 81 [p.1], Secret sharing 10 [p.1], CKKS 5 [p.4], Multi-key HE 5 [p.3], Threshold HE 3 [p.2], Oblivious transfer 3 [p.1], Zero-knowledge proofs 3 [p.10], BGV 2 [p.4]
- library: MP-SPDZ 8 [p.2], Lattigo 7 [p.1], PALISADE 2 [p.15], Microsoft SEAL 2 [p.15]
- hardware: Intel Xeon 1 [p.11]
- technique: Relinearization 19 [p.4], Key switching 15 [p.5], Semi-honest model 14 [p.1], Rotations 10 [p.8], Bootstrapping 9 [p.1], Non-interactive 5 [p.1], RNS 3 [p.10], Two-party computation 2 [p.12]
- assumption: RLWE 18 [p.1], Lattice-based 7 [p.3], LWE 6 [p.2]
- task: Medical / healthcare 5 [p.1], Genomics 4 [p.14], Finance 2 [p.14]
- topic: Homomorphic encryption 38 [p.1], Open source 9 [p.1], Benchmark 2 [p.10]
Related papers¶
- Low Communication Threshold FHE from Standard (Module-)LWE follow up of this paper — follow-up listed for scheme "Multiparty HE (MHE) for BFV/CKKS"
- Revisiting Shamir Secret Sharing for Threshold Fully Homomorphic Encryption follow up of this paper — follow-up listed for scheme "Multiparty HE (MHE) for BFV/CKKS"
- Ajax: Fast Threshold Fully Homomorphic Encryption without Noise Flooding follow up of this paper — follow-up listed for scheme "Multiparty HE (MHE) for BFV/CKKS"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/2-028_multiparty-homomorphic-encryption-from-ring-learning-with-er.pdf |
catalogue | 18 | 488.1 KB | e9447abeeb38 |
|
references/schemes/s36-0_multiparty-homomorphic-encryption-from-ring-learning-with-er.pdf |
schemes | 18 | 488.1 KB | e9447abeeb38 |
byte-identical to references/catalogue/2-028_multiparty-homomorphic-encryption-from-ring-learning-with-er.pdf |
Database key: multiparty-homomorphic-encryption-from-ring-learning-with-errors · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set multiparty-homomorphic-encryption-from-ring-learning-with-errors COLUMN VALUE