电子学报2024，Vol.52Issue(12)：3957-3966,10.DOI:10.12263/DZXB.20230945
高能效混合基多项式乘法算法及可重构硬件结构研究与设计
Research and Design of High Energy Efficient Hybrid Base Polynomial Multiplication Algorithm and Reconfigurable Hardware Structure
摘要
Abstract
In this paper,we present a fast polynomial multiplication algorithm,the hybrid-basis number theoretic transform(NTT)and inverse NTT(INTT)algorithms.These algorithms can efficiently implement polynomial multiplica-tion based on finite domain using NTT conversion.On this basis,the paper explores the computational structure of fast poly-nomial multiplication algorithms.Without adding extra computational components,it optimizes network connectivity and proposes an energy-efficient reconfigurable hybrid-basis polynomial multiplication acceleration network.This network can flexibly implement base-2,base-3,and base-4 NTT/INTT algorithms,while doubling the operational efficiency of base-3 and base-4 NTT.This paper studies the issue of memory access conflicts in the computation process of hybrid-basis NTT.It theoretically analyzes the causes of these conflicts and,based on this analysis,proposes an energy-efficient hybrid-basis memory management scheme,designing the corresponding address generation logic.The proposed memory access scheme is a form of in-place memory access,and once implemented in hardware,it can still manage memory for different polynomi-al multiplication algorithms.Experimental results show that,under the 55 nm CMOS process,completing polynomial multi-plication with a dimension of 256 and modulus less than 216 requires only 0.785 μs.The maximum operating frequency can reach 476 MHz,with a power consumption of 83.6 mW and an area time product(ATP)of 152.604 kGE·μs.Compared to the existing research,the ATP value of the proposed structure in this paper is reduced by more than 40%.关键词
后量子密码算法/格/多项式乘法/数论变换Key words
post-quantum cryptography algorithm/lattice-based/polynomial multiplication/NTT分类
信息技术与安全科学引用本文复制引用
别梦妮,李伟,陈韬,李慧琴,杜怡然,南龙梅..高能效混合基多项式乘法算法及可重构硬件结构研究与设计[J].电子学报,2024,52(12):3957-3966,10.基金项目
国防预研项目(No.2019-JCJQ-JJ-123) National Defense Pre-Research Project(No.2019-JCJQ-JJ-123) （No.2019-JCJQ-JJ-123）
