Lattice 学习记录

卷积多项式环

在介绍NTRU公钥密码体系之前，我们需要一些数学知识的铺垫。

• 定义：给定一个正整数N，卷积多项式的环（秩为N）是商环

同样的，卷积多项式的环（模q）是商环

我们知道，对于$R$或$R_q$都有可以写成$\sum _{i=0}^{n-1}a_ix^i$​的形式，而其中的系数分别在$Z$或$Z/qZ$​​中。而我们对$x^N-1$取模，是为了更简单的运算，把高次项（指数大于N）化为低次项。

在没有模数情况下的多项式加法和乘法没什么好说的。有模数的加法，只需要对系数求模即可。有模数的乘法需要注意一下，计算公式如下

而有模数的除法（即求逆元），需要使用扩展欧几里得算法求解。一般来说，如果$q$是素数$p$的幂，那么为了计算$R_q$中$f(x)$的逆，首先计算$R_P$中的逆，然后“提升”这个值到$R_{p^2}$中的逆，然后在$R_{p^4}$中提升逆，以此类推。 同样，如果$q$是多个素数（幂）$q_i$​的乘积，则首先计算$R_{q^i}$​​​中的逆，然后使用中国剩余定理组合逆。

这里我们提一下“提升”的方法，在书中方法被放在exercise部分了。

下面我们证明一下这个结论。

NTRU公钥密码体系

在介绍NTRU中，我们再补充一个定义hhh。

• 定义：$T(d_1,d_2)=\{a(x)\in R\}$​​，其中$a(x)$​有$d_1$​个系数为1，$d_2$​个系数为-1，其余系数为0。

然后我们开始介绍这个密码体系。

Alice选择四个参数$(N,p,q,d)$​，其中$N,p$是素数，$gcd(p,q)=gcd(N,q)=1,q>(6d+1)p$​​。Alice再选择两个多项式$f\in T(d+1,d),g\in T(d,d)$​，并计算$f$在$R_p,R_q$中的逆$F_p(x),F_q(x)$​，若逆不存在，就重新选择。

然后Alice再计算$R_q$中的$h=F_q*g$​，把$h,(N,p,q,d)$，作为公钥，$f,g$作为私钥。

Bob有明文$m\in R_p$​​​​​，再选择一个随机多项式$r\in T(d,d)$​​​，计算$e\equiv pr*h+m(mod\ q)$​​​。

Alice收到密文e后，计算$f*e\equiv pg*r+f*m(mod\ q)$​​​，a为前面这个式子算出的多项式移动到$R$后的多项式，再计算$F_p*a(mod\ p)$​​​，得到的就是明文。

NTRU中的数学问题

对于上面随机的$h(x)$，实际上我们有以下关系

而我们知道$f(x),h(x)$的系数都非常小，那么破解NTRU的问题就变成，已知$h(x)$，求解$f(x),g(x)$。然而，事实上这个解并不唯一，因为如果$f(x),g(x)$满足等式，那么$x^kf(x),x^kg(x)$也满足等式，这时候求出的明文就会多$x^m$倍。

为什么人们会认为NTRU密钥恢复问题是一个困难的数学问题？ 一个必要的要求是，这个问题不能通过蛮力或碰撞搜索来解决。更重要的是，求解NTRU密钥恢复问题，被证明（几乎肯定）等价于在某一类格中求解SVP。因此这个密码系统被认为是比较安全的。

作为格密码系统的NTRU

令$h(x)=h_0+h_1x+...+h_N-1x^{N-1}$是NTRU的一个公钥，那么NTRU的格可以写成如下形式

可以知道，这个矩阵是2n维的，其中左上角是单位矩阵$E$，左下角是0矩阵，右下角是矩阵$qE$，右上角是由$h(x)$​各个系数循环得到的。

我们可以把它写的简单一些

• 我们知道$f(x)h(x)\equiv g(x)\pmod{x^N-1} \text{ in } R_q$，那么

  其中$u(x)$​也是一个多项式。我们把$qu(x)$移到左边，然后再写一个恒等式

  我们就可以对这个方程组改写，写成矩阵相乘的形式

  因此$(\vec f,\vec g)$​在格$M_h^{NTRU}$中。

  这时只需要向量长度满足一定条件，我们就可以像在引入中的例子一样，找到解。