A Low-Cost Twiddle Tactor Generator for Fully Homomorphic Encryption

FU Qiu-xing; LI Wei; BIE Meng-ni; CHEN Tao; DU Yi-ran; NAN Long-mei

doi:10.12263/DZXB.20250301

您当前的位置：

首页 >

文章列表页 >

A Low-Cost Twiddle Tactor Generator for Fully Homomorphic Encryption

PAPERS | 更新时间：2025-12-27

- A Low-Cost Twiddle Tactor Generator for Fully Homomorphic Encryption
- ACTA ELECTRONICA SINICA Vol. 53, Issue 8, Pages: 2936-2945(2025)
- 作者机构：
  
  信息工程大学，河南郑州 450001
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62302519)
- DOI：10.12263/DZXB.20250301
  CLC： TN402;TP309
- Received：19 April 2025，
  
  Accepted：21 August 2025，
  
  Published：25 August 2025
- 稿件说明：
移动端阅览
付秋兴, 李伟, 别梦妮, 等. 一种面向全同态加密的低成本旋转因子发生器[J]. 电子学报, 2025, 53(08): 2936-2945.

FU Qiu-xing, LI Wei, BIE Meng-ni, et al. A Low-Cost Twiddle Tactor Generator for Fully Homomorphic Encryption[J]. Acta Electronica Sinica, 2025, 53(08): 2936-2945.
付秋兴, 李伟, 别梦妮, 等. 一种面向全同态加密的低成本旋转因子发生器[J]. 电子学报, 2025, 53(08): 2936-2945. DOI：10.12263/DZXB.20250301

FU Qiu-xing, LI Wei, BIE Meng-ni, et al. A Low-Cost Twiddle Tactor Generator for Fully Homomorphic Encryption[J]. Acta Electronica Sinica, 2025, 53(08): 2936-2945. DOI：10.12263/DZXB.20250301

摘要

全同态加密和后量子密码严重依赖数论变换（Number Theory Transformation，NTT）来加速多项式乘法，随着NTT多项式维度的提升，旋转因子的存储和传输对系统的影响愈发严重，为了解决这一问题，本文设计了一款面向全同态加密的低面积成本的旋转因子发生器.本文首先分析了NTT算法的旋转因子调用规律，提出了一种动态旋转因子生成方案，通过数据生成和覆盖，将旋转因子压缩至原有存储空间的0.12%，在执行维度为65 536的NTT运算时，仅需78个单位的存储成本.其次，本文基于全同态加密中RNS-CKKS方案，评估出了120个具有低汉明权重的60位宽的素数模，并设计了一种轻量级的Barrett模乘算法，基于该算法设计出了一种低面积成本模乘单元.最后，本文基于动态旋转因子生成方案，实现了一款面向全同态加密的Radix-16 NTT蝶形单元的低成本动态旋转因子发生器，满足全同态加密中NTT运算的实际需求.为进一步验证本文硬件设计的优越性，在Zynq UltraScale+XCZU9EG器件上进行实验验证，工作频率达252 MHz，Slice资源消耗降低了15%；在40 nm CMOS（ss-corner）工艺节点进行综合实现，与现有的设计相比，本文的硬件设计TPG（Throughput Per Gate）提升5倍以上.

Abstract

Fully homomorphic encryption and post-quantum cryptography rely heavily on NTT (Number Theory Transformation) to accelerate polynomial multiplication. As the dimension of NTT polynomials increases

the storage and transmission of rotation factors have an increasingly serious impact on the system. To solve this problem

this paper designs a twiddle factor generator with low area cost for fully homomorphic encryption. This paper first analyzes the calling rule of the twiddle factor of the NTT algorithm and proposes a dynamic twiddle factor generation scheme. Through data generation and overwriting

the twiddle factor is compressed to 0.12% of the original storage space. When performing the NTT operation with a dimension of 65 536

only 78 units of storage cost are required. Secondly

based on the RNS-CKKS scheme in fully homomorphic encryption

this paper evaluates 120 prime number modules with low Hamming weights and 60 bits wide

proposes a lightweight Barrett modular multiplication algorithm

and designs a modular multiplication unit with low area cost based on this algorithm. Finally

based on the dynamic twiddle factor generation scheme

this paper implements a low-cost dynamic twiddle factor generator for the Radix-16 NTT butterfly unit of fully homomorphic encryption

meeting the actual requirements of NTT operations in fully homomorphic encryption. To further verify the superiority of the hardware design in this paper

experimental verification was conducted on the Zynq UltraScale+ XCZU9EG device. The operating frequency reached 252 MHz

and the Slice resource consumption was reduced by 15%. The comprehensive implementation was carried out at the 40 nm CMOS (ss-corner) process node. Compared with the existing designs

the hardware design TPG (Throughput Per Gate) in this paper has increased by more than five times.

关键词

Keywords

references

GENTRY C . Fully homomorphic encryption using ideal lattices [C ] // Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing . New York : ACM , 2009 : 169 - 178 .

FAN J F , VERCAUTEREN F . Somewhat practical fully homomorphic encryption [J ] . IACR Cryptol. EPrint Arch. , 2012 , 2012 : 144 .

