Multi-key fully homomorphic encryption scheme based on NTRU bootstrapping

ZHENG Junhua; JIANG Hongwei; LIU Rong; LI Yixiu; LI Wen; WENG Jian

doi:10.11959/j.issn.2096-109x.2024085

您当前的位置：

首页 >

文章列表页 >

Multi-key fully homomorphic encryption scheme based on NTRU bootstrapping

Papers | 更新时间：2025-02-06

- Multi-key fully homomorphic encryption scheme based on NTRU bootstrapping
- Chinese Journal of Network and Information Security Vol. 10, Issue 6, Pages: 123-136(2024)
- 作者机构：
  
  1.中国烟草总公司广东省公司，广东广州 510610
  2.暨南大学网络空间安全学院，广东广州 510632
- 作者简介：
- 基金信息：
  
  Science and Technology Project of CNTC Guangdong Corporation(粤烟科项202207);Guangzhou Science and Technology Plan Project(2024A03J0464)
- DOI：10.11959/j.issn.2096-109x.2024085
  CLC： TP309
- Received：05 August 2024，
  
  Revised：2024-11-06，
  
  Published：25 December 2024
- 稿件说明：
移动端阅览
郑俊华, 江宏伟, 刘荣, 等. 基于NTRU自举的多密钥全同态加密方案[J]. 网络与信息安全学报, 2024, 10(6): 123-136.

ZHENG J H, JIANG H W, LIU R, et al. Multi-key fully homomorphic encryption scheme based on NTRU bootstrapping[J]. Chinese Journal of Network and Information Security, 2024, 10(6): 123-136.
郑俊华, 江宏伟, 刘荣, 等. 基于NTRU自举的多密钥全同态加密方案[J]. 网络与信息安全学报, 2024, 10(6): 123-136. DOI： 10.11959/j.issn.2096-109x.2024085.

ZHENG J H, JIANG H W, LIU R, et al. Multi-key fully homomorphic encryption scheme based on NTRU bootstrapping[J]. Chinese Journal of Network and Information Security, 2024, 10(6): 123-136. DOI： 10.11959/j.issn.2096-109x.2024085.

摘要

多密钥全同态加密（multi-key fully homomorphic encryption

MK-FHE）技术支持对不同密钥加密的密文进行同态运算，能够直接应用于现实中的多用户数据融合计算场景，如多方协同计算和联邦学习。目前，主流的多密钥全同态加密主要通过自举技术实现对LWE（learning with error）加密密文的多密钥同态计算。将单密钥密文扩展为多密钥密文的时间效率和存储开销与自举技术密切相关，通常需要大量的同态评估密钥以及复杂的运算。因此，如何结合更优的自举技术设计多密钥全同态加密方案，进而提升计算效率与降低存储开销成为研究的关键问题。基于NTRU（number theory research unit）自举技术，设计了一种针对LWE密文的高效多密钥全同态加密方案。与其他方案相比，所提方案在密文扩展过程中具有更高的计算效率。此外，对所提方案的正确性进行了详细阐述和分析，并在理论上将所提方案与现有主流的多密钥全同态加密方案进行了多维度对比，结果显示所提方案具有更优的计算效率。最后，探索了该方案在多行业多源销售数据跨部门监管场景中的潜在应用，在保护数据隐私的前提下帮助税务部门实现税务核验，有助于推动各行业的数字化转型和健康发展。

Abstract

Multi-key fully homomorphic encryption (MK-FHE) technology supports homomorphic operations on ciphertexts encrypted with different keys

and can be directly applied to real-world multi-user data fusion computing scenarios

such as multi-party collaborative computing and federated learning. At present

mainstream multi-key fully homomorphic encryption mainly uses bootstrapping technology to achieve multi-key homomorphic computing of LWE (learning with errors) encrypted ciphertexts. The time efficiency and storage overhead of expanding single-key ciphertexts to multi-key ciphertexts are closely related to the bootstrapping technology

which usually requires a large number of homomorphic evaluation keys and complex operations. Therefore

designing a multi-key fully homomorphic encryption scheme in combination with a better bootstrapping technology to improve computational efficiency and reduce storage overhead had become a key research issue. Based on the NTRU (number theory research unit) bootstrapping technology

an efficient multi-key fully homomorphic encryption scheme for LWE ciphertexts was designed. Compared with other schemes

