面向基于格密码学的高速 Karatsuba 多项式乘法器及新颖调度

《IEEE Transactions on Emerging Topics in Computing》：High-Speed Karatsuba-Based Polynomial Multiplier With Novel Scheduling for Lattice-Based Cryptography

　　多项式乘法是基于格的后量子密码（PQC）方案中最耗时的操作之一。朴素多项式乘法（SPMA）和数论变换（NTT）技术已被广泛使用。前者是一种简单的方法，适用于简单的硬件实现，但可能会带来较长的延迟。后者具有较低的运算复杂度。对于硬件实现而言，它会产生预计算、数组重排和后处理等操作的额外开销。卡拉楚巴（Karatsuba）算法在两种方案之间提供了一种折中方案。本文没有采用原始的卡拉楚巴算法，而是提出了一种无重叠的混合层卡拉楚巴框架，并设计了一种新颖的调度方案，在预处理阶段没有空闲周期，以提高整体吞吐量。该设计的主要目标是实现高速多项式乘法，特别是针对非NTT友好多项式环这一类。所提出的架构在Saber和二元环学习带误差（BRLWE）方案中进行了评估。现场可编程门阵列（FPGA）实现结果显示，所提出的Saber架构在硬件资源不变的情况下，吞吐量分别比基于卡拉楚巴和托普利茨矩阵-向量乘积（TMVP）的现有设计高出2.41倍和3.68倍，而硬件成本分别仅增加了2.9倍。因此，面积-时间复杂度降低了58.72%和21.11%。对于BRLWE方案，与现有的卡拉楚巴框架相比，吞吐量提高到4.28倍，硬件资源成本仅增加2.6倍。面积-时间复杂度改善了38.97%。对于NIST标准化的Kyber方案，所提出的架构在403MHz下仅需52个周期即可完成一次多项式乘法，与最近的基于NTT的Kyber设计相比，延迟减少了11倍以上。