全同态加密技术的研究现状及发展路线综述

戴怡然; 张江; 向斌武; 邓燚

doi:10.11999/JEIT230703

全同态加密技术的研究现状及发展路线综述

doi: 10.11999/JEIT230703

戴怡然^{1, 2, 3},
张江²,
向斌武^{1, 2, 3},
邓燚^{1, 3, ,}

1.
中国科学院信息工程研究所信息安全国家重点实验室北京 100093
2.
密码科学技术全国重点实验室北京 100878
3.
中国科学院大学网络空间安全学院北京 100049

基金项目: 国家重点研发计划(2023YFB4503203)，国家自然科学基金(62372447, 61932019)

详细信息

作者简介:
戴怡然：女，博士生，研究方向为全同态加密

张江：男，副研究员，研究方向为公钥密码可证明安全理论、抗量子密码、多方安全计算协议设计与分析研究

向斌武：男，博士生，研究方向为抗量子密码算法的设计与安全性分析、全同态加密

邓燚：男，研究员，研究方向为零知识证明、安全归约方法

通讯作者:
邓燚　deng@iie.ac.cn

1¹⁾ 通常自举算法只需自举密钥与密文做乘法即可同时完成密文的解密与重加密
2²⁾ 每个明文槽都只包含字段（或环）的一个元素，而不是扩展字段（或环）。
中图分类号: TN918.4; TP309
计量
- 文章访问数: 1536
- HTML全文浏览量: 463
- PDF下载量: 387
- 被引次数: 0
出版历程
- 收稿日期: 2023-09-28
- 修回日期: 2024-01-22
- 网络出版日期: 2024-05-12
- 刊出日期: 2024-05-30

Overview on the Research Status and Development Route of Fully Homomorphic Encryption Technology

DAI Yiran^{1, 2, 3},
ZHANG Jiang²,
XIANG Binwu^{1, 2, 3},
DENG Yi^{1, 3
, ,}

1.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
2.
State Key Laboratory of Cryptology, Beijing 100878, China
3.
School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China

Funds: The National Key Research and Development Project of China (2023YFB4503203), The National Natural Science Foundation of China (62372447, 61932019)

摘要

摘要: 随着物联网、云计算、人工智能的应用与普及，数据安全与隐私保护成为人们关注的焦点。全同态加密，作为隐私安全问题的有效解决办法，允许对加密数据执行任意同态计算，是一种强大的加密工具，具有广泛的潜在应用。该文总结了自2009年以来提出全同态加密方案，并根据方案的核心技术划分成4条技术路线，分析讨论了各类方案的关键构造，算法优化进程和未来发展方向。首先，全面介绍了全同态加密相关的数学原理，涵盖了全同态加密方案的基础假设和安全特性。随后，按照4条全同态加密方案的技术路线，归纳了加密方案的结构通式，总结了自举算法的核心步骤，讨论了最新研究进展，并在此基础上综合分析比较了各类方案的存储效率及运算速度。最后，展示了同态算法库对每条技术路线下加密方案的应用实现情况，分析了在当前时代背景下全同态加密方案的机遇与挑战，并对未来的研究前景做出了展望。
- 全同态加密 /
- 自举 /
- BGV /
- GSW /
- CKKS
Abstract: With the application and popularization of IoT, cloud computing, and artificial intelligence, data security and privacy protection have become the focus of attention. Fully homomorphic encryption, as an effective solution to the privacy security problem, allows performing arbitrary homomorphic computation on encrypted data, and is a powerful encryption tool with a wide range of potential applications. The paper summarizes the proposed fully homomorphic encryption schemes since 2009, and divides them into four technical routes based on the core technologies of the schemes, analyzes and discusses the key constructs, algorithm optimization processes, and future development directions of each type of scheme. The paper firstly introduces fully homomorphic encryption-related mathematical principles, covering the basic assumptions and security features of fully homomorphic encryption schemes. Subsequently, according to the technical routes of the four fully homomorphic encryption schemes, it summarizes the structural general formulas of the encryption schemes, summarizes the core steps of the bootstrap algorithms, discusses the latest research progress, and on the basis of this, comprehensively analyzes and compares the storage efficiencies and computing speeds of various schemes. The paper finally shows the application implementation of homomorphic algorithm library for encryption schemes under each technical route, analyzes the opportunities and challenges of fully homomorphic encryption schemes in the current era, and makes an outlook on the future research prospects.
- Fully Homomorphic Encryption /
- Bootstrapping /
- BGV /
- GSW /
- CKKS

HTML全文