BRAKERSKI Z , GENTRY C , VAIKUNTANATHAN V . (Leveled) fully homomorphic encryption without bootstrapping [C ] // Proceedings of the 3rd Innovations in Theoretical Computer Science Conference . New York : ACM , 2012 : 309 - 325 .

CHEON J H , KIM A , KIM M , et al . Homomorphic encryption for arithmetic of approximate numbers [C ] // Advances in Cryptology-ASIACRYPT 2017 . Cham : Springer , 2017 : 409 - 437 .

GENTRY C , SAHAI A , WATERS B . Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based [C ] // Advances in Cryptology-CRYPTO 2013 . Berlin : Springer , 2013 : 75 - 92 .

DUCAS L , MICCIANCIO D . FHEW: Bootstrapping homomorphic eencryption in less than a second [M ] // Advances in Cryptology—EUROCRYPT 2015 . Berlin, Heidelberg : Springer , 2015 : 617 - 640 .

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 .

KIM S , KIM J , KIM M J , et al . BTS: An accelerator for bootstrappable fully homomorphic encryption [C ] // Proceedings of the 49th Annual International Symposium on Computer Architecture . New York : ACM , 2022 : 711 - 725 .

AGRAWAL R , DE CASTRO L , YANG G W , et al . FAB: An FPGA-based accelerator for bootstrappable fully homomorphic encryption [C ] // 2023 IEEE International Symposium on High-Performance Computer Architecture . Piscataway : IEEE , 2023 : 882 - 895 .

ZHANG N , YANG B H , CHEN C , et al . Highly efficient architecture of NewHope-NIST on FPGA using low-complexity NTT/INTT [J ] . IACR Transactions on Cryptographic Hardware and Embedded Systems , 2020 : 49 - 72 .

CHEON J H , HAN K , KIM A , et al . A full RNS variant of approximate homomorphic encryption [C ] // Selected Areas in Cryptography-SAC 2018 . Cham : Springer , 2019 : 347 - 368 .

KILTZ E , LYUBASHEVSKY V , SCHAFFNER C . A concrete treatment of fiat-Shamir signatures in the quantum random-oracle model [C ] // Advances in Cryptology- EUROCRYPT 2018 . Cham : Springer , 2018 : 552 - 586 .

MARETA R , SATRIAWAN A , DUONG P N , et al . A bootstrapping-capable configurable NTT architecture for fully homomorphic encryption [J ] . IEEE Access , 2024 , 12 : 52911 - 52921 .

IM N , YANG H , EOM Y , et al . Efficient twiddle factor generators for NTT [J ] . Electronics , 2024 , 13 ( 16 ): 3128 .

LEE C , LEE H , DUONG-NGOC P , et al . Twiddle factor generator architecture for number theoretic transform [C ] // 2023 20th International SoC Design Conference . Piscataway : IEEE , 2024 : 209 - 210 .

DUONG-NGOC P , KWON S , YOO D , et al . Area-efficient number theoretic transform architecture for homomorphic encryption [J ] . IEEE Transactions on Circuits and Systems I: Regular Papers , 2023 , 70 ( 3 ): 1270 - 1283 .

PATYK T , QURESHI F , TAKALA J . Hardware-efficient twiddle factor generator for mixed radix-2/3/4/5 FFTs [C ] // 2016 IEEE International Workshop on Signal Processing Systems . Piscataway : IEEE , 2016 : 201 - 206 .

LIU W Q , FAN S L , KHALID A , et al . Optimized schoolbook polynomial multiplication for compact lattice-based cryptography on FPGA [J ] . IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 2019 , 27 ( 10 ): 2459 - 2463 .

FENG X , LI S G . Accelerating an FHE integer multiplier using negative wrapped convolution and Ping-pong FFT [J ] . IEEE Transactions on Circuits and Systems II: Express Briefs , 2019 , 66 ( 1 ): 121 - 125 .

GEELEN R , VAN BEIRENDONCK M , PEREIRA H V L , et al . BASALISC: Programmable hardware accelerator for BGV fully homomorphic encryption [J ] . IACR Transactions on Cryptographic Hardware and Embedded Systems , 2023 : 32 - 57 .

JHENG C S , WU Y T , SHIEH M D . On-the-fly twiddle factor generator design for efficient memory management of negative wrapped convolution [C ] // 2024 International VLSI Symposium on Technology, Systems and Applications . Piscataway : IEEE , 2024 : 1 - 4 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

An Identity-Based Fully Homomorphic Encryption Over NTRU Lattice

Identity-Based Fully Homomorphic Encryption from Ring Learning with Errors Problem

A Fully Homomorphic Encryption Scheme Based on NTRU

Rational Delegation Computation Protocol Based on Fully Homomorphic Encryption

Related Author

DUAN Ran

GU Chun-xiang

ZHU Yue-fei

ZHENG Yong-hui

CHEN Li

XIN Dan

GU Chun-xiang

ZHENG Yong-hui

Related Institution

Institute of Network Information Security Henan University of Economics and Law Zhengzhou Henan China

State Key Laboratory of Mathematical Engineering and Advanced Computing Wuxi Jiangsu China

Fourth Department, PLA Information Engineering University

State Key Laboratory of Mathematical Engineering and Advanced Computing

Institute of Network Information Security, Henan University of Economics and Law

⁰