高能效混合基多项式乘法算法及可重构硬件结构研究与设计  

Research and Design of High Energy Efficient Hybrid Base Polynomial Multiplication Algorithm and Reconfigurable Hardware Structure

作　　者：别梦妮 李伟[1] 陈韬[1] 李慧琴 杜怡然 南龙梅[1] BIE Meng-ni;LI Wei;CHEN Tao;LI Hui-qin;DU Yi-ran;NAN Long-mei(University of Information Engineering,Zhengzhou,Henan 450001,China)

机构地区：[1]信息工程大学,河南郑州450001

出　　处：《电子学报》2024年第12期3957-3966,共10页Acta Electronica Sinica

基　　金：国防预研项目(No.2019-JCJQ-JJ-123)。

摘　　要：本文针对快速多项式乘法算法与可重构单元的高能效设计问题展开研究,首先对现有的格基后量子密码算法展开研究,提出了一种基于数论变换(Number Theoretic Transform,NTT)的快速多项式乘法算法,并针对其中的核心运算过程,提出了高能效混合基的NTT和INTT(Inverse Number Theoretic Transform)算法,该算法可以利用NTT变换高效实现所有基于有限域的格基后量子密码算法中的多项式乘法.在此基础上,对快速多项式乘法算法运算结构进行研究,在不增加额外运算部件的前提下,通过优化网络连接关系,提出了一种高能效可重构的混合基多项式乘法加速网络,在可灵活实现基2、基3、基4的NTT/INTT算法的同时,将基3与基4的NTT运算效率提升了一倍.本文针对混合基NTT运算过程中的访存冲突问题展开研究,从理论上分析了冲突产生的原因,在此基础上分析提出了一种高能效混合基的内存管理方案,设计了相应的地址生成逻辑.本文提出的内存访问方案是原地内存访问的一种,硬件固化后仍可实现不同的多项式乘法算法的内存管理.实验结果表明,在55 nm CMOS工艺下,完成维度为256,模数小于2^(16)的多项式乘法运算仅需0.785μs,最高工作频率可达到476 MHz,功耗为83.6 mW,面积时间积(Area Time Product,ATP)为152.604 kGE·μs.与当前现有研究相比,本文提出的结构的ATP值降低了40%以上.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 2^(16) 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%.

关 键 词：后量子密码算法 格 多项式乘法 数论变换 

分 类 号：TN402[电子电信—微电子学与固体电子学] TP309[自动化与计算机技术—计算机系统结构]