the proposed scheme exhibited higher computational efficiency in the ciphertext expansion process. In addition

the correctness of the proposed scheme was elaborated and analyzed in detail. The proposed scheme was compared with the existing mainstream multi-key fully homomorphic encryption scheme in theory. The results show that the proposed scheme has better computational efficiency. Finally

the potential application of the scheme in cross-departmental supervision scenarios of multi-industry and multi-source data sales data was explored

which helped the tax department to realize tax verification under the premise of protecting data privacy

and helped promote the digital transformation and healthy development of various industries.

关键词

Keywords

references

杨德春 , 冉彬 , 孔令虎 , 等 . 以数据为核心的烟草制造行业数字化转型 [J ] . 智能制造 , 2021 , ( 1 ): 106 - 109 .

YANG D C , RAN B , KONG L H , et al . Digital transformation of tobacco manufacturing industry with data as the core [J ] . Intelligent Manufacturing , 2021 , ( 1 ): 106 - 109 .

李凤华 , 李晖 , 贾焰 , 俞能海 , 等 . 隐私计算研究范畴及发展趋势 [J ] . 通信学报 , 2016 , 37 ( 4 ): 4 .

LI F H , LI H , JIA Y , YU N H , et al . Privacy computing：concept, connotation and its research trend [J ] . Journal on Communications , 2016 , 37 ( 4 ): 4 .

YAO A C . Protocols for secure computations [C ] // 23rd Annual Symposium on Foundations of Computer Science ( SFCS 1982) . IEEE , 1982 : 160 - 164 .

YANG Q , LIU Y , CHEN T , et al . Federated machine learning: concept and applications [J ] . ACM Transactions on Intelligent Systems and Technology (TIST) , 2019 , 10 ( 2 ): 1 - 19 .

杨帆 , 孙奕 , 陈性元 , 等 . 基于同态代理重认证的可验证联邦聚合方法 [J ] . 网络与信息安全学报 , 2024 , 10 ( 3 ): 91 - 106 .

YANG F , SUN Y , CHEN X Y , et al . Verifiable federated aggregation method based onhomomorphic proxy re-authentication [J ] . Chinese Journal of Network and Information Security , 2024 , 10 ( 3 ): 91 - 106 .

SABT M , ACHEMLAL M , BOUABDALLAH A . Trusted execution environment: what it is, and what it is not [C ] // 2015 IEEE Trustcom/BigDataSE/ISPA . IEEE , 2015 ( 1 ): 57 - 64 .

张晓均 , 张经伟 , 黄超 , 等 . 可验证医疗密态数据聚合与统计分析方案 [J ] . 软件学报 , 2022 , 33 ( 11 ): 4285 - 4304 .

ZHANG X J , ZHANG J W , CHEN Y X , et al . Verifiable encrypted medical data aggregation and statistical analysis scheme [J ] Journal of Software , 2022 , 33 ( 11 ): 4285 - 4304 .

任艳丽 , 余凌赞 , 何港 , 等 . 一种隐私保护的卷积神经网络预测方案 [J ] . 计算机学报 , 2023 , 46 ( 8 ): 1606 - 1619 .

REN Y L , YU L Z , HE G , et al . A scheme of privacy-preserving convolutional neural network prediction [J ] . Chinese Journal of Computers , 2023 , 46 ( 8 ): 1606 - 1619 .

李宇溪 , 周福才 , 徐紫枫 . 支持 K -近邻搜索的移动社交网络隐私保护方案 [J ] . 计算机学报 , 2021 , 44 ( 7 ): 1481 - 1500 .

LI Y X , ZHOU F C , XU Z F . Privacy-preserving k -nearest-neighbor search over mobile Ssocial network [J ] . Chinese Journal of Computers , 2021 , 44 ( 7 ): 1481 - 1500 .

肖文乾 , 杨高波 , 王德望 , 等 . 基于加法同态加密与多高位嵌入的加密域图像可逆信息隐藏 [J ] . 网络与信息安全学报 , 2023 , 9 ( 4 ): 121 - 133 .

XIAO W Q , YANG G B , WANG D W , et al . Reversible data hiding in encrypted images based on additive homomorphic encryption and multi-MSB embedding [J ] . Chinese Journal of Network and Information Security , 2023 , 9 ( 4 ): 121 - 133 .

