Abstract: Polynomial multiplication accounts for more than 80% of the computational time in lattice-based cryptographic operations. Polynomial multiplication based on the Number Theoretic Transform (NTT) can reduce the computational complexity of polynomial multiplication from to . However, compared with other implementation methods, polynomial multiplication based on the NTT algorithm is more complex in data scheduling and more difficult in memory mapping. At present, memory mapping schemes tailored for specific algorithms are limited by algorithm parameters and hardware characteristics, resulting in poor scalability. Memory mapping schemes for reconfigurable polynomial multiplication incur significant overhead in control and storage units, leading to low area efficiency of polynomial multiplication architectures. To address the above issues, this paper proposes a conflict-free memory mapping scheme based on partial constant geometry transformation, which can support lattice-based cryptographic polynomial multiplication operations that meet the condition . A conflict-free data scheduling scheme is proposed to avoid write-write conflicts during the mode transition of polynomial multiplication and data conflicts in the polynomial point multiplication stage. In addition, to avoid read-write conflicts in memory units during data scheduling, a multi-Bank storage scheme with cyclic shift storage is proposed, which can reduce the control complexity and cut down the storage capacity by 37.5% compared with the classic ping-pong storage method. To further demonstrate the superiority of performance, the polynomial multiplication architecture based on the conflict-free memory mapping scheme was experimentally verified on the FPGA xc7v2000tflg1925. Compared with the relevant literature, the conflict-free memory mapping scheme proposed in this paper exhibits higher area efficiency.

摘要： 多项式乘法在格密码运算中占用80%以上的时间，基于快速数论变换(NTT)的多项式乘法能够将多项式乘法的计算复杂度从 降低至 。然而，基于NTT算法的多项式乘法在数据调度方面相比于其他实现方式更为复杂，内存映射更为困难。当前，适用于特定算法的内存映射方案受算法参数和硬件特征限制，扩展性有限；适用于可重构多项式乘法运算的内存映射方案在控制单元和存储单元的开销较大，导致多项式乘法架构面积效率较低。基于上述问题，该文提出一种基于部分常数几何变换的无冲突内存映射方案，能够支持满足 条件的格密码多项式乘法运算。其中，提出一种基于部分CG算法的无冲突数据调度方案，避免多项式乘法在模式转换过程中的写写冲突以及多项式点乘阶段的数据冲突。此外，为避免存储单元在数据调度过程中的读写冲突，提出一种循环移位存储的多Bank存储方案，能够降低控制复杂度的同时，相较于经典乒乓存储方式减少37.5%的存储容量。为进一步证明性能的优越性，基于无冲突内存映射方案的多项式乘法架构在FPGA xc7v2000tflg1925上进行实验验证，和相关文献相比，本文提出的无冲突内存映射方案具有更高的面积效率。