LatticeNotes3

huangx607087学习格密码的笔记3

0. About

一个密码学fw的学习笔记，别看，很菜的。

这个笔记接着之前发布的笔记2，继续往后面扩展新的内容。

6.Babai算法和寻找好的基底解决apprCVP问题

如果 一个格的基底中的向量两两正交，也就是对于任意的$i \not = j$，均有$ \vec v_i·\vec v_j =0 $。那么在这个格里面解决SVP和CVP问题就会是很简单的。可以证明，这个格中的最段向量就是$\vec v_1$到$\vec v_n$中的最短向量。因为向量的长度的平方为$(\sum_{i=1}^n a_i\vec v_i)^2=\sum _{i=1}^n a_i^2\vec v_i^2$。又因为$a$是不全为$0$的整数，因此给基底中最短的那个向量前的系数赋值为$±1$，其他向量前的系数赋值为$0$即为我们所求的解。

而在正交基底的格中解决CVP问题，根据线性代数原理，对任意向量$\vec w$正交分解，可以分解成以下的式子：
$$
\vec w=\sum_{i=1}^n b_i\vec v_i,b_i \in R
$$
所以我们只需要找到一组$a$，使得$a_i$是$b_i$最近的那个整数就可以求出与$ \vec w $最接近的格中的向量。

然而，如果一个格中的基底向量是高度非正交的，也就是我们在笔记2中的52o01节提到的Hadamard比率$H(B)$接近于$0$时，CVP问题就没有那么好解决了。

一个可能的方法就是，假如给定了一个向量$\vec w=\sum_{i=1}^n b_i\vec v_i$。求与它最接近的格向量就是把所有的$b_i$通过四舍五入的方式转化成与其最接近的整数。不过这种方法在比较正交的基底的格中还是比较好用的，但对于由“不好的”基底组成的格来说，由于每个平行四边形（$2D$平面）会被拉的很长，那么里目标点最近的顶点的距离也会增加。因此除非基底相当正交，在维数低于$5$的格中apprCVP的这个问题还是不太好解决的。

因此，Babai算法就是在格中基底充分正交的情况下，对任意向量$\vec w$进行分解，然后取$\vec v_i$向量中的每个向量的系数$b_i$取其最接近的整数作为我们所求向量的分量。

例如，在一个三维的格中，假设$\vec v_1,\vec v_2,\vec v_3$充分正交（$H(v_1,v_2,v_3)>0.7$），某个向量$\vec w$的分解表达式为$\vec w=3.23\vec v_1+4.83\vec v_2-4.07\vec v_3$，那么与它最接近的一个格中的向量就是$3\vec v_1+5\vec v_2-4 \vec v_3$。如果$H(B)$值过于接近于$0$，那么就会导致最接近的向量值出现的偏差也会比较大，甚至很有可能就不是最近的格点了。

7.基于困难格问题的密码

[Translated by baidu translation]

在20世纪90年代中期，引入了几个密码系统，其潜在的硬问题是大维N的格L中的SVP和/或CVP。其中最重要的，按字母顺序排列Dwork密码系统、Goldreich、Goldwasser和Halevi的GGH密码系统，以及Hoffstein、Pipher和Silverman提出的NTRU密码系统。

引入这些密码系统的动机是双重的。 首先，拥有基于各种硬数学问题的密码系统当然是令人感兴趣的，因为从那时起，解决一个数学问题的突破并不会损害所有系统的安全性。 其次，基于格的密码体制往往比分解或离散对数系统(如ElGamal、RSA和ECC)快得多。 粗略地说，为了实现$k$位的安全，ElGamal、RSA和ECC需要$O(K^3)$操作，而基于格的系统的加密和解密只需要$O(K^2)$操作。 此外，基于格的系统使用的简单线性代数操作在硬件和软件上非常容易实现。 然而，必须指出的是，基于格的密码体制的安全分析并不像基于因式分解和离散对数的系统那样容易理解。 因此，虽然基于点阵的系统是目前许多研究的主题，但与旧系统相比，它们的实际实现是很少的。

Ajtai-Dwork系统特别有趣，因为Ajtai和Dwork表明，除非在多项式时间内解决最坏情况下的晶格问题，否则它们的系统是可证明的安全的。 抵消这一重要的理论结果是密钥大小被证明是$O(N^4)$的实际限制，这导致了巨大的密钥。 阮和斯特恩随后表明，Ajtai-Dwork系统的任何实际和有效的实现都是不安全的。

然后我们会在下面继续讲解几个典型的格密码

8.GGH公钥密码系统

8x01 加密过程

