Design and Implementation of an FPGA-Based Bootstrapping Accelerator for Torus Fully Homomorphic Encryption
-
摘要: 环面全同态加密(Torus Fully Homomorphic Encryption, TFHE)支持在密文域上直接评估布尔电路，是隐私计算领域的重要密码学技术。然而，TFHE在密文运算过程中会产生噪声累积，需通过自举操作刷新密文噪声。由于自举过程涉及大规模多项式运算和密钥数据访问，其计算复杂度高、访存开销大，已成为制约TFHE实用化部署的主要性能瓶颈。针对上述问题，本文设计并实现了一种基于现场可编程门阵列(Field-Programmable Gate Array, FPGA)的TFHE自举专用硬件加速器。该加速器采用全硬件化流水数据通路，可在无需中央处理器(Central Processing Unit, CPU)参与核心计算的情况下独立完成自举操作流程；同时设计了数论变换(Number Theoretic Transform, NTT)加速模块，以提高多项式乘法运算效率并降低自举延迟。针对自举密钥数据规模庞大、片外访存压力高的特点，本文进一步引入批处理机制，以提升密钥数据复用率和系统吞吐量，在保持合理单次自举延迟的同时，显著提升了批量自举吞吐率。本设计在Xilinx Alveo U280 FPGA平台上完成部署与验证，实验结果表明，在300 MHz工作频率下，其可在3.9 ms内完成8个密文的自举操作，平均单个密文自举延迟为0.49 ms。与现有CPU和GPU自举加速方案相比，本文设计在批处理吞吐能力方面分别实现约21.8倍和6.0倍提升。
-
关键词:
- 环面全同态加密 /
- 可编程自举 /
- 数论变换 /
- 批处理机制 /
- FPGA专用硬件加速器
Abstract:Objective Torus Fully Homomorphic Encryption (TFHE) is an important cryptographic technique for privacy-preserving computation, as it enables Boolean circuits to be evaluated directly over encrypted data. In TFHE, programmable bootstrapping refreshes ciphertext noise while evaluating a user-defined lookup-table function, thereby providing a flexible foundation for secure inference, encrypted data processing, and privacy-preserving cloud services. However, bootstrapping remains the major performance bottleneck of TFHE. A complete bootstrapping procedure consists of modulus switching, blind rotation, sample extraction, and identity key switching. Among these operations, blind rotation and key switching involve intensive polynomial arithmetic and frequent accesses to large bootstrapping keys and key switching keys. Consequently, software implementations usually suffer from high latency and limited throughput, which limits the deployment of TFHE in practical high-throughput applications. To overcome this limitation, this paper proposes an FPGA-based accelerator for TFHE programmable bootstrapping. The objective is to improve bootstrapping execution efficiency by combining a dedicated streaming data path, an optimized Number Theoretic Transform (NTT)-based polynomial multiplication module, and a batching mechanism oriented toward bootstrapping key reuse. Methods A fully hardware-based streaming architecture is designed to map the main stages of TFHE programmable bootstrapping onto dedicated FPGA. The accelerator consists of a test vector generation module, a polynomial rotation module, a decomposition module, an element-wise multiplication module, a sample extraction module, and an identity key switching module. These modules are connected through on-chip buffers and streaming interfaces, enabling the bootstrapping data path to execute in a pipelined manner. Compared with CPU-like control-oriented architectures, the proposed architecture reduces instruction scheduling and centralized control overhead, and is suitable for continuous processing of multiple ciphertexts. To accelerate the external product in the CMUX operation, a Radix-32 Four-Step Number Theoretic Transform (NTT) module is developed for polynomial multiplication. The required 1024 -point NTT is decomposed into smaller 32-point NTT operations, reducing the hardware complexity of directly implementing a large-size NTT. A negative-cycle NTT method is further adopted to avoid zero-padding and reduce redundant computation. In addition, a generalized Mersenne prime, also known as the Goldilocks prime, is used as the NTT modulus. By exploiting its special form, part of the twiddle-factor multiplication and modular reduction operations can be converted into shifts, additions, and subtractions. For the 192-bit intermediate data generated in the Radix-32 NTT pipeline, a large-word modular reduction method is designed to avoid costly division-based modular reduction. To alleviate off-chip memory traffic caused by bootstrapping key accesses, a ciphertext batching mechanism is introduced. Multiple TLWE ciphertexts sharing the same bootstrapping key are organized as a batch. After a portion of the bootstrapping key is loaded into the on-chip buffer, it can be reused by multiple ciphertexts in the same batch. Meanwhile, the key data required for subsequent computation are prefetched to partially hide off-chip memory access latency.Results and Discussions The proposed accelerator is implemented and evaluated on a Xilinx Alveo U280 FPGA platform. The platform provides HBM2 memory with multiple independent channels to support high-bandwidth accesses to input TLWE ciphertexts, bootstrapping keys, key switching keys, and output ciphertexts. Different HBM channels are allocated according to the bandwidth requirements of different data types. Several channels are used for bootstrapping key transfer to match the throughput demand of the NTT-based polynomial multiplication module, while more channels are assigned to the key switching key to support the high access rate of the identity key switching module. In the physical implementation, the element-wise multiplication module is placed across different super logic regions to balance resource utilization and reduce timing pressure. Experimental results show that the proposed accelerator correctly completes TFHE programmable bootstrapping on the FPGA platform. Under the same TFHE parameter setting, it achieves higher bootstrapping efficiency than existing CPU and GPU implementations. Benefiting from the streaming pipeline and ciphertext batching mechanism, the proposed design also improves bootstrapping throughput compared with previous FPGA-based accelerators. These results indicate that the proposed architecture reduces polynomial multiplication cost and improves bootstrapping key reuse. The batching mechanism amortizes the loading cost of the bootstrapping key over multiple ciphertexts, thereby alleviating the off-chip memory bottleneck. Resource utilization results show that the accelerator consumes a moderate amount of LUT, register, BRAM, and DSP resources on the Alveo U280 platform, leaving room for further parallel extension. Power evaluation also shows that the proposed design achieves a reasonable trade-off among throughput, resource consumption, and energy efficiency. Although the absolute latency is still affected by the sequential dependency of blind rotation iterations and off-chip key accesses, the overall throughput is significantly improved in batch-processing scenarios. Conclusions A dedicated FPGA accelerator for TFHE programmable bootstrapping is presented in this paper. The proposed design introduces a fully hardware-based streaming bootstrapping architecture, an efficient Radix-32 Four-Step NTT module with large-word modular reduction, and a ciphertext batching mechanism for bootstrapping key reuse. These techniques jointly reduce control overhead, polynomial multiplication cost, and repeated off-chip memory accesses. The implementation results on the Alveo U280 FPGA platform demonstrate that the accelerator correctly executes TFHE programmable bootstrapping and achieves high throughput under practical hardware resource constraints. Therefore, the proposed accelerator provides an effective hardware implementation approach for high-throughput privacy-preserving computation based on TFHE. Future work may further explore larger-scale parallelism, more flexible parameter support, and tighter integration with privacy-preserving application workloads. -
表 1 TFHE算法相关符号
符号 定义 $ \lambda $ 加密参数 $ Z $ 整数集 $ R $ 实数集 $ B $ 二进制数集，即{0,1} $ T $ 实数环面，即全部实数模1后的集合 $ {\boldsymbol{T}}_{\boldsymbol{N}}[\boldsymbol{X}] $ N-1阶多项式在$ \boldsymbol{R}[\boldsymbol{X}]/({\boldsymbol{X}}^{\boldsymbol{N}}+\mathbf{1}) $模1下的表示 $ {\boldsymbol{B}}_{\boldsymbol{N}}[\boldsymbol{X}] $ N-1阶多项式在$ \boldsymbol{R}[\boldsymbol{X}]/({\boldsymbol{X}}^{\boldsymbol{N}}+\mathbf{1}) $模1下的表示，
系数来于B
下载: 导出CSV
表 3 不同TFHE自举加速方案对比
方案 平台 频率(MHz) 自举延迟(ms) 吞吐率(PBS/ms) 资源(LUT, FF, DSP, BRAM) 功耗(w) TFHE[6] CPU 2900 11.5 0.09 - - cuFHE[7] GPU 1700 11.3 0.34 - - MATCHA[8] ASIC 2000 0.16 10 - 40 HOGE[10] FPGA 295 1.6 0.63 216K 238K 1024 12.9Mb35.5 FPT[9] FPGA 200 0.74 28.4 595K 1024K 5980 14.5Mb99 UNIT[11] FPGA 200 2.077 - 377K 316K 6060 18.3Mb27.5 本文设计 FPGA 300 3.9 2.05 334K 353K 1590 21.2Mb37.7
下载: 导出CSV
-
[1] YAO Yifan, DUAN Jinhao, XU Kaidi, et al. A survey on large language model (LLM) security and privacy: The Good, The Bad, and The Ugly[J]. High-Confidence Computing, 2024, 4(2): 100211. doi: 10.1016/j.hcc.2024.100211. [2] CHEN Kang, ZHOU Xiuze, LIN Yuanguo, et al. A survey on privacy risks and protection in large language models[J]. Journal of King Saud University Computer and Information Sciences, 2025, 37(7): 163. doi: 10.1007/s44443-025-00177-1. [3] GENTRY C. Fully homomorphic encryption using ideal lattices[C]. Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, Bethesda, USA, 2009: 169–178. doi: 10.1145/1536414.1536440. [4] 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. [5] CHILLOTTI I, JOYE M, and PAILLIER P. Programmable bootstrapping enables efficient homomorphic inference of deep neural networks[C]. 5th International Symposium Cyber Security Cryptography and Machine Learning, Be’er Sheva, Israel, 2021: 1–19. doi: 10.1007/978-3-030-78086-9_1. [6] 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. [7] DAI W. cuFHE: CUDA-accelerated fully homomorphic encryption library[EB/OL]. https://github.com/vernamlab/cuFHE. (查阅网上资料,未找到本条文献信息,请确认). [8] JIANG Lei, LOU Qian, and JOSHI N. MATCHA: A fast and energy-efficient accelerator for fully homomorphic encryption over the torus[C]. Proceedings of the 59th ACM/IEEE Design Automation Conference, San Francisco, USA, 2022: 235–240. doi: 10.1145/3489517.3530435. [9] VAN BEIRENDONCK M, D'ANVERS J P, TURAN F, et al. FPT: A fixed-point accelerator for torus fully homomorphic encryption[C]. Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, Copenhagen, Denmark, 2023: 741–755. doi: 10.1145/3576915.3623159. [10] MATSUOKA K, BIAN Song, and SATO T. HOGE: Homomorphic gate on an FPGA[C]. Proceedings of the 29th Asia and South Pacific Design Automation Conference, Incheon, Republic of Korea, 2024: 325–332. doi: 10.1109/ASP-DAC58780.2024.10473861. [11] ZHANG Yuying, SINHA S, XU Jiang, et al. UNIT: A highly unified and memory-efficient FPGA-based accelerator for torus FHE[C]. 2025 Design, Automation & Test in Europe Conference (DATE), Lyon, France, 2025: 1–7. doi: 10.23919/DATE64628.2025.10993051. [12] ZHANG Jian, CUI Aijiao, and JIN Yier. Acceleration of the bootstrapping in TFHE by FPGA[J]. IEEE Transactions on Emerging Topics in Computing, 2025, 13(2): 496–511. doi: 10.1109/TETC.2024.3433473. [13] XIAO Yu, LIU Fenghao, KU Yute, et al. GPU acceleration for FHEW/TFHE bootstrapping[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024, 2025(1): 314–339. doi: 10.46586/tches. v2025. i1.314-339. [14] 李冰, 刘怀骏, 张伟功. 魔方派: 面向全同态加密的存算模运算加速器设计[J]. 电子与信息学报, 2023, 45(9): 3302–3310.LI Bing, LIU Huaijun, and ZHANG Weigong. M2PI: Processing-in-memory modular computing accelerator for full homomorphic encryption[J]. Journal of Electronics & Information Technology, 2023, 45(9): 3302–3310. [15] BAILEY D H. FFTs in external or hierarchical memory[C]. Proceedings of the 1989 ACM/IEEE Conference on Supercomputing, Reno, USA, 1989: 234–242. doi: 10.1145/76263.76288. [16] LONGA P and NAEHRIG M. Speeding up the number theoretic transform for faster ideal lattice-based cryptography[C]. 15th International Conference Cryptology and Network Security, Milan, Italy, 2016: 124–139. doi: 10.1007/978-3-319-48965-0_8. [17] REGEV O. The learning with errors problem (invited survey)[C]. Proceedings of the 2010 IEEE 25th Annual Conference on Computational Complexity, Cambridge, USA, 2010: 191–204. doi: 10.1109/CCC.2010.26. [18] TRAMA D, BOUDGUIGA A, CLET P E, et al. Designing a general-purpose 8-bit (T)FHE processor abstraction[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025, 2025(2): 535–578. doi: 10.46586/tches.v2025.i2.535-578. [19] XIA Han and WANG Mingsheng. Efficient and compact full-domain functional bootstrapping via subring folding[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025, 2025(4): 737–762. doi: 10.46586/tches.v2025.i4.737-762. [20] 何仁华, 李冰, 杜一博, 等. 基于容错学习问题的全同态加密算法和硬件优化综述[J]. 计算机研究与发展, 2025, 62(7): 1738–1753. doi: 10.7544/issn1000-1239.202331022.HE Renhua, LI Bing, DU Yibo, et al. Survey on algorithm and hardware optimization to LWE-based fully homomorphic encryption[J]. Journal of Computer Research and Development, 2025, 62(7): 1738–1753. doi: 10.7544/issn1000-1239.202331022. [21] 施佺, 韩赛飞, 黄新明, 等. 面向全同态加密的有限域FFT算法FPGA设计[J]. 电子与信息学报, 2018, 40(1): 57–62. doi: 10.11999/JEIT170312.SHI Quan, HAN Saifei, HUANG Xinming, et al. Design of finite field FFT for fully homomorphic encryption based on FPGA[J]. Journal of Electronics & Information Technology, 2018, 40(1): 57–62. doi: 10.11999/JEIT170312. [22] ZAMAN M A, KHAN M B, AHMAD W, et al. A lightweight and hardware-efficient NTT FPGA accelerator for FHE applications[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2026, 73(1): 78–82. doi: 10.1109/TCSII.2025.3633181. [23] DENG Xianglong, FAN Shengyu, HU Zhicheng, et al. Trinity: A general purpose FHE accelerator[C]. 2024 57th IEEE/ACM International Symposium on Microarchitecture, Austin, USA, 2024: 338–351. doi: 10.1109/MICRO61859.2024.00033. [24] 边松, 毛苒, 朱永清, 等. 全同态加密软硬件加速研究进展[J]. 电子与信息学报, 2024, 46(7): 1790–1805. doi: 10.11999/JEIT230448.BIAN Song, MAO Ran, ZHU Yongqing, et al. A survey on software-hardware acceleration for fully homomorphic encryption[J]. Journal of Electronics & Information Technology, 2024, 46(7): 1790–1805. doi: 10.11999/JEIT230448. -
下载:
图(6) / 表(3)
计量
- 文章访问数: 12
- HTML全文浏览量: 1
- PDF下载量: 0
- 被引次数: 0
