FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE
Authors
Jeongeun Park, Barry van Leeuwen, Oliver Zajonc
Jeongeun Park
Norwegian University of Science and Technology, Trondheim, Norway
jeongeun dot park at ntnu dot no
jeongeun dot park at ntnu dot no
Barry van Leeuwen
KU Leuven, Leuven, Belgium
barry dot vanleeuwen at kuleuven dot be
barry dot vanleeuwen at kuleuven dot be
Oliver Zajonc
KU Leuven, Leuven, Belgium
oliver dot zajonc at esat dot kuleuven dot be
oliver dot zajonc at esat dot kuleuven dot be
Abstract
Multi-key fully homomorphic encryption (MKFHE), a generalization of fully homomorphic encryption (FHE), enables a computation over encrypted data under multiple keys. The first MKFHE schemes were based on the NTRU primitive, however these early NTRU based FHE schemes were found to be insecure due to the problem of over-stretched parameters. Recently, in the case of standard (non-multi key) FHE a secure version, called FINAL, of NTRU has been found. In this work we extend FINAL to an MKFHE scheme, this allows us to benefit from some of the performance advantages provided by NTRU based primitives. Thus, our scheme provides competitive performance against current state-of-the-art multi-key TFHE, in particular reducing the computational complexity from quadratic to linear in the number of keys.
References
[ABD16]
Martin R. Albrecht, Shi Bai, and Léo Ducas. A Subfield Lattice Attack on Overstretched NTRU Assumptions - Cryptanalysis of Some FHE and Graded Encoding Schemes. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part I, volume 9814 of LNCS, pages 153–178. August 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-53018-4_6
[AH19]
Asma Aloufi and Peizhao Hu. Collaborative Homomorphic Computation on Data Encrypted under Multiple Keys. 2019.
[AJL+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, EUROCRYPT 2012, volume 7237 of LNCS, pages 483–501. April 2012. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-29011-4_29
[AK{\"O}23]
Yavuz Akin, Jakub Klemsa, and Melek Önen. A Practical TFHE-Based Multi-Key Homomorphic Encryption with Linear Complexity and Low Noise Growth. In Gene Tsudik, Mauro Conti, Kaitai Liang, and Georgios Smaragdakis, editors, ESORICS 2023, Part I, volume 14344 of LNCS, pages 3–23. September 2023. Springer, Cham. DOI: 10.1007/978-3-031-50594-2_1
[APS15]
Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology, 9(3):169–203, 2015. DOI: doi:10.1515/jmc-2015-0016
[BIP+22]
Charlotte Bonte, Ilia Iliashenko, Jeongeun Park, Hilder V. L. Pereira, and Nigel P. Smart. FINAL: Faster FHE Instantiated with NTRU and LWE. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part II, volume 13792 of LNCS, pages 188–215. December 2022. Springer, Cham. DOI: 10.1007/978-3-031-22966-4_7
[CCS19]
Hao Chen, Ilaria Chillotti, and Yongsoo Song. Multi-Key Homomorphic Encryption from TFHE. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part II, volume 11922 of LNCS, pages 446–472. December 2019. Springer, Cham. 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 Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 395–412. November 2019. ACM Press. DOI: 10.1145/3319535.3363207
[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, January 2020. DOI: 10.1007/s00145-019-09319-x
[CJL16]
Jung Hee Cheon, Jinhyuck Jeong, and Changmin Lee. An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero. LMS Journal of Computation and Mathematics, 19(A):255–266, 2016. DOI: 10.1112/S1461157016000371
[DM15]
Léo Ducas and Daniele Micciancio. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 617–640. April 2015. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-46800-5_24
[Dv21]
Léo Ducas and Wessel P. J. van Woerden. NTRU Fatigue: How Stretched is Overstretched?. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part IV, volume 13093 of LNCS, pages 3–32. December 2021. Springer, Cham. DOI: 10.1007/978-3-030-92068-5_1
[GPV23]
Antonio Guimarães, Hilder V. L. Pereira, and Barry Van Leeuwen. Amortized Bootstrapping Revisited: Simpler, Asymptotically-Faster, Implemented. In Jian Guo and Ron Steinfeld, editors, ASIACRYPT 2023, Part VI, volume 14443 of LNCS, pages 3–35. December 2023. Springer, Singapore. DOI: 10.1007/978-981-99-8736-8_1
[KKL+23]
Taechan Kim, Hyesun Kwak, Dongwon Lee, Jinyeong Seo, and Yongsoo Song. Asymptotically Faster Multi-Key Homomorphic Encryption from Homomorphic Gadget Decomposition. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 726–740, New York, NY, USA. 2023. Association for Computing Machinery. DOI: 10.1145/3576915.3623176
[KL23]
Jiseung Kim and Changmin Lee. A polynomial time algorithm for breaking NTRU encryption with multiple keys. DCC, 91(8):2779–2789, 2023. DOI: 10.1007/s10623-023-01233-5
[KLSW21]
Hyesun Kwak, Dongwon Lee, Yongsoo Song, and Sameer Wagh. A Unified Framework of Homomorphic Encryption for Multiple Parties with Non-Interactive Setup. https://eprint.iacr.org/2021/1412. Cryptology ePrint Archive, Paper 2021/1412. 2021.
[KMS22]
Hyesun Kwak, Seonhong Min, and Yongsoo Song. Towards Practical Multi-key TFHE: Parallelizable, Key-Compatible, Quasi-linear Complexity. Cryptology ePrint Archive, Report 2022/1460. 2022.
[KMS24]
Hyesun Kwak, Seonhong Min, and Yongsoo Song. Towards Practical Multi-key TFHE: Parallelizable, Key-Compatible, Quasi-linear Complexity. In Qiang Tang and Vanessa Teague, editors, PKC 2024, Part II, volume 14604 of LNCS, pages 354–385. April 2024. Springer, Cham. DOI: 10.1007/978-3-031-57728-4_12
[LATV12]
Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan. On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pages 1219–1234, New York, NY, USA. 2012. Association for Computing Machinery. DOI: 10.1145/2213977.2214086
[LP19]
Hyang-Sook Lee and Jeongeun Park. On the Security of Multikey Homomorphic Encryption. In Martin Albrecht, editor, 17th IMA International Conference on Cryptography and Coding, volume 11929 of LNCS, pages 236–251. December 2019. Springer, Cham. DOI: 10.1007/978-3-030-35199-1_12
[MS18]
Daniele Micciancio and Jessica Sorrell. Ring Packing and Amortized FHEW Bootstrapping. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, ICALP 2018, volume 107 of LIPIcs, pages 100:1–100:14. July 2018. Schloss Dagstuhl. DOI: 10.4230/LIPIcs.ICALP.2018.100
[MW16]
Pratyay Mukherjee and Daniel Wichs. Two Round Multiparty Computation via Multi-key FHE. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 735–763. May 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-49896-5_26
[Par21]
Jeongeun Park. Homomorphic Encryption for Multiple Users With Less Communications. IEEE Access, 9:135915-135926, 2021. DOI: 10.1109/ACCESS.2021.3117029
[PS16]
Chris Peikert and Sina Shiehian. Multi-key FHE from LWE, Revisited. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B, Part II, volume 9986 of LNCS, pages 217–238. 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-53644-5_9
[XTW+23]
Kexin Xu, Benjamin Hong Meng Tan, Li-Ping Wang, Khin Mi Mi Aung, and Huaxiong Wang. Multi-key fully homomorphic encryption from NTRU and (R)LWE with faster bootstrapping. Theoretical Computer Science, 968:114026, 2023. DOI: https://doi.org/10.1016/j.tcs.2023.114026
PDF
History
Submitted: 2024-07-05
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Jeongeun Park, Barry van Leeuwen, and Oliver Zajonc, FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/aebn-4c2h.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.