Alice首先选取一组线性无关的向量组$\vec v_1,\vec v_2,…,\vec v_n$，它们之间是相当正交的。这样做的一个方法是确定一个参数$d>0$，然后在$-d$与$d$之间随机选择基底向量$\vec v$的坐标。也可以计算它的Hadamard比率 来看看它们是否相当正交。确定好向量之后，就构建一个以$\vec v_1$到$\vec v_n$为基底的格$L$和由这些（行）向量构建的一个矩阵$V$。这些向量也将成为Alice的私钥。

Alice然后选择一个$n×n$的矩阵$U$，满足$U$中所有元素均为整数且$\det ^2 U=1$。然后计算$W=UV$，并将$W$中所有的行向量作为公钥。

当Bob想要传递信息给Alice时，他会选择一个小向量（比如二进制向量）作为他的明文$\vec m$。然后再选择一个小的随机扰动向量$\vec r$。然后他计算$\vec c=\vec mW+\vec r$。$\vec c$并不是格上的点，但由于$\vec m$是一个小向量，因此$\vec r$是一个小向量。

Alice解密时也很直接，她可以使用Babai算法计算与$\vec c$最接近的格向量$\vec d $，然后计算$\vec dW^{-1}$就可以恢复明文$\vec m$

下面我们来尝试一下：

首先，Alice选择向量$\vec v_1=(-97,19,19),\vec v_2=(-36,30,86),\vec v_3=(-184,-64,78)$作为基底$B$。经计算，$H(B)=0.7462$，符合条件。

Alice构建如下矩阵$U$（其行列式为$-1$）,然后计算$W=UV$如下图

然后，Bob设定明文为$\vec m=(86,-35,-32)$，扰动向量为$\vec r=(-4,-3,2)$

随后计算$\vec c=\vec mW+\vec r=(-79081427,-35617462,11035473)$，并将结果发送给Alice

收到消息后，Alice通过线性代数计算，分解$\vec c$得$\vec c = 81878.97\vec v_1 − 292300.00 \vec v_2 + 443815.04 \vec v_3$.

然后她选取向量$\vec d=81879\vec v_1 − 292300 \vec v_2 + 443815 \vec v_3= (−79081423, −35617459, 11035471)$。容易看出$\vec d$与$\vec e$近似。然后Alice就可以计算出明文$\vec m=\vec d W^{-1}=(86,-35,-32)$

然而，当攻击者想要通过公钥计算密文得话，计算$\vec c=75.76\vec w_1-34.52\vec w_2-24.18 \vec w_3$。因此得到了错误的明文$(75,-35,-24)$。原因也很简单。因为$H(V)=0.7462$，比较大，而$H(W)=0.00002$很小。因此导致了误差的出现。

当然，在$3$维的格中进行加解密是不安全的。后面的笔记中，我们会讲到LLL算法。

8x02 附注

1.我们观察到GGH是概率密码系统的一个例子，因为由于随机扰动r的选择，单个明文导致许多不同的密文。如果Bob使用不同的随机扰动两次发送相同的消息，或者使用相同的随机扰动发送不同的消息，这将导致潜在的危险。 因此，在实践中，随机扰动r是通过将哈希函数应用于明文$m$来确定的。

2.另一个版本的GGH逆转了$m$和$r$的角色，因此密文具有形式$c=\vec rW+\vec m$。Alice通过计算最接近$c$的格向量找到$\vec rW$，然后她将明文恢复为$\vec m=\vec c−\vec rW$。

9.卷积多项式环

9x01 简介

在本节中，我们描述了NTRU公钥密码系统使用的特殊多项式商环，这也是在后面的笔记中我们会用到的。

固定一个整数$N$，使得卷积多项式的环是商环$R=\dfrac{Z[x]}{x^N-1}$。同理，卷积多项式环模$q$后，剩下的环也是商环$R_q=\dfrac{\frac{Z}{qZ}[x]}{x^N-1}$。

当然，$R$和$R_q$中的每个元素都有一个形式为$\sum _{i=0}^{n-1}a_ix^i$。所有的$a$作为系数，取值范围为$Z$或者$Z_q$。而我们对$x^N-1$取模的原因也非常的简单，因为一旦出现了$x^N$，我们就可以将其替换成$1$，同理，出现$x^{N+1}$我们可以将其替换成$x$，

9x02 无模数情况下的计算法则

