1．目的及意义
非对称密码（即公钥密码）自1976年提出开始，经过了四十多年的发展，在各行各业都取得了广泛的运用，最著名的有RSA、ECC、ElGamal、MG背包公钥加密算法等。RSA密码方案是基于整数因子分解的困难性，而ECC方案是依赖于椭圆曲线上的离散对数问题。1994年，Shor证明RSA加密方案理论上是可以被量子计算攻破。 2003年，Shor又证明了椭圆曲线离散对数密码（ECC）理论上也是可以通过量子计算破解的。如今量子计算机的问世，使得理论上的破解方法得到了实现。因此现有广泛使用的公钥加密方案的安全性已经不能符合当今社会发展的需求，国际上对信息安全的发展有了更高的要求，需要一种普通计算机能够应用的后量子公钥算法，来抵抗量子计算机的暴力攻击破解。

目前后量子公钥密码可分为基于编码的公钥密码体制、基于多变量的密码体制、基于Hash算法构造的密码体制和基于格的密码体制四个类型。其中基于格的密码体制因其良好的安全特性和简单的代数结构成为当今构建后量子密码系统研究的热点之一。1996年，Ajtai首先证明了格问题在平均情况和最坏情况下的复杂性之间存在着等价关系。1997年,Ajtai和Dwork提出的AD97密码方案是第一个基于格的密码方案。随之而来的是GGH密码方案，但其安全性与运算效率难以兼顾，不具备很高的实用价值。之后也出现了许多基于格的公钥算法，但是大部分实用价值不高，且没有严格的理论安全性证明。2005年，Regev提出的LWE（Learning With Error）公钥密码方案是第一个支持严格理论安全性证明的格密码方案。

虽然基于LWE问题所构造的公钥密码方案有着支持严格理论安全性证明等许多的优点，但却有一个明显的缺点，即公钥长度过大。LWE密码方案所消耗的时间与空间资源会随着参数进行平方级增长，方案的运算效率会明显降低。所以，以增大安全参数来增强加密方案的安全性的方法是不可取的，不利于实际应用。2012年，Lyubashevsky和Peikert等人提出了Ring-LWE问题，即基于特定环上的LWE问题，该方案比LWE的优势在于更高效且密钥较小，使得在不影响加密方案安全性的情况下提高了方案的效率。但是Ring-LWE方案会使硬件实现时电路结构更加复杂。因为Ring-LWE在运算时主要涉及的是多项式乘法，需要大量的乘法单元。所以如果能解决多项式乘法的运算问题，就能优化电路结构，使得Ring-LWE方案更加高效。

本设计主要意义在于，在Ring-LWE方案中，涉及到许多多项式乘法的实现。将NTT算法应用于多项式乘法的计算，通过将多项式乘法转化为多项式系数的点乘，能够明显减小Ring-LWE加密方案中计算的复杂度，从而减小了电路开销，使得其硬件电路的实现更加高效。

{title}

2. 研究的基本内容与方案

{title} 2.1 基本内容与目标

本课题主要研究的是应用于Ring-LWE加密体制的NTT运算单元的设计与实现方法。在理解NTT算法的基础上，完成NTT算法的C语言或MATLAB建模、仿真，继而对仿真结果进行优化，最终在FPGA上实现满足预期的NTT算法单元，并观察其面积和功耗使用情况，进行最终优化。

2.2基本理论

Number Theoretic Transform（NTT）即快速数论变换是在快速傅里叶变换（FFT）基础上实现的，因此也称为FNTT。快速傅里叶变换是在复数域上的变换，大部分系数都是浮点数，进行复数域的计算时计算量会较大，而且浮点数的计算可能会导致误差增大。而NTT算法能够通过将复数对应到整数，使得多项式乘法的计算较FFT而言更加精简。

2.3拟采用的技术方案与措施

1) 先用软件实现NTT算法（C或matlab)；

2) 对算法进行建模与仿真，验证算法结果是否正确；

3) 规划NTT算法单元的系统结构；

4) 使用verilog HDL逐步实现该单元中的各个模块，对各模块进行综 合与仿真；