基于MLWE的格密码高效硬件实现

后量子密码的发展已经引起各界的广泛关注,硬件实现效率是后量子密码最终标准的重要衡量指标之一。其中基于模误差学习问题(Module Learning With Errors,MLWE)的CRYSTALS-Kyber格密码是NIST第三轮后量子密码标准中最有希望的一种加密方案,可变的公钥矩阵维度参数k将基于MLWE的公钥加密方案的安全性扩展到不同级别,相较于其他格密码方案更具灵活性和安全性。本文首先分析了基于NIST第三轮最新参数q=3329的MLWE的格密码公钥加密方案的算法理论,并针对其中的核心模块—多项式乘法模块提出了两种不同的硬件实现方式。两种多项式乘法硬件实现方式都是采用基于频率抽取的数论变换(Number Theoretic Transform,NTT)算法,使用NTT算法实现多项式乘法降低了传统算法实现的线性复杂度,在硬件结构上能够面对不同应用场景进行优化,因此本文针对NTT算法中循环计算的核心模块提出了两种不同的优化硬件结构。一是面积和执行时间折中的迭代型NTT硬件结构,二是高性能低时延的多路延时转接(Multi-path Delay Commutator)的流水型NTT硬件结构;并且针对于面积时间均衡的迭代型NTT模块设计了一种整体MLWE硬件实现结构。与已有的先进设计相比,本文的流水型NTT结构具备更好的速度性能,在速度上相较于之前的设计分别提升11.64%和59.43%。而对于使用迭代型NTT的MLWE整体实现方案,本文的设计使用了最少的周期和最小的面积时间乘积(Area-Time-Product,ATP),其效率比最新发表的工作的硬件效率实现高2倍左右。