基于NTT的高效多项式乘法器设计及其FPGA实现

Design and FPGA implementation of efficient polynomial multiplier based on NTT

基于快速数论变换(number theoretic transform,NTT)的多项式乘法运算是后量子密码(post-quantum cryptography,PQC)的重要组件,提高多项式乘法器的运算速度至关重要。文章基于现场可编程门阵列(field programmable gate array,FPGA)提出一种输入位宽为14位、长度为1024的高效多项式乘法器硬件加速方案,设计一种无冗余可重用的蝶形运算单元电路。通过提高部分运算的并行度,实现模乘器接近100%的利用率,降低整个多项式乘法运算的迭代周期,提高整体运算速度。该乘法器最终被部署在Xilinx Artix-7 FPGA开发板上,实验结果表明,电路的最高工作频率为238 MHz,多项式乘法运算的总体用时为35.59μs,对比现有的硬件设计,该文提出的电路运算效率提高36.9%。

Polynomial multiplication based on number theoretic transform(NTT)is an important component of post-quantum cryptography(PQC)and it is very important to improve the operation speed of polynomial multipliers.Based on field programmable gate array(FPGA),this paper proposed an efficient hardware acceleration scheme for polynomial multiplier with input bit width of 14 bits and length of 1024,and designed a non-redundant and reusable butterfly unit circuit.By improving the parallelism of some operations,the utilization rate of modulo multiplier is close to 100%,and the iteration cycle of the whole polynomial multiplication is reduced and the overall operation speed is improved.The multiplier was finally deployed on Xilinx Artix-7 FPGA development board.The experimental results show that the maximum operating frequency of the circuit is 238 MHz,and the overall time of polynomial multiplication is 35.59μs.Compared with the existing hardware design,the algorithm efficiency of the proposed circuit is improved by 36.9%.