Revisiting Module Lattice-based Homomorphic Encryption and Application to Secure-MPC¶
Authors: Anisha Mukherjee; Sujoy Sinha Roy
Year: 2025
type: technique collection: schemes status: auto
Links: ePrint 2025/1218
Summary¶
Auto-extracted summary (unreviewed)
The paper revisits the module-LWE-based instantiation of CKKS (MLWE-HE), proposing a new relinearization key-generation technique that reduces relinearization key size from quadratic to linear in the module rank without raising relinearization complexity. It then extends MLWE-HE to a multi-group homomorphic encryption (MGHE) framework with flexible access structures and builds an MPC protocol from it with security in the semi-malicious model, validated by a SageMath proof-of-concept.
Abstract¶
Homomorphic encryption (HE) schemes have gained significant popularity in modern privacy-preserving applications across various domains. While research on HE constructions based on learning with errors (LWE) and ring-LWE has received major attention from both cryptographers and software-hardware designers alike, their module-LWE-based counterpart has remained comparatively under-explored in the literature. A recent work provides a module-LWE-based instantiation (MLWE-HE) of the Cheon-Kim-Kim-Song (CKKS) scheme and showcases several of its advantages such as parameter flexibility and improved parallelism. However, a primary limitation of this construction is the quadratic growth in the size of the relinearization keys. Our contribution is two-pronged: first, we present a new relinearization key-generation technique that addresses the issue of quadratic key size expansion by reducing it to linear growth. Second, we extend the application of MLWE-HE in a multi-group homomorphic encryption (MGHE) framework, thereby generalizing the favorable properties of the single-keyed HE to a multi-keyed setting as well as investigating additional flexibility attributes of the MGHE framework.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | relinearization key generation for MLWE-based CKKS with O(r) instead of O(r^2) keys | llm | 0.80 |
| contribution | multi-group homomorphic encryption (MGHE) framework over MLWE-HE combining multi-party and multi-key access structures | llm | 0.80 |
| contribution | flexible access-structure procedures (with and without confidential channels) | llm | 0.80 |
| contribution | MPC protocol from MGHE-MLWE with semi-malicious security proof | llm | 0.80 |
| contribution | SageMath proof-of-concept implementation | llm | 0.80 |
| schemes | CKKS | llm | 0.80 |
| schemes | MLWE-HE (module-LWE CKKS) | llm | 0.80 |
| schemes | multi-group HE | llm | 0.80 |
| schemes | multi-key HE | llm | 0.80 |
| schemes | multi-party HE | llm | 0.80 |
| libraries | SageMath | llm | 0.80 |
| tasks | secure multi-party computation | llm | 0.80 |
| tasks | multi-key homomorphic encryption | llm | 0.80 |
| hardware | MacBook Air, Apple M1 | llm | 0.80 |
| threat model | semi-malicious parties; semi-honest cloud server as evaluator | llm | 0.80 |
| interaction | interactive (HE+MPC) | llm | 0.80 |
| code url | https://github.com/anishamukh/MLWE-MGHE.git (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/tuneinsight/lat (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/Microsoft/SEAL (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/anishamukh/MLWE-MGHE.git | llm | 0.80 |
| limitations | modified relinearization needs more key-ciphertext multiplications (9 vs 6 for r = 2), increasing runtime | llm | 0.80 |
| limitations | no formal timing results reported; proof-of-concept SageMath code is not comparable to optimised RLWE libraries | llm | 0.80 |
| limitations | optimised library for single and multi-client MLWE-HE is still ongoing work | llm | 0.80 |
| limitations | increased error propagation / precision loss with higher module rank; balance between rank and error distribution needs further analysis | llm | 0.80 |
| llm relevance | low | llm | 0.80 |
| key result | relinearization key count: O(r) vs O(r^2) (module rank r, compared with MAM+24 MLWE-HE) | llm | 0.80 |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: MPC 51 [p.1], Multi-key HE 22 [p.1], CKKS 11 [p.1], Hybrid HE / transciphering 5 [p.19], Zero-knowledge proofs 4 [p.24], TFHE 3 [p.1], Multiparty HE 3 [p.1], BFV 2 [p.1], Threshold HE 2 [p.25]
- library: Microsoft SEAL 2 [p.29], Lattigo 1 [p.27], Concrete (Zama) 1 [p.5], MP-SPDZ 1 [p.28]
- hardware: Apple silicon 1 [p.20]
- technique: Relinearization 111 [p.1], Key switching 23 [p.5], RNS 13 [p.5], Malicious model 5 [p.23], Non-interactive 3 [p.12], Modulus switching 2 [p.11], Federated learning 2 [p.24], Secure aggregation 2 [p.24]
- assumption: Module-LWE 155 [p.1], RLWE 40 [p.1], Lattice-based 29 [p.1], LWE 14 [p.1], Post-quantum 2 [p.25]
- topic: Homomorphic encryption 140 [p.1], Open source 3 [p.20]
Related papers¶
- this paper follow up of ModHE: Modular Homomorphic Encryption Using Module Lattices: Potentials and Limitations — follow-up listed for scheme "Module-LWE HE (ModHE)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s19-1_eprint-2025-1218.pdf |
schemes | 35 | 1.5 MB | 738bd8b0d57d |
Database key: revisiting-module-lattice-based-homomorphic-encryption-and-application · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set revisiting-module-lattice-based-homomorphic-encryption-and-application COLUMN VALUE