面向基于格的密码的有效多项式乘法

带有错误的环学习（Ring-LWE）是各种基于格的密码系统的基础。 基于Ring-LWE的密码系统最关键且计算量大的操作是环上的多项式乘法。 在本文中，我们介绍了几种优化技术，以利用数论变换（NTT）构建有效的多项式乘法器。 我们提出了一种优化NTT和反向NTT的位反向操作的技术。 通过其他优化，我们的多项式乘法器将所需的时钟周期从（8n + 1.5n lg n）减少到（2n + 1.5n lg n）。 通过利用常数因子之间的关系，我们的多项式乘法器能够将常数因子的数量从4n减少到2.5n，从而节省了大约37.5％的ROM存储。 此外，我们提出了一种新颖的内存访问方案，以实现蝶形运算符的最大利用。 借助这些技术，我们的多项式乘法器能够在Spartan-6 FPGA上针对维度256/512每秒执行57304/26913多项式乘法。