Bootstrapping Optimization Techniques for the FINAL Fully Homomorphic Encryption Scheme

ZHAO Xiufeng; WU Meng; SONG Weitao

doi:10.11999/JEIT241036

Volume 47 Issue 7

Jul. 2025

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 > 47(7): 2183-2193

ZHAO Xiufeng, WU Meng, SONG Weitao. Bootstrapping Optimization Techniques for the FINAL Fully Homomorphic Encryption Scheme[J]. Journal of Electronics & Information Technology, 2025, 47(7): 2183-2193. doi: 10.11999/JEIT241036

Citation:

ZHAO Xiufeng, WU Meng, SONG Weitao. Bootstrapping Optimization Techniques for the FINAL Fully Homomorphic Encryption Scheme[J]. Journal of Electronics & Information Technology, 2025, 47(7): 2183-2193. doi: 10.11999/JEIT241036

Citation:

PDF( 4248 KB)

Bootstrapping Optimization Techniques for the FINAL Fully Homomorphic Encryption Scheme

doi: 10.11999/JEIT241036 cstr: 32379.14.JEIT241036

College of Cryptography Engineering Information Engineering University, Zhengzhou 450001, China

Funds: The National Cryptologic Science Fund of China (2025NCSF02044), The Fund of Laboratory for Advanced Computing and Intelligence Engineering (2023-LYJJ-01-002)

Received Date: 2024-11-22
Rev Recd Date: 2025-05-19

Available Online: 2025-06-24

Publish Date: 2025-07-22

Abstract

Abstract

Objective Bootstrapping is a fundamental process in Fully Homomorphic Encryption (FHE) that directly affects its practical efficiency. The FINAL scheme, presented at ASIACRYPT 2022, achieves a 28% improvement in bootstrapping speed compared with TFHE, demonstrating high suitability for homomorphic Boolean operations. Nevertheless, further improvements are required to reduce its computational overhead and storage demands. This study aims to optimize the bootstrapping phase of FINAL by lowering its computational complexity and key size while preserving the original security level. Methods This study proposes two key optimizations. Accumulator compression for blind rotation: A blockwise binary distribution is incorporated into the Learning With Errors (LWE) key generation process. By organizing the key into blocks, each requiring only a single external product, the number of external product operations during blind rotation is reduced. Key reuse strategy for key switching: The LWE key is partially reused during the generation of the Number-theoretic Gadget Switching (NGS) key. The reused portion is excluded from the key switching key, thereby reducing both the key size and the number of associated operations. Results and Discussions Under equivalent security assumptions, the optimized FINAL scheme yields substantial efficiency gains. For blind rotation, the number of external product operations is reduced by 50% (from 610 to 305), and the number of Fast Fourier Transform (FFT) operations is halved (from 3,940 to 1,970) (Table 5). For key switching, the key size is reduced by 60% (from 11,264 to 4,554), and the computational complexity decreases from 13.8 × 10⁶ to 5.6× 10⁶ scalar operations (Table 6). Conclusions The proposed optimizations substantially improve the efficiency of the FINAL scheme’s bootstrapping phase. Blind rotation benefits from structured key partitioning, reducing the number of core operations by half. Key switching achieves comparable reductions in both storage requirements and computational cost through partial key reuse. These enhancements improve the practicality of FHE for real-world applications that demand efficient evaluation of Boolean circuits. Future directions include hardware acceleration and adaptive parameter tuning.
- Fully Homomorphic Encryption (FHE),
- FINAL,
- Bootstrapping,
- Blind rotation,
- Key switching

FullText(HTML)

References(27)

References