图 1 全同态加密的不同技术路线分支及其代表性方案

下载: 全尺寸图片幻灯片

表 1 Andrey Kim团队对BFV和BGV方案的算法优化

BFV	BGV	优化效果
$\left\lfloor {\dfrac{q}{t}} \right\rfloor m \to \left\lfloor {\dfrac{{qm}}{t}} \right\rfloor $预计算$qm$	\	降低初始噪声
将乘法中的模切换步骤置于重线性化之后	\	降低模切换维数
将BFV的模数分层，乘法之后切换到小模数	\	减缓噪声增长速度
\	静态噪声管理	增强方案的实用性

下载: 导出CSV

表 2 CKKS 类全同态加密方案自举的不同近似函数及自举精度对比

方案名称	近似函数(方法)	自举精度(bit)
CHKKS^[31]	$ \sin \left( {\dfrac{{2\pi x}}{q}} \right) \approx x\text{mod} q $	24
LLLK^[32]	$\left( {\dfrac{{2\pi x}}{q}} \right)\arcsin \left( {\sin \left( {\dfrac{{2\pi x}}{q}} \right)} \right) = x\text{mod} q$	40.5
JM^[33]	$\dfrac{q}{{2\pi }}\mathop \sum \limits_{k = 1}^n {\beta _k}{\text{sin}}\left( {\dfrac{{2\pi kx}}{q}} \right) \approx x\text{mod} q$	44
BCCKK^[24]	META BTS	255

下载: 导出CSV

表 3 4条技术路线全同态加密方案对比

	Gentry类	BGV类		GSW类	CKKS类
基础假设	理想格	LWE	RLWE	(R)LWE	RLWE
密文空间	${\mathbb{Z}_d}$	$\mathbb{Z}_q^n$	$R_q^n$	$\mathbb{Z}_q^{n \times n}$	$R_q^n$
密文大小	$f\left( \lambda \right)$	$\left( {n + 1} \right)\left\lceil {\log_2 q} \right\rceil $	$2n\left\lceil {\log_2 q} \right\rceil $	${\left( {n + 1} \right)^2}{\left\lceil {\log_2 q} \right\rceil ^3}$	$2n\left\lceil {\log_2 q} \right\rceil $
明文空间	${\mathbb{Z}_2}$	${\mathbb{Z}_t}$	${R_t}$	${\mathbb{Z}_2}$	\
单个密文存储明文数	1	1	n	1	n
公钥大小	$s \cdot \left\lceil {2\sqrt S } \right\rceil \cdot {\log _2}d$	$2n\left( {n + 1} \right){\log_2}q$	$2n\left\lceil {\log_2 q} \right\rceil $	$2n\left( {n + 1} \right){\log_2}q$	$2n\left\lceil {\log_2 q} \right\rceil $
是否支持消息打包	\	否	是	暂不支持	是
是否支持SIMD	\	是	是	暂不支持	是
同态乘法噪声增长速度	${N^{{{\Omega }}\left( 1 \right)}}$	$O\left( {{n^2}} \right)$	$O\left( {{n^2}} \right)$	$O\left( n \right)$	$O\left( {{n^2}} \right)$
(平均)单比特自举时间	30 min	\	1.3 ms	13 ms	6.43 s

下载: 导出CSV

表 4 不同实现库的应用特点对比

实现库名称	实现语言	支持加密方案	自举	特色功能
Helib	C++	BGV, CKKS	√	支持HE 汇编语言
SEAL	C++	BFV, CKKS	√	跨平台编译
PALISADE	C++	BGV, BFV, CKKS, FHEW, TFHE	√	跨平台编译，BGV/BFV/CKKS的多方扩展
TFHE	C/C++	GSW, FHEW, TFHE	√	可编程自举
HEAAN	C++	CKKS	√	GPU加速
NFLlib	C++	\	\	基于NTT的快速格计算
cuFHE	C++	TFHE	√	CUDA加速
Lattigo	Go	BGV, BFV, CKKS	√	跨平台编译，剩余数系统(RNS)
OpenFHE	C++	BGV, BFV, CKKS, FHEW, TFHE	√	剩余数系统(RNS), BGV/BFV/CKKS的多方扩展

下载: 导出CSV

参考文献(67)

