Research on Gate Bootstrapping in Fully Homomorphic Encryption

doi:10.3969/j.issn.1671-1122.2025.11.004

Abstract

Abstract:

Fully homomorphic encryption (FHE), a fundamental cryptographic technology that enables computation directly on encrypted data, is increasingly recognized as a core enabler for building highly secure confidential computing systems. Gate bootstrapping, as the key mechanism for supporting the evaluation of circuits with arbitrary depth, plays a decisive role in determining the practicality and efficiency of FHE in real-world applications. This article presents a comprehensive review of recent advances in gate bootstrapping, with a particular focus on classical blind rotation techniques such as AP, GINX, and LMKC+, along with their evolutionary trajectories. It further investigates efficient blind rotation schemes based on the NTRU architecture. Moreover, the article surveys mainstream fine-grained noise management strategies, including noise control in blind rotation, optimizations in modulus and key switching, and compact secret key structure design. It also summarizes representative parameter configurations and performance metrics of existing schemes, and reviews both software and hardware acceleration implementations—especially those achieving low latency and high throughput. This work provides a systematic reference and technical foundation for the application of gate bootstrapping in practical confidential computing deployments.

Key words: fully homomorphic encryption (FHE), gate bootstrapping, blind rotation, noise management, haedware acceleration

CLC Number:

TP309

CHEN Chunling, LU Xianhui, WANG Ruida, BAI Jikang, XIE Shubing. Research on Gate Bootstrapping in Fully Homomorphic Encryption[J]. Netinfo Security, 2025, 25(11): 1691-1706.

Figures/Tables 12

References 52

