Skip to content

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]

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