论文标题
数字理论变换及其在基于晶格的密码系统中的应用：一项调查
Number Theoretic Transform and Its Applications in Lattice-based Cryptosystems: A Survey
论文作者
论文摘要
数字理论变换（NTT）是将两个高度多项式与整数系数相乘，这是由于其在算法和实现方面具有一系列优势，因此在基于lattice基于晶格的密码方案的实际实现中尤其重要，因此尤其是基本的。尤其是，最近的作品表明，NTT可以在没有NTT友好环的情况下使用，并且可以超越其他乘法算法。在本文中，我们首先回顾了多项式乘法，卷积和NTT的基本概念。随后，我们系统地通过中文定理以代数方式系统地引入基本的Radix-2快速NTT算法。然后，我们详细阐述了有关削弱NTT参数条件限制的方法的最新进展。此外，我们系统地介绍了如何为各种给定环选择适当的NTT算法策略。后来，我们介绍了NTT在基于NIST的量子后加密标准化竞争的基于晶格的加密方案中的应用。最后，我们试图提出一些可能的未来研究方向。
Number theoretic transform (NTT) is the most efficient method for multiplying two polynomials of high degree with integer coefficients, due to its series of advantages in terms of algorithm and implementation, and is consequently widely-used and particularly fundamental in the practical implementations of lattice-based cryptographic schemes. Especially, recent works have shown that NTT can be utilized in those schemes without NTT-friendly rings, and can outperform other multiplication algorithms. In this paper, we first review the basic concepts of polynomial multiplication, convolution and NTT. Subsequently, we systematically introduce basic radix-2 fast NTT algorithms in an algebraic way via Chinese Remainder Theorem. And then, we elaborate recent advances about the methods to weaken restrictions on parameter conditions of NTT. Furthermore, we systematically introduce how to choose appropriate strategy of NTT algorithms for the various given rings. Later, we introduce the applications of NTT in the lattice-based cryptographic schemes of NIST post-quantum cryptography standardization competition. Finally, we try to present some possible future research directions.