[1]	GENTRY C, HALEVI S, RAYKOVA M, et al. Outsourcing Private RAM Computation[C]// IEEE. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. New York: IEEE, 2014: 404-413.
[2]	GENTRY C, SAHAI A, WATERS B. Homomorphic Encryption from Learning with Errors:Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[C]// Springer.Advances in Cryptology(CRYPTO 2013). Heidelberg: Springer, 2013: 75-92.
[3]	DOWLIN N, GILAD-BACHRACH R, LAINE K, et al. CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy[C]// ICML. The 33rd International Conference on Machine Learning. New York: ICML, 2016: 201-210.
[4]	GENTRY C, HALEVI S, SMART, N P. Homomorphic Evaluation of the AES Circuit[C]// Springer.Advances in Cryptology(CRYPTO 2012). Heidelberg: Springer, 2012: 850-867.
[5]	AMUTHAN A, SENDHIL R. Hybrid GSW and DM Based Fully Homomorphic Encryption Scheme for Handling False Data Injection Attacks under Privacy Preserving Data Aggregation in Fog Computing[J]. Journal of Ambient Intelligence and Humanized Computing, 2020, 11: 5217-5231. doi: 10.1007/s12652-020-01849-8
[6]	CURTMOLA R, GARAY J, KAMARA S, et al. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions[J]. Journal of Computer Security, 2011, 19(5): 895-934. doi: 10.3233/JCS-2011-0426 URL
[7]	CASH D, JARECKI S, JUTLA C, et al. Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation[C]// NDSS. Network and Distributed System Security Symposium (NDSS 2014). San Diego: NDSS, 2014: 463-478.
[8]	PAPPAS V, KRELL F, VO B, et al. Blind Seer: A Scalable Private DBMS[C]// IEEE.2014 IEEE Symposium on Security and Privacy. New York: IEEE, 2014: 359-374.
[9]	LUO Ming, LIU Fenghao, WANG Han. Faster FHE-Based Single-Server Private Information Retrieval[C]// ACM. Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2024: 1405-1419.
[10]	IEZZI M. Practical Privacy-Preserving Data Science with Homomorphic Encryption: An Overview[C]// IEEE. 2020 IEEE International Conference on Big Data. New York: IEEE, 2020: 3979-3988.
[11]	RIVEST R L, ADLEMAN L, DEAOUZOS M L. On Data Banks and Privacy Homomorphism[J]. Foundations of Secure Computation, 1978, 4(11): 169-180.
[12]	MARCOLLA C, SUCASAS V, MANZANO M, et al. Survey on Fully Homomorphic Encryption, Theory, and Applications[J]. Proceedings of the IEEE, 2022, 110(10): 1572-1609. doi: 10.1109/JPROC.2022.3205665 URL
[13]	BOURA C, GAMA N, GEORGIEVA M, et al. Simulating Homomorphic Evaluation of Deep Learning Predictions[C]// Springer.Cyber Security Cryptography and Machine Learning. Heidelberg: Springer, 2019: 212-230.
[14]	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 URL
[15]	MATSUMOTO M, OGUCHI M. Speeding up Encryption on IoT Devices Using Homomorphic Encryption[C]// IEEE. 2021 IEEE International Conference on Smart Computing (SMARTCOMP). New York: IEEE, 2021: 270-275.
[16]	REGEV O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[J]. Journal of the ACM, 2009, 56(6): 1-40.
[17]	LYUBASHEVSKY V, PEIKERT C, REGEV O. On Ideal Lattices and Learning with Errors over Rings[C]// Springer.Advances in Cryptology (EUROCRYPT 2010). Heidelberg: Springer, 2010: 1-23.
[18]	KIRCHNER P, FOUQUE P A. Revisiting Lattice Attacks on Overstretched NTRU Parameters[C]// Springer.Advances in Cryptology (EUROCRYPT 2017). Heidelberg: Springer, 2017: 3-26.
[19]	GENTRY C. A Fully Homomorphic Encryption Scheme[D]. California: Stanford University, 2009.
[20]	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V. (Leveled) Fully Homomorphic Encryption without Bootstrapping[J]. ACM Transactions on Computation Theory, 2014, 6(3): 1-36.
[21]	BRAKERSKI Z, VAIKUNTANATHAN V. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages[C]// Springer.Advances in Cryptology(CRYPTO 2011). Heidelberg: Springer, 2011: 505-524.
[22]	FAN J, VERCAUTEREN F. Somewhat Practical Fully Homomorphic Encryption[EB/OL]. (2012-06-26)[2025-11-13]. https://eprint.iacr.org/2012/144.
[23]	CHEON J H, KIM A, KIM M, et al. Homomorphic Encryption for Arithmetic of Approximate Numbers[C]// Springer.Advances in Cryptology (ASIACRYPT 2017). Heidelberg: Springer, 2017: 409-437.
[24]	CHEON J H, HAN K, KIM A, et al. Bootstrapping for Approximate Homomorphic Encryption[C]// Springer.Advances in Cryptology (EUROCRYPT 2018). Heidelberg: Springer, 2018: 360-384.
[25]	DUCAS L, MICCIANCIO D. FHEW: Bootstrapping Homomorphic Encryption in Less than a Second[C]// Springer.Advances in Cryptology (EUROCRYPT 2015). Heidelberg: Springer, 2015: 617-640.
[26]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster Fully Homomorphic Encryption: Bootstrapping in Less than 0.1 Seconds[C]// Springer.Advances in Cryptology (ASIACRYPT 2016). Heidelberg: Springer, 2016: 3-33.
[27]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster Packed Homomorphic Operations and Efficient Circuit Bootstrapping for TFHE[C]// Springer.Advances in Cryptology (ASIACRYPT 2017). Heidelberg: Springer, 2017: 377-408.
[28]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. TFHE: Fast Fully Homomorphic Encryption over the Torus[J]. Journal of Cryptology, 2020, 33(1): 34-91. doi: 10.1007/s00145-019-09319-x
[29]	MICCIANCIO D, POLYAKOV Y. Bootstrapping in FHEW-Like Cryptosystems[C]// ACM. The 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography. New York: ACM, 2021: 17-28.
[30]	LEE Y, MICCIANCIO D, KIM A, et al. Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption[C]// Springer.Advances in Cryptology (EUROCRYPT 2023). Heidelberg: Springer, 2023: 227-256.
[31]	XIANG Binwu, ZHANG Jiang, DENG Yi, et al. Fast Blind Rotation for Bootstrapping FHEs[C]// Springer.Advances in Cryptology(CRYPTO 2023). Heidelberg: Springer, 2023: 3-36.
[32]	LI Zhihao, LU Xianhui, WANG Zhiwei, et al. Faster NTRU-Based Bootstrapping in less than 4 ms[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(3): 418-451.
[33]	LI Zhihao, LIU Ying, LU Xianhui, et al. Faster Bootstrapping via Modulus Raising and Composite NTT[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(1): 563-591.
[34]	CHEN Chunling, LU Xianhui, XIANG Binwu, et al. Refined Error Management for Gate Bootstrapping[C]// Springer.Information Security and Privacy. Heidelberg: Springer, 2025: 252-274.
[35]	ALPERIN-SHERIFF J, PEIKERT C. Faster Bootstrapping with Polynomial Error[C]// Springer.Advances in Cryptology (CRYPTO 2014). Heidelberg: Springer, 2014: 297-314.
[36]	KIM A, LEE Y, DERYABIN M, et al. LFHE: Fully Homomorphic Encryption with Bootstrapping Key Size Less than a Megabyte[EB/OL]. (2023-05-26)[2025-11-12]. https://eprint.iacr.org/2023/767.
[37]	GAMA N, IZABACHÈNE M, NGUYEN P Q, et al. Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems[C]// Springer.Advances in Cryptology (EUROCRYPT 2016). Heidelberg: Springer, 2016: 528-558.
[38]	BONTE C, ILIASHENKO I, PARK J, et al. FINAL: Faster FHE Instantiated with NTRU and LWE[C]// Springer.Advances in Cryptology (ASIACRYPT 2022). Heidelberg: Springer, 2022: 188-215.
[39]	PEREIRA H V L. Bootstrapping Fully Homomorphic Encryption over the Integers in Less than One Second[C]// Springer.Public-Key Cryptography(PKC 2021). Heidelberg: Springer, 2021: 331-359.
[40]	BONTE C, ILIASHENKO I, PARK J, et al. FINAL: Faster FHE Instantiated with NTRU and LWE[C]// Springer.Advances in Cryptology (ASIACRYPT 2022). Heidelberg: Springer, 2022: 188-215.
[41]	GENTRY C, HALEVI S, SMART N P. Homomorphic Evaluation of the AES Circuit[C]// Springer.Advances in Cryptology(CRYPTO 2012). Heidelberg: Springer, 2012: 850-867.
[42]	ALBRECHT M R, PLAYER R, SCOTT S. On the Concrete Hardness of Learning with Errors[J]. Journal of Mathematical Cryptology, 2015, 9(3): 169-203. doi: 10.1515/jmc-2015-0016 URL
[43]	ALKIM E, DUCAS L, POPPELMANN T, et al. Post-Quantum Key Exchange: A New Hope[C]// USENIX. The 25th USENIX Conference on Security Symposium. Berkeley: USENIX, 2016: 327-343.
[44]	DUCAS L, VAN WOERDEN W. NTRU Fatigue: How Stretched is Overstretched[C]// Springer.Advances in Cryptology (ASIACRYPT 2021). Heidelberg: Springer, 2021: 3-32.
[45]	XIANG Binwu, ZHANG Jiang, WANG Kaixing, et al. NTRU-Based Bootstrapping for MK-FHEs without Using Overstretched Parameters[C]// Springer.Advances in Cryptology (ASIACRYPT 2024). Heidelberg: 2024: 241-270.
[46]	ALBRECHT M R, PLAYER R, SCOTT S. On the Concrete Hardness of Learning with Errors[J]. Journal of Mathematical Cryptology, 2015, 9(3): 169-203. doi: 10.1515/jmc-2015-0016 URL
[47]	MATSUOKA K, BANNO R, MATSUMOTO, et al. Virtual Secure Platform: A Five-Stage Pipeline Processor over TFHE[C]// USENIX.USENIX Security Symposium. Berkeley: USENIX,2021: 4007-4024.
[48]	ZAMA. TFHE-rs: A Pure Rust Implementation of the TFHE Scheme for Boolean and Integer Arithmetics over Encrypted Data[EB/OL]. [2025-06-23]. https://github.com/zama-ai/tfhe-rs.
[49]	VANBEIREN DONCK M, D’ANVERS J P, TURAN F, et al. FPT: A Fixed-Point Accelerator for Torus Fully Homomorphic Encryption[C]// ACM. The 2023 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2023: 741-745.
[50]	JIANG Lei, LOU Qian, JOSHI N. MATCHA: A Fast and Energy-Efficient Accelerator for Fully Homomorphic Encryption over the Torus[C]// ACM. The 59th ACM/IEEE Design Automation Conference. New York: ACM, 2022: 235-240.
[51]	PUTRA A, PRASETIYO, CHEN Yi, et al. Strix: An End-to-End Streaming Architecture with Two-Level Ciphertext Batching for Fully Homomorphic Encryption with Programmable Bootstrapping[C]// ACM. The 56th Annual IEEE/ACM International Symposium on Microarchitecture. New York: ACM, 2023: 1319-1331.
[52]	PRASETIYO, PUTRA A, KIM J Y. Morphling: A Throughput-Maximized TFHE-Based Accelerator Using Transform-Domain Reuse[C]// IEEE. 2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA). New York: IEEE, 2024: 249-262.

方案分类	主要特征	典型应用场景
BFV/BGV^[20-22]	有限域上的精确算术	精确整数计算
CKKS^[23,24]	支持近似算术，适用于实数/复数	机器学习、统计分析
FHEW/TFHE^[25-28]	高效逐比特布尔逻辑运算	布尔电路评估

方法	底层结构	方法类型	参数	密钥分布	#NTT/FFT	BSK/bit
FHEW^[25,35]	RLWE	AP	STD128^[29]	三元	$2\text{(}1-\frac{1}{{{B}_{r}}}\text{)}n{{d}_{r}}\text{(}l+1\text{)}$	$\begin{align} & 4nN{{d}_{r}}\text{(}{{B}_{r}}- \\ & 1\text{)}l{{\log }_{2}}Q \\ \end{align}$
TFHE^[26,28,29]	RLWE	GINX	STD128^[29]	三元	$4n(l+1)$	$8nlN{{\log }_{2}}Q$
LMKC+^[30]	RLWE	Automorphism	LMKC128G^[30]	高斯	$l(3n+2)$	$6nlN{{\log }_{2}}Q$
Final^[38]	NTRU	GINX	PT128T^[31]	三元	$n(l+1)$	$2nlN{{\log }_{2}}Q$
XZD+^[31]	NTRU	Automorphism GINX	P128G^[31] P128T^[31]	高斯三元	$l(2n+1)$ $n(l+1)$	$2nlN{{\log }_{2}}Q$ $2nlN{{\log }_{2}}Q$
LLW+^[32]	NTRU	GINX	STD128B^[32]	二元	$n(l+1)$	$nlN{{\log }_{2}}Q$
CXL+^[34]	NTRU	Automorphism	C128B2Q25^[34]	二元	$n(l+1)$	$nlN{{\log }_{2}}Q$

方法	密钥分布	噪声公式
AP^[25,35,39]	二元三元	${{l}_{r}}lnN\frac{{{B}^{2}}}{6}\sigma _{e}^{2}$ $2{{l}_{r}}lnN\frac{{{B}^{2}}}{6}\sigma _{e}^{2}$
GINX^[26-29]	二元三元	$\|U\|lnN\frac{{{B}^{2}}}{6}\sigma _{e}^{2}$ $2\|U\|lnN\frac{{{B}^{2}}}{6}\sigma _{e}^{2}$
LMKC+^[30]	高斯	$(3n+2)lN\frac{{{B}^{2}}}{12}\sigma _{e}^{2}$
FINAL^[40]	三元	$nlnN\frac{{{B}^{2}}}{6}\sigma _{g}^{2}$
XZD+^[31]	高斯三元	$(2n+1)lN\frac{{{B}^{2}}}{12}\sigma _{g}^{2}$ $nlnN\frac{{{B}^{2}}}{6}\sigma _{g}^{2}$
LLW+^[32]	二元	$lnN\frac{{{B}^{2}}}{12}\sigma _{g}^{2}$

参数	$\lambda $	Key Distr.	$n$	$q$	$N$	$Q$	${{Q}_{ks}}$	${{B}_{br}}$	${{l}_{br}}$	${{B}_{ks}}$	${{l}_{ks}}$	$\text{FR}$
CSTD128B	128	二元	571	2¹¹	1024	2²⁵	2¹⁴	2⁷	2	2¹⁴	1	2^-40.7
CSTD128B1	128	二元	532	2¹¹	1024	2²⁵	2¹³	2⁷	2	2¹³	1	2^-28.2
CSTD128T	128	二元	512	2¹¹	1024	2²⁷	2¹⁴	2⁹	2	2¹⁴	1	2^-63
CSTD128G	128	高斯	458	2¹¹	1024	2²⁸	2¹³	2⁹	2	2¹³	1	2^-52

参数	$\lambda $	NTRU			LWE										FR
参数	$\lambda $	$N$	$Q$	Key Distr.	${{\sigma }_{N}}$	n	q	Key	$\sigma $	${{B}_{br}}$	${{l}_{br}}$	$l_{br}^{{'}}$	${{Q}_{ks}}$	${{B}_{ks}}$	${{l}_{ks}}$
C128B2Q25	128	1024	2²⁵	高斯	3.5	532	2¹¹	二元	3.19	2⁸	4	2	2¹³	2¹³	1	2^-47
C128G2Q25	128	1024	2²⁵	高斯	3.5	465	2¹¹	高斯	3.19	2⁸	4	2	2¹⁴	2¹⁴	1	2^-59