本技术介绍了一种新型NTT多项式乘法器,具备原位存储、恒定几何结构和无访存冲突的特点。该设计将传统NTT的错位存储方法优化为原位存储,并通过奇数Bank存储技术,提高了存储效率和计算性能。
背景技术
格基密码学(Lattice-based cryptography,LBC)在最近流行的全同态加密(Fully Homomorphic Encryption,FHE)和后量子密码学(Post-Quantum Cryptography,PQC)领域占据着核心地位。目前,大多数FHE和PQC方案都是基于环上容错学习(RingLearning With Errors,RLWE)或模容错学习(Module Learning With Errors,MLWE)构建的,这需要在高次多项式环上进行操作。然而,进行高次多项式乘法会耗费大量时间和内存,因此成为大多数FHE和PQC方案应用的主要瓶颈。
为了加快多项式的乘法运算,基于数论变换(Number Theoretic Transform,NTT)的方法被广泛使用。NTT算法主要有两种类型:原位存储的迭代型NTT;以及错位存储的恒定几何结构型NTT。原位存储的迭代型NTT在不同的NTT计算阶段中,多项式系数的访问顺序会发生变化,因此往往具有复杂的内存访问模式。这使得数据传输和地址逻辑非常复杂,不利于灵活和轻量级的实现。相反,错位存储的恒定几何结构型NTT通常具有简单而统一的内存访问模式,因为在不同的NTT计算阶段中多项式数据的访问顺序保持不变,这使得它越来越多地被用于NTT的高效硬件实现。
但是,现有的恒定几何结构型NTT多项式乘法器依然存在以下问题:
1、尽管原位存储的迭代型NTT的内存访问模式复杂,但它的数据读写可以在同一存储区域内完成。错位存储的恒定几何结构型NTT虽然具有统一的内存访问模式,但通常需要使用乒乓结构存储器来防止读写冲突,这导致其存储器使用量比原位存储的NTT多一倍。
2、现有的针对NTT的无访存冲突读写方案往往与多项式长度N直接相关,因此,当多项式长度N改变时,NTT多项式乘法器需要重新在FPGA上编译,无法实现动态重构。
实现思路