Revisiting Module Lattice-based Homomorphic Encryption and Application to Secure-MPC
Authors
Anisha Mukherjee, Sujoy Sinha Roy
Anisha Mukherjee
Graz University of Technology, Graz, Austria
anisha dot mukherjee at tugraz dot at
anisha dot mukherjee at tugraz dot at
Sujoy Sinha Roy
Graz University of Technology, Graz, Austria
sujoy dot sinharoy at tugraz dot at
sujoy dot sinharoy at tugraz dot at
Keywords:
Homomorphic encryption
module lattices
multi-party homomorphic encryption
multi-key homomorphic encryption
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.
References
[ACPS09]
Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. In Shai Halevi, editor, Advances in Cryptology - CRYPTO 2009, pages 595–618, Berlin, Heidelberg. 2009. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-03356-8_35
[AJLA+12]
Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, pages 483–501, Berlin, Heidelberg. 2012. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-29011-4_29
[BDK+21]
Shi Bai, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium. https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions. Proposal to NIST PQC Standardization, Round3. 2021.
[BGK11]
Zvika Brakerski, Shafi Goldwasser, and Yael Tauman Kalai. Black-Box Circular-Secure Encryption beyond Affine Functions. In Yuval Ishai, editor, Theory of Cryptography, pages 201–218, Berlin, Heidelberg. 2011. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-19571-6_13
[BGV11]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. Fully Homomorphic Encryption without Bootstrapping. Electron. Colloquium Comput. Complex., 2011.
[BHHI10]
Boaz Barak, Iftach Haitner, Dennis Hofheinz, and Yuval Ishai. Bounded Key-Dependent Message Security. In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, pages 423–444, Berlin, Heidelberg. 2010. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-13190-5_22
[BJRW23]
Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, and Weiqiang Wen. On the Hardness of Module Learning with Errors with Short Distributions. J. Cryptol., 36(1):1, 2023. DOI: 10.1007/S00145-022-09441-3
[BLS19]
Jonathan Bootle, Vadim Lyubashevsky, and Gregor Seiler. Algebraic Techniques for Short(er) Exact Lattice-Based Zero-Knowledge Proofs. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part I, volume 11692 of Lecture Notes in Computer Science, pages 176–202. 2019. Springer. DOI: 10.1007/978-3-030-26948-7_7
[BS23]
Katharina Boudgoust and Peter Scholl. Simple Threshold (Fully Homomorphic) Encryption from LWE with Polynomial Modulus. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part I, volume 14438 of Lecture Notes in Computer Science, pages 371–404. 2023. Springer. DOI: 10.1007/978-981-99-8721-4_12
[BV11]
Zvika Brakerski and Vinod Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 97-106. 2011. DOI: 10.1109/FOCS.2011.12
[Can01]
Ran Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 136–145. 2001. IEEE Computer Society. DOI: 10.1109/SFCS.2001.959888
[CCS19]
Hao Chen, Ilaria Chillotti, and Yongsoo Song. Multi-Key Homomorphic Encryption from TFHE. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part II, volume 11922 of Lecture Notes in Computer Science, pages 446–472. 2019. Springer. DOI: 10.1007/978-3-030-34621-8_16
[CDKS19]
Hao Chen, Wei Dai, Miran Kim, and Yongsoo Song. Efficient Multi-Key Homomorphic Encryption with Packed Ciphertexts with Application to Oblivious Neural Network Inference. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 395–412, New York, NY, USA. 2019. Association for Computing Machinery. DOI: 10.1145/3319535.3363207
[CDN01]
Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen. Multiparty Computation from Threshold Homomorphic Encryption. In Birgit Pfitzmann, editor, Advances in Cryptology - EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, May 6-10, 2001, Proceeding, volume 2045 of Lecture Notes in Computer Science, pages 280–299. 2001. Springer. DOI: 10.1007/3-540-44987-6_18
[CDW17]
Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Short Stickelberger Class Relations and Application to Ideal-SVP. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology – EUROCRYPT 2017, pages 324–348, Cham. 2017. Springer International Publishing. DOI: 10.1007/978-3-319-56620-7_12
[CGGI20]
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1):34–91, 2020. DOI: 10.1007/S00145-019-09319-X
[CHK+18]
Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. A Full RNS Variant of Approximate Homomorphic Encryption. In Carlos Cid and Michael J. Jacobson Jr., editors, Selected Areas in Cryptography - SAC 2018 - 25th International Conference, Calgary, AB, Canada, August 15-17, 2018, Revised Selected Papers, volume 11349 of Lecture Notes in Computer Science, pages 347–368. 2018. Springer. DOI: 10.1007/978-3-030-10970-7_16
[CKKS17]
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I, volume 10624 of Lecture Notes in Computer Science, pages 409–437. 2017. Springer. DOI: 10.1007/978-3-319-70694-8_15
[CLR17]
Hao Chen, Kim Laine, and Peter Rindal. Fast Private Set Intersection from Homomorphic Encryption. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1243–1255, New York, NY, USA. 2017. Association for Computing Machinery. DOI: 10.1145/3133956.3134061
[CS16]
Ana Costache and Nigel P. Smart. Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?. In Kazue Sako, editor, Topics in Cryptology - CT-RSA 2016, pages 325–340, Cham. 2016. Springer International Publishing. DOI: 10.1007/978-3-319-29485-8_19
[Fer23]
Ramsès Fernàndez-València. Verifiable encodings in multigroup fully homomorphic encryption. CoRR, abs/2303.08432, 2023. DOI: 10.48550/ARXIV.2303.08432
[FH96]
Matthew K. Franklin and Stuart Haber. Joint Encryption and Message-Efficient Secure Computation. J. Cryptol., 9(4):217–232, 1996. DOI: 10.1007/BF00189261
[FTSH20]
David Froelicher, Juan Ramón Troncoso-Pastoriza, Joao Sa Sousa, and Jean-Pierre Hubaux. Drynx: Decentralized, Secure, Verifiable System for Statistical Queries and Machine Learning on Distributed Datasets. IEEE Trans. Inf. Forensics Secur., 15:3035–3050, 2020. DOI: 10.1109/TIFS.2020.2976612
[FV12]
Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. IACR Cryptol. ePrint Arch., 2012.
[Gen09]
Craig Gentry. A Fully Homomorphic Encryption Scheme. PhD thesis. Stanford University, Stanford, CA, USA, 2009.
[GNS23]
Chaya Ganesh, Anca Nitulescu, and Eduardo Soria-Vazquez. Rinocchio: SNARKs for Ring Arithmetic. J. Cryptol., 36(4):41, 2023. DOI: 10.1007/S00145-023-09481-3
[Ins23]
Tune Insight. Lattigo v5. EPFL-LDS, Tune Insight SA. Online: https://github.com/tuneinsight/lattigo. November 2023.
[KLSW24]
Hyesun Kwak, Dongwon Lee, Yongsoo Song, and Sameer Wagh. A General Framework of Homomorphic Encryption for Multiple Parties with Non-interactive Key-Aggregation. In Christina Pöpper and Lejla Batina, editors, Applied Cryptography and Network Security, pages 403–430, Cham. 2024. Springer Nature Switzerland. DOI: 10.1007/978-3-031-54773-7_16
[LPR10]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, pages 1–23, Berlin, Heidelberg. 2010. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-13190-5_1
[LS15]
Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr., 75(3):565–599, 2015. DOI: 10.1007/s10623-014-9938-4
[LTV12]
Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 1219–1234. 2012. ACM. DOI: 10.1145/2213977.2214086
[MAM+24]
Anisha Mukherjee, Aikata, Ahmet Can Mert, Yongwoo Lee, Sunmin Kwon, Maxim Deryabin, and Sujoy Sinha Roy. ModHE: Modular Homomorphic Encryption Using Module Lattices Potentials and Limitations. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2024(1):527–562, 2024. DOI: 10.46586/TCHES.V2024.I1.527-562
[MTBH21]
Christian Mouchet, Juan Ramón Troncoso-Pastoriza, Jean-Philippe Bossuat, and Jean-Pierre Hubaux. Multiparty Homomorphic Encryption from Ring-Learning-with-Errors. Proc. Priv. Enhancing Technol., 2021(4):291–311, 2021. DOI: 10.2478/POPETS-2021-0071
[MTY11]
Tal Malkin, Isamu Teranishi, and Moti Yung. Efficient Circuit-Size Independent Public Key Encryption with KDM Security. In Kenneth G. Paterson, editor, Advances in Cryptology – EUROCRYPT 2011, pages 507–526, Berlin, Heidelberg. 2011. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-20465-4_28
[PLZ24]
Jeongeun Park, Barry Van Leeuwen, and Oliver Zajonc. FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE. IACR Commun. Cryptol., 1(3):15, 2024. DOI: 10.62056/AEBN-4C2H
[RST+22]
Dragos Rotaru, Nigel P. Smart, Titouan Tanguy, Frederik Vercauteren, and Tim Wood. Actively Secure Setup for SPDZ. J. Cryptol., 35(1):5, 2022. DOI: 10.1007/S00145-021-09416-W
[S+24]
W. A. Stein and others. Sage Mathematics Software (Version 10.3). The Sage Development Team, 2024.
[SAB+21]
Peter Schwabe, Roberto Avanzi, Joppe Bos, Leo Ducas, Eike Kiltz, Tancrede Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, and Damien Stehle. CRYSTALS-KYBER. https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions. Proposal to NIST PQC Standardization. 2021.
[SEA21]
Microsoft SEAL (release 3.7). Microsoft Research, Redmond, WA.. https://github.com/Microsoft/SEAL. September 2021.
[Sma23]
Nigel P. Smart. Practical and Efficient FHE-Based MPC. In Elizabeth A. Quaglia, editor, Cryptography and Coding - 19th IMA International Conference, IMACC 2023, London, UK, December 12-14, 2023, Proceedings, volume 14421 of Lecture Notes in Computer Science, pages 263–283. 2023. Springer. DOI: 10.1007/978-3-031-47818-5_14
[TZF+24]
Wenxu Tang, Fangyu Zheng, Guang Fan, Tian Zhou, Jingqiang Lin, and Jiwu Jing. DPad-HE: Towards Hardware-friendly Homomorphic Evaluation using 4-Directional Manipulation. In Bo Luo, Xiaojing Liao, Jun Xu, Engin Kirda, and David Lie, editors, Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS 2024, Salt Lake City, UT, USA, October 14-18, 2024, pages 2475–2489. 2024. ACM. DOI: 10.1145/3658644.3690280
[YAZ+19]
Rupeng Yang, Man Ho Au, Zhenfei Zhang, Qiuliang Xu, Zuoxia Yu, and William Whyte. Efficient Lattice-Based Zero-Knowledge Arguments with Standard Soundness: Construction and Applications. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part I, volume 11692 of Lecture Notes in Computer Science, pages 147–175. 2019. Springer. DOI: 10.1007/978-3-030-26948-7_6
[ZPGS19]
Wenting Zheng, Raluca Ada Popa, Joseph E. Gonzalez, and Ion Stoica. Helen: Maliciously Secure Coopetitive Learning for Linear Models. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pages 724–738. 2019. IEEE. DOI: 10.1109/SP.2019.00045
PDF
History
Submitted: 2025-01-14
Accepted: 2025-06-02
Published: 2025-07-07
Accepted: 2025-06-02
Published: 2025-07-07
How to cite
Anisha Mukherjee and Sujoy Sinha Roy, Revisiting Module Lattice-based Homomorphic Encryption and Application to Secure-MPC. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/ay7qjp10.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.