两个多项式的加法，直接就是将$x$相同次数相加。设$f(x)=\sum_{i=0}^{n-1}a_ix^i,g(x)=\sum_{i=0}^{n-1}b_ix^i$。则
$$
f(x)+g(x)=\sum_{i=0}^{n-1}(a_i+b_i)x^i
$$
而对于$2$个多项式相乘$f(x)g(x)$，我们有这样的计算方法：
$$
f(x)g(x)=\sum_{i=0}^{n-1} \sum_{j+k\equiv i \pmod n} a_jb_k
$$
例如，假如$f(x)=x^4+3x^3+x^2-2x+1,g(x)=4x^4+x^3-2x^2+3x+3$。那么$f(x)+g(x)$中，$x^3$前面的系数就是$3+1=4$。而$f(x)g(x)$中，$x^3$前面的系数则为$a_0b_3+a_1b_2+a_2b_1+a_3b_0+a_4b_4=1×1+(-2)×(-2)+1×3+3×3+1×4=21$。注意到这里的$n=5$,除了$0+3,1+2,2+1,3+0 \equiv 3 \pmod 5$之外，$4+4\equiv 3 \pmod 5$也是成立的，因此不能把$a_4b_4$这一项漏掉。

9x03 有模数情况下的计算法则

假如$n=5$时两个多项式$f(x),g(x)$经过计算，得到了结果为$h(x)=4x^4+23x^3-7x^2+9x-10$，如果我们想要对它模$15$的操作，我们又该怎么办呢？

很容易想到的就是把$23$换成$8$，化$h(x)$表达式为，$h(x)=4x^4+8x^3-7x^2+9x-10$

不过在多数情况下，由于数字越小越容易计算，因此我们一般选择将所有的系数压缩在区间$(\dfrac {-q} 2,\dfrac q 2]$这个区间里，因此我们最好把$8$化成$-7$，$9$化成$-6$，$-10$化成$5$，因此最后我们化简后的表达式就是
$$
h(x)=4x^4-7x^3-7x^2-6x+5
$$
特殊地，如果$q=2$，那么我们所得到的一个多项式就是一个二进制多项式。并且平时为了简化计算，最好提前将$f(x)$与$g(x)$中的所有系数进行化简，然后再进行乘积。

9x04 素数域中的乘法运算

刚才我们讲到的那个例子中，模数$15$不是素数，而如果当模数是素数时，那么对于这个多项式环中的任意一个多项式$f(x)$，总存在唯一的一个$g(x)$，使得$f(x)g(x)\equiv 1 \pmod q$ 。此时我们称$g(x)$是$f(x)$的逆元。而这种情况下，我们可以使用扩展欧几里得计算两个多项式的最大公约式$=1$和它们的模逆。这一步很容易在Sagemath中实现。

下面这张图具体地实现了$f(x)g(x)$结果和求$h(x),p(x)$的最大公因数，定义域为$GF(13)$，多项式最高次为$x^7$，取模$x^8-1$

注意到我们如果用欧几里得辗转相除法，计算出来的$\gcd (h(x),p(x))=9x+4$。不过最后正确的答案却是$x+12$。因为最高次项系数为$1$的多项式计算总是非常方便的，多项式两边除以$9$（也就是乘上$9$模$13$的逆元$3$，就可以得到$x+12$的结果了）

模数不是素数的时候，有些步骤也是可以计算的，把$13$换成$15$，很多也是可行的。不过这里要用Zmod，因为$GF(15)$无意义。

回顾一下：只有某个数式素数或者素数幂的时候，$GF$域才有意义，例如$GF(2),GF(3),GF(7),GF(11)$或$GF(9),GF(256),GF(343),GF(14641)$

但环跟$GF$域不一样，无论环长度或者模数是不是素数， 环都是有意义的，并且在某些情况下，使用合数$q$产生的效果反而比使用素数来的更好（比如$q=2^k$）

一般来说，如果$q$是素数$p$的幂，那么为了计算$R_q$中$ f(x)$的逆，首先计算$R_p$中的逆，然后“提升”这个值到$R_{p^2}$中的逆，然后在$R_{p^4}$中提升到逆，以此类推。 同样，如果$q$是多个素数（幂）$q_i$的乘积，则首先计算$R_{q_i}$中的逆，然后使用中国余数定理组合逆。

Update 7.29 增加了具体实现方法：

下面我们来讨论一下具体在$R_q$中求出某个多项式$f(x)$的逆，其中$q=p^{e}$:

假设我们已知:
$$
f(x)F(x)\equiv 1 \pmod {x^n}
$$
那么我们有
$$
G(x)=(2-f(x)F(x))F(x)
$$
使得$f(x)G(x)\equiv 1 \pmod {x^{2n}}$

以上所有的多项式计算都在 $R_q$ 中实现

Update 2023.12.11 这就是多项式求逆的公式！