Lattice learning-3

发布于 2021-07-28  84 次阅读






Lattice learning-3

Lattice 学习记录

卷积多项式环

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

  • 定义:给定一个正整数N,卷积多项式的环(秩为N)是商环

同样的,卷积多项式的环(模q)是商环

我们知道,对于都有可以写成​的形式,而其中的系数分别在​​中。而我们对取模,是为了更简单的运算,把高次项(指数大于N)化为低次项。

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

而有模数的除法(即求逆元),需要使用扩展欧几里得算法求解。一般来说,如果是素数的幂,那么为了计算的逆,首先计算中的逆,然后“提升”这个值到中的逆,然后在中提升逆,以此类推。 同样,如果是多个素数(幂)​的乘积,则首先计算​​​中的逆,然后使用中国剩余定理组合逆。

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

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

NTRU公钥密码体系

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

  • 定义:​​,其中​有​个系数为1,​个系数为-1,其余系数为0。

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

Alice选择四个参数​,其中是素数,​​。Alice再选择两个多项式​,并计算中的逆​,若逆不存在,就重新选择。

然后Alice再计算中的​,把,作为公钥,作为私钥。

Bob有明文​​​​​,再选择一个随机多项式​​​,计算​​​。

Alice收到密文e后,计算​​​,a为前面这个式子算出的多项式移动到后的多项式,再计算​​​,得到的就是明文。

NTRU中的数学问题

对于上面随机的,实际上我们有以下关系

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

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

作为格密码系统的NTRU

是NTRU的一个公钥,那么NTRU的格可以写成如下形式

可以知道,这个矩阵是2n维的,其中左上角是单位矩阵,左下角是0矩阵,右下角是矩阵,右上角是由​各个系数循环得到的。

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

  • 我们知道,那么

    其中​也是一个多项式。我们把移到左边,然后再写一个恒等式

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

    因此​在格中。

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