Skip to content

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]

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