LÓPEZ-ALT A , TROMER E , VAIKUNTANATHAN V . On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption [C ] // Proceedings of the 44th Annual ACM Symposium on Theory of Computing . 2012 : 1219 - 1234 .

CLEAR M , MCGOLDRICK C . Multi-identity and multi-key leveled FHE from learning with errors [C ] // Advances in Cryptology--CRYPTO 2015: 35th Annual Cryptology Conference . 2015 : 630 - 656 .

MUKHERJEE P , WICHS D . Two round multiparty computation via multi-key FHE [C ] // Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques . 2016 : 735 - 763 .

CHEN H , CHILLOTTI I , SONG Y . Multi-key homomorphic encryption from TFHE [C ] // Advances in Cryptology–ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security . 2019 : 446 - 472 .

XU K , TAN B H M , WANG L P , et al . Multi-key fully homomorphic encryption from NTRU and (R) LWE with faster bootstrapping [J ] . Theoretical Computer Science , 2023 , 968 : 114026 .

BONTE C , ILIASHENKO I , PARK J , et al . FINAL: faster FHE instantiated with NTRU and LWE [C ] // International Conference on the Theory and Application of Cryptology and Information Security . 2022 : 188 - 215 .

KLUCZNIAK K . NTRU-v-um: secure fully homomorphic encryption from NTRU with small modulus [C ] // Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security . 2022 : 1783 - 1797 .

XIANG B , ZHANG J , DENG Y , et al . Fast blind rotation for bootstrapping FHEs [C ] // Annual International Cryptology Conference . 2023 : 3 - 36 .

RIVEST R L , ADLEMAN L , DERTOUZOS M L . On data banks and privacy homomorphisms [J ] . Foundations of Secure Computation , 1978 , 4 ( 11 ): 169 - 180 .

HOFFSTEIN J , PIPHER J , SILVERMAN J H . NTRU: a ring-based public key cryptosystem [C ] // Proc Int Algorithmic Number Theory Symp . 1998 : 267 - 288 .

REGEV O . On lattices, learning with errors, random linear codes, and cryptography [C ] // STOC , ACM , 2005 : 84 - 93 .

LYUBASHEVSKY V , PEIKERT C , REGEV O . On ideal lattices and learning with errors over rings [C ] // Advances in Cryptology-EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques , 2010 : 1 - 23 .

KIM E , LEE H S , PARK J . Towards round-optimal secure multiparty computations: multikey FHE without a CRS [C ] // Information Security and Privacy , ACISP 2018 , 2018 : 101 - 113 .

STEHLÉ D , STEINFELD R . Making NTRU as secure as worst-case problems over ideal lattices [C ] // Advances in Cryptology–EUROCRYPT 2011: 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques . 2011 : 27 - 47 .

ALBRECHT M R , BAI S , DUCAS L , A subfield lattice attack on overstretched NTRU assumptions - cryptanalysis of some FHE and graded encoding schemes [C ] // CRYPTO , Lecture Notes in Computer Science . 2016 : 153 - 178 .

CHEON J H , JEONG J , LEE C . An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero [J ] . LMS Journal of Computation and Mathematics , 2016 , 19 : 255 - 266 .

KIRCHNER P , FOUQUE P , Revisiting lattice attacks on overstretched NTRU parameters [C ] // EUROCRYPT , Lecture Notes in Computer Science , 2017 : 3 - 26 .

DUCAS L , VAN-WOERDEN W P J . NTRU fatigue: how stretched is overstretched [C ] //ASIACRYPT,Lecture Notes in Computer Science. 2021 ,: 3 - 32 .

BRAKERSKI Z , PERLMAN R . Lattice-based fully dynamic multi-key FHE with short ciphertexts [C ] // Annual International Cryptology Conference . 2016 : 190 - 213 .

PEIKERT C . Public-key cryptosystems from the worst-case shortest vector problem [C ] // Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing . 2009 : 333 - 342 .

PEIKERT C , SHIEHIAN S . Multi-key FHE from LWE, revisited [C ] // Theory of Cryptography Conference . 2016 : 217 - 238 .

CHEN Y , DONG S , LI T , et al . Dynamic multi-key FHE in asymmetric key setting from LWE [J ] . IEEE Transactions on Information Forensics and Security , 2021 , 16 : 5239 - 5249 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