[1]	BRICKELL E F and YACOBI Y. On privacy homomorphisms (Extended Abstract)[C]. The Workshop on the Theory and Application of Cryptographic Techniques, Amsterdam, The Netherlands, 1988: 117–125. doi: 10.1007/3-540-39118-5_12.
[2]	CRAMER R, DAMGÅRD I, and NIELSEN J B. Multiparty computation from threshold homomorphic encryption[C]. The International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, 2001: 280–300. doi: 10.1007/3-540-44987-6_18.
[3]	RIVEST R L, ADLEMAN L, and DERTOUZOS M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978, 4(11): 169–179.
[4]	ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms[M]. BLAKLEY G R and CHAUM D. Advances in Cryptology. Berlin Heidelberg: Springer, 1985: 10–18. doi: 10.1007/3-540-39568-7_2.
[5]	RIVEST R L, SHAMIR A, and ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120–126. doi: 10.1145/359340.359342.
[6]	BONEH D, GOH E J, and NISSIM K. Evaluating 2-DNF formulas on ciphertexts[C]. The Second Theory of Cryptography Conference, Cambridge, USA, 2005: 325–341. doi: 10.1007/978-3-540-30576-7_18.
[7]	BEHERA S and PRATHURI J R. Design of novel hardware architecture for fully homomorphic encryption algorithms in FPGA for real-time data in cloud computing[J]. IEEE Access, 2022, 10: 131406–131418. doi: 10.1109/ACCESS.2022.3229892.
[8]	LI Juyan, QIAO Zhiqi, ZHANG Kejia, et al. A lattice-based homomorphic proxy re-encryption scheme with strong anti-collusion for cloud computing[J]. Sensors, 2021, 21(1): 288. doi: 10.3390/s21010288.
[9]	LEE J W, KANG H, LEE Y, et al. Privacy-preserving machine learning with fully homomorphic encryption for deep neural network[J]. IEEE Access, 2022, 10: 30039–30054. doi: 10.1109/ACCESS.2022.3159694.
[10]	李腾, 方保坤, 马卓, 等. 基于同态加密的医疗数据密文异常检测方法[J]. 中国科学: 信息科学, 2023, 53(7): 1368–1391. doi: 10.1360/SSI-2022-0214. LI Teng, FANG Baokun, MA Zhuo, et al. Homomorphic encryption-based ciphertext anomaly detection method for e-health records[J]. Scientia Sinica Informationis, 2023, 53(7): 1368–1391. doi: 10.1360/SSI-2022-0214.
[11]	GENTRY C. Fully homomorphic encryption using ideal lattices[C]. The 41st Annual ACM Symposium on Theory of Computing, Bethesda, USA, 2009: 169–169. doi: 10.1145/1536414.1536440.
[12]	PEREIRA H V L. Bootstrapping fully homomorphic encryption over the integers in less than one second[C/OL]. The 24th IACR International Conference on Practice and Theory of Public Key Cryptography, 2021. doi: 10.1007/978-3-030-75245-3_13.
[13]	BONTE C, ILIASHENKO I, PARK J, et al. FINAL: Faster FHE instantiated with NTRU and LWE[C]. The 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, China, 2022. doi: 10.1007/978-3-031-22966-4_7.
[14]	KLUCZNIAK K. NTRU-v-um: Secure fully homomorphic encryption from NTRU with small modulus[C]. The 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, USA, 2022: 1783–1797. doi: 10.1145/3548606.3560700.
[15]	XIANG Binwu, ZHANG Jiang, DENG Yi, et al. Fast blind rotation for bootstrapping FHEs[C]. The 43rd Annual International Cryptology Conference, Santa Barbara, USA, 2023. doi: 10.1007/978-3-031-38551-3_1.
[16]	STEHLÉ D, STEINFELD R, TANAKA K, et al. Efficient public key encryption based on ideal lattices[C]. The 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, 2009. doi: 10.1007/978-3-642-10366-7_36.
[17]	SVP challenge[EB/OL]. https://www.latticechallenge.org/svp-challenge/.
[18]	REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, Baltimore, USA, 2005: 84–93. doi: 10.1145/1060590.1060603.
[19]	BLUM A, FURST M, KEARNS M, et al. Cryptographic primitives based on hard learning problems[C]. The 13th Annual International Cryptology Conference, Santa Barbara, USA, 1994. doi: 10.1007/3-540-48329-2_24.
[20]	BRAKERSKI Z and VAIKUNTANATHAN V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[C]. The 31st Annual Cryptology Conference, Santa Barbara, USA, 2011. doi: 10.1007/978-3-642-22792-9_29.
[21]	GENTRY C, HALEVI S, and VAIKUNTANATHAN V. i-Hop homomorphic encryption and rerandomizable Yao circuits[C]. The 30th Annual Cryptology Conference, Santa Barbara, USA, 2010. doi: 10.1007/978-3-642-14623-7_9.
[22]	KITAGAWA F and MATSUDA T. Circular security is complete for KDM security[C]. The 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, 2020. doi: 10.1007/978-3-030-64837-4_9.
[23]	BRAKERSKI Z and VAIKUNTANATHAN V. Efficient fully homomorphic encryption from (standard) LWE[C]. The IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, USA, 2011: 97–106. doi: 10.1109/FOCS.2011.12.
[24]	GENTRY C, SAHAI A, and WATERS B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[C]. The 33rd Annual Cryptology Conference, Santa Barbara, USA, 2013. doi: 10.1007/978-3-642-40041-4_5.
[25]	CHEON J H, KIM A, KIM M, et al. Homomorphic encryption for arithmetic of approximate numbers[C]. The 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017. doi: 10.1007/978-3-319-70694-8_15.
[26]	GENTRY C. Computing arbitrary functions of encrypted data[J]. Communications of the ACM, 2010, 53(3): 97–105. doi: 10.1145/1666420.1666444.
[27]	GENTRY C and HALEVI S. Implementing Gentry’s fully-homomorphic encryption scheme[C]. The 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, 2011: 129–148. doi: 10.1007/978-3-642-20465-4_9.
[28]	GENTRY C and HALEVI S. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits[C]. The IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, USA, 2011. doi: 10.1109/FOCS.2011.94.
[29]	GENTRY C, HALEVI S, and SMART N P. Better bootstrapping in fully homomorphic encryption[C]. The 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, 2012: 1–16. doi: 10.1007/978-3-642-30057-8_1.
[30]	BRAKERSKI Z, GENTRY C, and VAIKUNTANATHAN V. (Leveled) fully homomorphic encryption without bootstrapping[C]. The 3rd Innovations in Theoretical Computer Science Conference, Cambridge, USA, 2012. doi: 10.1145/2090236.2090262.
[31]	CHEON J H, HAN K, KIM A, et al. Bootstrapping for approximate homomorphic encryption[C]. The 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 2018. DOI: 10.1007/978-3-319-78381-9_14.
[32]	LEE J W, LEE E, LEE Y, et al. High-precision bootstrapping of RNS-CKKS homomorphic encryption using optimal minimax polynomial approximation and inverse sine function[C]. The 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 2021. doi: 10.1007/978-3-030-77870-5_22.
[33]	JUTLA C S and MANOHAR N. Sine series approximation of the mod function for bootstrapping of approximate HE[R]. Paper 2021/572, 2021.
[34]	BAE Y, CHEON J H, CHO W, et al. META-BTS: Bootstrapping precision beyond the limit[C]. The 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, USA, 2022: 223–234. doi: 10.1145/3548606.3560696.
[35]	LI Baiyu and MICCIANCIO D. On the security of homomorphic encryption on approximate numbers[C]. The 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 2021. doi: 10.1007/978-3-030-77870-5_23.
[36]	LI Baiyu, MICCIANCIO D, SCHULTZ M, et al. Securing approximate homomorphic encryption using differential privacy[R]. Paper 2022/816, 2022.
[37]	FAN Junfeng and VERCAUTEREN F. Somewhat practical fully homomorphic encryption[R]. Paper 2012/144, 2012.
[38]	GENTRY C, HALEVI S, and SMART N P. Fully homomorphic encryption with polylog overhead[C]. The 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, 2012. doi: 10.1007/978-3-642-29011-4_28.
[39]	GENTRY C, HALEVI S, and SMART N P. Homomorphic evaluation of the AES circuit[C]. The 32nd Annual Cryptology Conference, Santa Barbara, USA, 2012. doi: 10.1007/978-3-642-32009-5_49.
[40]	HALEVI S and SHOUP V. Algorithms in HElib[C]. The 34th Annual Cryptology Conference, Santa Barbara, USA, 2014. doi: 10.1007/978-3-662-44371-2_31.
[41]	HALEVI S and SHOUP V. Design and implementation of HElib: A homomorphic encryption library[R]. Paper 2020/1481, 2020.
[42]	HALEVI S and SHOUP V. Bootstrapping for HElib[J]. Journal of Cryptology, 2021, 34(1): 7. doi: 10.1007/s00145-020-09368-7.
[43]	KIM A, POLYAKOV Y, and ZUCCA V. Revisiting homomorphic encryption schemes for finite fields[C]. Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 2021. DOI: 10.1007/978-3-030-92078-4_21.
[44]	ALPERIN-SHERIFF J and PEIKERT C. Faster bootstrapping with polynomial error[C]. The 34th Annual Cryptology Conference, Santa Barbara, USA, 2014: 297–314. doi: 10.1007/978-3-662-44371-2_17.
[45]	DUCAS L and MICCIANCIO D. FHEW: Bootstrapping homomorphic encryption in less than a second[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 2015: 617–640. doi: 10.1007/978-3-662-46800-5_24.
[46]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[C]. The 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016. DOI: 10.1007/978-3-662-53887-6_1.
[47]	MYERS S and SHULL A. Practical revocation and key rotation[C]. The Cryptographers’ Track at the RSA Conference 2018, San Francisco, USA, 2018. DOI: 10.1007/978-3-319-76953-0_9.
[48]	LIU Fenghao and WANG Han. Batch bootstrapping II: Bootstrapping in polynomial modulus only requires $ O(1) $ FHE multiplications in amortization[C]. The 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 2023: 353–384. doi: 10.1007/978-3-031-30620-4_12.
[49]	LIU Fenghao and WANG Han. Batch bootstrapping I: A new framework for SIMD bootstrapping in polynomial modulus[C]. The 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 2023: 321–352. doi: 10.1007/978-3-031-30620-4_11.
[50]	MICCIANCIO D and REGEV O. Lattice-based cryptography[M]. BERNSTEIN D J, BUCHMANN J, and DAHMEN E. Post-Quantum Cryptography. Berlin, Heidelberg: Springer, 2009. doi: 10.1007/978-3-540-88702-7_5.
[51]	AJTAI M. Generating hard instances of lattice problems (extended abstract)[C]. The Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, USA, 1996: 99–108. doi: 10.1145/237814.237838.
[52]	LYUBASHEVSKY V, PEIKERT C, and REGEV O. On ideal lattices and learning with errors over rings[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France, 2010. doi: 10.1007/978-3-642-13190-5_1.
[53]	DUCAS L and DURMUS A. Ring-LWE in polynomial rings[C]. The 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, 2012: 34–51. doi: 10.1007/978-3-642-30057-8_3.
[54]	SMART N P and VERCAUTEREN F. Fully homomorphic SIMD operations[J]. Designs, Codes and Cryptography, 2014, 71(1): 57–81. doi: 10.1007/s10623-012-9720-4.
[55]	Homenc. HElib[EB/OL].https://github.com/homenc/HElib.
[56]	Microsoft. SEAL[EB/OL]. https://github.com/microsoft/SEAL.
[57]	Openfheorg. Openfhe-development[EB/OL]. https://github.com/openfheorg/openfhe-development.
[58]	Tfhe. Tfhe[EB/OL].https://github.com/tfhe/tfhe.
[59]	Snucrypto. HEAAN[EB/OL]. https://github.com/snucrypto/HEAAN.
[60]	CHOWDHURY S, SINHA S, SINGH A, et al. Efficient threshold FHE with application to real-time systems[R]. Paper 2022/1625, 2022.
[61]	YUAN Minghao, WANG Dongdong, ZHANG Feng, et al. An examination of multi-key fully homomorphic encryption and its applications[J]. Mathematics, 2022, 10(24): 4678. doi: 10.3390/math10244678.
[62]	PARK J and ROVIRA S. Efficient TFHE bootstrapping in the multiparty setting[R]. Paper 2023/759, 2023.
[63]	DI GIUSTO A and MARCOLLA C. Breaking the power-of-two barrier: Noise estimation for BGV in NTT-friendly rings[R]. Paper 2023/783, 2023.
[64]	CHEN Hao, ILIASHENKO I, and LAINE K. When HEAAN Meets FV: A new somewhat homomorphic encryption with reduced memory overhead[C]. The 18th IMA International Conference, 2021. doi: 10.1007/978-3-030-92641-0_13.
[65]	AUNG K M M, LIM E, SIM J J, et al. Field instruction multiple data[R]. Paper 2022/771, 2022.
[66]	LI Zengpeng and WANG Ding. Achieving one-round password-based authenticated key exchange over lattices[J]. IEEE Transactions on Services Computing, 2022, 15(1): 308–321. doi: 10.1109/TSC.2019.2939836.
[67]	WANG Qingxuan, WANG Ding, CHENG Chi, et al. Quantum2FA: Efficient quantum-resistant two-factor authentication scheme for mobile devices[J]. IEEE Transactions on Dependable and Secure Computing, 2023, 20(1): 193–208. doi: 10.1109/TDSC.2021.3129512.