[1]	GENTRY C. Fully homomorphic encryption using ideal lattices[C]. The Forty-First Annual ACM Symposium on Theory of Computing, Bethesda, USA, 2009: 169–178. doi: 10.1145/1536414.1536440.
[2]	BRAKERSKI Z, GENTRY C, and VAIKUNTANATHAN V. (Leveled) fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory (TOCT), 2014, 6(3): 13. doi: 10.1145/2633600.
[3]	BRAKERSKI Z. Fully homomorphic encryption without modulus switching from classical GapSVP[C]. The 32nd Annual Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2012: 868–886. doi: 10.1007/978-3-642-32009-5_50.
[4]	FAN Junfeng and VERCAUTEREN F. Somewhat practical fully homomorphic encryption[EB/OL]. https://eprint.iacr.org/2012/144, 2012.
[5]	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 on Advances in Cryptology, Santa Barbara, USA, 2013: 75–92. doi: 10.1007/978-3-642-40041-4_5.
[6]	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 Advances in Cryptology, Hong Kong, China, 2017: 409–437. doi: 10.1007/978-3-319-70694-8_15.
[7]	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 Advances in Cryptology, Sofia, Bulgaria, 2015: 617–640. doi: 10.1007/978-3-662-46800-5_24.
[8]	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.
[9]	CARPOV S, IZABACHÈNE M, and MOLLIMARD V. New techniques for multi-value input homomorphic evaluation and applications[C]. The Cryptographers’ Track at the RSA Conference 2019 Topics in Cryptology, San Francisco, USA, 2019: 106–126. doi: 10.1007/978-3-030-12612-4_6.
[10]	CHILLOTTI I, LIGIER D, ORFILA J B, et al. Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE[C]. The 27th International Conference on the Theory and Application of Cryptology and Information Security Advances in Cryptology, Singapore, Singapore, 2021: 670–699. doi: 10.1007/978-3-030-92078-4_23.
[11]	GUIMARÃES A, BORIN E, and ARANHA D F. Revisiting the functional bootstrap in TFHE[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021, 2021(2): 229–253. doi: 10.46586/tches.v2021.i2.229-253.
[12]	CHEN Hao, CHILLOTTI I, and SONG Y. Multi-key homomorphic encryption from TFHE[C]. The 25th International Conference on the Theory and Application of Cryptology and Information Security Advances in Cryptology, Kobe, Japan, 2019: 446–472. doi: 10.1007/978-3-030-34621-8_16.
[13]	KWAK H, MIN S, and SONG Y. Towards practical multi-key TFHE: Parallelizable, key-compatible, quasi-linear complexity[C]. The 27th IACR International Conference on Practice and Theory of Public-Key Cryptography Public-Key Cryptography, Sydney, Australia, 2024: 354–385. doi: 10.1007/978-3-031-57728-4_12.
[14]	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 Advances in Cryptology, Taipei, China, 2022: 188–215. doi: 10.1007/978-3-031-22966-4_7.
[15]	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.
[16]	LEE Y, MICCIANCIO D, KIM A, et al. Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption[C]. The 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology, Lyon, France, 2023: 227–256. doi: 10.1007/978-3-031-30620-4_8.
[17]	LEE C, MIN S, SEO J, et al. Faster TFHE bootstrapping with block binary keys[C]. The 2023 ACM Asia Conference on Computer and Communications Security, Melbourne, Australia, 2023: 2–13. doi: 10.1145/3579856.3595804.
[18]	XIANG Binwu, ZHANG Jiang, DENG Yi, et al. Fast blind rotation for bootstrapping FHEs[C]. The 43rd Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2023: 3–36. doi: 10.1007/978-3-031-38551-3_1.
[19]	MA Shihe, HUANG Tairong, WANG Anyu, et al. Accelerating BGV bootstrapping for large p using null polynomials over $ \mathbb{Z}_{p^{e}} $[C]. The 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology, Zurich, Switzerland, 2024: 403–432. doi: 10.1007/978-3-031-58723-8_14.
[20]	WANG Ruida, WEN Yundi, LI Zhihao, et al. Circuit bootstrapping: Faster and smaller[C]. The 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology, Zurich, Switzerland, 2024: 342–372. doi: 10.1007/978-3-031-58723-8_12.
[21]	PEIKERT C. A decade of lattice cryptography[J]. Foundations and Trends^® in Theoretical Computer Science, 2016, 10(4): 283–424. doi: 10.1561/0400000074.
[22]	GOLDWASSER S, KALAI Y, PEIKERT C, et al. Robustness of the learning with errors assumption[C]. Proceedings of the Innovations in Computer Science–ICS 2010, Beijing, China, 2010: 230–240.
[23]	ALBRECHT M R. On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL[C]. The 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology, Paris, France, 2017: 103–129. doi: 10.1007/978-3-319-56614-6_4.
[24]	MAY A. How to meet ternary LWE keys[C]. The 41st Annual International Cryptology Conference on Advances in Cryptology, 2021: 701–731. doi: 10.1007/978-3-030-84245-1_24.
[25]	ALBRECHT M R, PLAYER R, and 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.
[26]	CHEN Yuanmi and NGUYEN P Q. BKZ 2.0: Better lattice security estimates[C]. The 17th International Conference on the Theory and Application of Cryptology and Information Security Advances in Cryptology, Seoul, South Korea, 2011: 1–20. doi: 10.1007/978-3-642-25385-0_1.
[27]	GUO Qian and JOHANSSON T. Faster dual lattice attacks for solving LWE with applications to CRYSTALS[C]. The 27th International Conference on the Theory and Application of Cryptology and Information Security Advances in Cryptology, Singapore, Singapore, 2021: 33–62. doi: 10.1007/978-3-030-92068-5_2.