基于格密码芯片的多项式乘法模块设计研究.pdf

基于格密码芯片的多项式乘法模块设计研究

摘要

从上世纪九十年代起，量子计算领域的蓬勃发展对传统公钥密码算法的安全性造成

了巨大冲击。因此，密码学界开展了大量抵御量子计算机攻击的后量子密码算法研究，

其中，最具有代表性且研究最为火热的为格密码算法。为了提高算法的执行效率，将格

密码算法实现在硬件芯片中成为了重要趋势。多项式乘法作为格密码算法之中的核心运

算，其在硬件实现上的高效性对于整个格密码芯片的性能至关重要。本文针对格密码算

法中的多项式乘法模块开展了高性能快速数论变换算法设计和轻量化硬件架构研究。

基于数论变换（NumberTheoreticTransform，NTT）的多项式乘法相比于其他多项

式乘法算法，其有着计算复杂度低、资源利用率高、稳定性好等优点，因此被广泛应用

在格密码算法的多项式乘法中。多项式乘法无论是运行时间还是资源占用，在整体格密

码流程中都占比最高，而现有的多项式乘法模块无法兼具这两方面需求，亟需进一步优

化NTT算法，设计硬件加速方案，提升多项式乘法模块计算效率。本文首先针对现有

的基4-NTT算法无法应用在Kyber算法中，而基2-NTT算法计算复杂度较高的问题，

提出了一种基2基4-NTT混合算法，通过更改循环顺序消除NTT中的预处理、后处理

操作，并实现NTT、INTT中旋转因子的复用，使Kyber公钥加密算法及其他格密码算

法可以使用基4-NTT算法，实现计算降维。然后，设计了轻量化的多项式硬件加速架

构，可以支持多项式乘法中不同基数下的NTT、INTT、点乘等运算，核心单元为由4组

小型蝶形结构构成的轻量化蝶形单元，并针对多项式乘法中的各种运算，设计了不同模

式下的调度方式。最后，根据本文设计的多项式乘法模块，提出了一种对应的无冲突内

存映射方案和数据存储方案，该方案简化了存储数据的读写控制，解决了多项式运算过

程中大量数据交互造成的地址转换过于复杂及数据互相冲突问题。

最后，本文实现了基于基2基4-NTT混合算法的多项式乘法模块硬件，并对其进

行了高级语言验证和功能仿真，且在FPGA上进行了性能评估。从仿真结果中可以看出

本设计可以正确完成基2基4-NTT混合算法的NTT、INTT、点乘运算。经过在Vivado

中布局布线后，本设计最高工作频率为200MHz。资源报告表明，本设计共消耗1818个

LUT、1308个FF、12个DSP及5个BRAM。与相关文献对比，本文提出的硬件设计在

性能与资源占用方面都具有一定的优势，有着高效的ATP表现。

关键词：格密码；多项式乘法；数论变换；硬件架构

基于格密码芯片的多项式乘法模块设计研究

Abstract

Sincethe1990s,theboomingdevelopmentofquantumcomputinghasposedsignificant

challengestothesecurityoftraditionalpublickeycryptographicalgorithms.Consequently,the

cryptographycommunityhasembarkedonextensiveresearchintopost-quantumcryptographic

algorithmstodefendagainstquantumcomputerattacks.Amongthese,lattice-based

cryptographicalgorithms,representedbythelattice-basedcryptosystems,havegarnered

considerableattentionandaresubjecttointenseresearch.Toenhancetheefficiencyofthese

algorithms,implementinglattice-basedcryptographicalgorithmsonhardwarech