NTRU算法详解

算法背景

    NTRU是Hoffstem、Pipher和silverman在1998年提出的一种新的公钥密码体制。该体制是建立在多项式环的基础之上的，其安全性基于格上最短向量问题，可以有效抵抗Shor算法。由于NTRU运算简洁快速，与目前广泛使用的公钥密码系统RSA及椭圆曲线密码系统相比较，在安全要求相同的情况下，NTRU产生密钥对更快，在加密和解密效率上也具有一定的优势。但NTRU的原始方案的安全性一直没有得到严格的证明。

    2011年，Stehle D，SteinfeldR在理想格上基于R-LWE问题构造了选择明文攻击安全的NTRU加密体制。2012年，Ron Steinfeld等人在理想格上提出了选择密文攻击安全的NTRU加密体制。

算法流程

参数选取

N：次数参数，素数

q：大模数，正整数

p：小模数，奇素数或多项式

d：用来限制非0系数的个数，正整数

f(x)：模多项式，N次整系数多项式，将格$Z^N$构造为环$Z[x]/f(x)$

经典参数值：

$(N，q，p，d，f(x))=(251，256，3，72，x^N-1)$

密钥生成

公钥：$(N, p, q, h(x))
$

私钥：$(f(x), f_{p}^{-1}(x))$

生成$f(x),f_{q}^{-1}(x),f_{p}^{-1}(x)$

（1）在格$Z[x]$上选取多项式$f(x)$，满足$f(x)$的次数不超过N-1，系数为$\{-1, 0, 1\}$中的值，且有d+1个系数为1，d个系数为-1，其他系数为0。

（2）检验$f(x)$在环$Z_q[x]/f(x)$上是否可逆，如果可逆则计算逆元$f_{q}^{-1}(x)$

（3）检验$f(x)$在环$Z_p[x]/f(x)$上是否可逆，如果可逆则计算逆元$f_{p}^{-1}(x)$

重复上述步骤，直至得到$(f_{q}^{-1}(x), f_{p}^{-1}(x))$
生成$g(x)$

在格Z[x]上选取多项式$f(x)$，满足$f(x)$的次数不超过N-1，系数为$\{-1, 0, 1\}$中的值，且有d+1个系数为1，d个系数为-1，其他系数为0
计算$h(x)$

$h(x) \equiv pg(x)f_{q}^{-1}(x) \pmod{q}$

加密阶段

将明文编码为系数属于$\{-1,0,1\}$的多项式$m(x)$，明文空间即为$\mathcal{M}=\{-1,0,1\}^N$；同时，在参数选取为$(p,f(x))=(3,x^N-1)$时，有$\mathcal{M}=Z_p[x]/f(x)$
随机选取多项式$r(x) \in Z_p[x]/f(x)$
计算密文

$e(x) = r(x)h(x) + m(x) \pmod{q}$

解密阶段

首先计算：（此处省略了多项式后的(x)）

$\begin{aligned} a &\equiv f*e \pmod{q} \\ &\equiv f*(r*h+m) \pmod{q} \\ &\equiv f*(r*p*g*f_{q}^{-1}+m) \pmod{q} \\ &\equiv r*p*g + f*m \pmod{q} \end{aligned}$

因为$r(x),g(x),f(x),m(x)$的系数都较小，故上述计算所得到的为恒等式

$a = r*p*g + f*m \quad in \ Z^N$

而非同余式

$a \equiv r*p*g + f*m \pmod{q}$

接下来计算：

$\begin{aligned} b &\equiv a*f_{p}^{-1} \pmod{p} \\ &\equiv (r*g + f*m)*f_{p}^{-1} \pmod{p} \\ &\equiv r*p*g*f_{p}^{-1} + m \pmod{p} \\ &\equiv m \pmod{p} \end{aligned}$

需要注意的是，1中实际上为概率性算法，概率与q的取值有关，细节见下图：

知识补充

这一部分主要为在代码实现时所要用到的算法

中心化处理取模

中心化处理，即模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)$都经过这样的中心化处理。

将明文编码为多项式

还没找到合适的算法……

判断多项式是否可逆

见NTRU - PamShao - 博客园或论文《NTRU中多项式的逆问题》

多项式卷积计算与快速卷积

设$a(x), b(x), c(x) \in Z^N/f(x)$，其中$c(x)$为a(x)与b(x)的卷积计算结果，记作

$c(x) = a(x) \otimes b(x)$

将上述多项式表示为向量形式，如下：

$\begin{aligned} a &= (a_0, a_1, a_2, \cdots, a_{N-1}) \\ b &= (b_0, b_1, b_2, \cdots, b_{N-1}) \\ c &= (c_0, c_1, c_2, \cdots, c_{N-1}) \end{aligned}$

由于$X^N \equiv 1 \pmod{X^N -1}$，故乘积后有$X^{N+i} \equiv X^i \pmod{X^N -1}$，进而可以得到：

$c_k = \sum_{i+j \equiv k \mod{N}} a_i b_j$

快速卷积算法