NTRU算法_karn算法

　　NTRU是Hoffstem、Pipher和silverman在1998年提出的一种新的公钥密码体制。该体制是建立在多项式环的基础之上的，其安全性基于格上最短向量问题。由于NTRU运算简洁快速，与目前广泛使用的公钥密码系统RSA及椭圆曲线密码系统相比较，在安全要求相同的情况下，NTRU产生密钥对更快，在加密和加密效率上也具有一定的优势。但NTRU的原始方案的安全性一直没有得到严格的证明。2011年，Stehle D，SteinfeldR在理想格上基于R-LWE问题构造了选择明文攻击安全的NTRU加密体制。2012年，Ron Steinfeld等人在理想格上提出了选择密文攻击安全的NTRU加密体制。

　　下面分别介绍基于格上最短向量问题的NTRU的原始加密方案的整个过程。以及为了达到CPA安全性，给出的一种新型的基于R-LWE问题的NTRU改进方案。

NTRU原始方案

NTRU原始方案的公开参数如下：

n：次数参数，为正整数。经典取值为素数n=251。

g：大模数，为正整数。经典取值为2的幂q=256。

p：小模数，为小的奇素数或多项式。经典取值为素数p=3。

d：用来限制非0系数的个数，为整数。当n=251时，d=72。

f（x）：模多项式，为n次整系数多项式。模多项式f（x）将格Zⁿ构造成了环z[x]/f（x）。经典取值为f（x）=xⁿ-1。

　　NTRU原始方案的一个说明：中心化处理，即模q运算或模p运算的结果以0为中心。比如模3运算的结果属于{-1，0，1}而不是{0，1，2}，模256运算的结果属于{-127，-126，…，128}而不是{0，1…，255}。这样的中心化处理在代数上没有任何不同，但使得尺寸变小了。环Z_q[x]/f（x）和环z_p[x]/f（x）都经过这样的中心化处理。

下面以经典参数值（n，q，p，d，f（x））=（251，256，3，72，xⁿ-1）来叙述NTRU原始方案，其中（n，g）是方案的安全参数。