Lattice学习记录

Intro

开始学习格密码（寒假学过，但是忘了，而且不会用，坏起来了）。这次学习主要参考${《An\ Introduction\ to\ Mathematical\ Cryptography》}$，也会参考一些师傅的博客。

我们先来了解一个真实公钥密码系统中的一个简单模型。它的维度很低，不过说明了密码分析中如何出现格。此外，它还提供了对NTRU公钥密码系统的最低维的介绍。

$Alice$选择了整数$q$作为mod，选择$f,\ g$ 作为密钥，其中$f<\sqrt{q/2}$， $\sqrt{q/4}<g<\sqrt{q/2}$，并且$gcd(f,\ q)$=1，然后计算$h\equiv f^{-1}g\ (mod\ q)$，$h,\ q$是公钥。$Bob$选择明文m和一个随机正整数r，满足$m<\sqrt{q/4}$，$r<\sqrt{q/2}$，然后计算密文$e\equiv rh+m\ (mod\ q)$。

$Alice$收到密文后，先计算$a\equiv fe\ (mod\ q)$，这时$a\equiv rg+fm\ (mod\ q)$，再计算$af^{-1}\equiv m\ (mod\ g)$。由于上面的限制条件，这里进行mod运算的数都比发送的信息大。

$Eva$想要从 h 和 q 中获得 f 和 g，也就是获得一组$F,G$，使得$Fh\equiv G(mod\ q)$，把这个式子改写为，$Fh-kq=G$， 补一个恒等式$F+0*q=F$，我们就可以把它改写成向量的形式：

因此，$Eva$知道两个向量$\vec{v_1}=(1,h)\quad\vec{v_2}=(0,q)\quad length=O(q)$，她想找到一个线性组合: $\vec w=a_1\vec v_1+a_2\vec v_2$，$length(\vec w)=O(\sqrt q)$，因此，她需要在向量集合$L=\{a_1\vec v_1+a_2\vec v_2:a_1,a_2\in Z\}$中找到一个短的非零向量。而寻找方法，已经由高斯提出，我们会在后面说到。

子集和问题与背包密码系统

• 子集合问题：

  给定一个正整数集合$M=\{M_1,M_2,...,M_n\}$并选定一个整数$S$，找到$M$的一个子集，使得其中的元素和为$S$。我们可以把这个问题划归成：需要找到一个二进制向量$\vec x=(x_1,x_2,...,x_n)$，使得$S=\sum_{i=1}^n x_iM_i$。

• 超级递增序列$(superincreasing\ sequence)$：

  令$\vec r=(r_1,\ r_2,...,\ r_n)$，其中$r_k>r_1+r_2+...+r_{k-1} \quad(k>1)$

有了上面的知识，我们来介绍Merkle -Hellman subset-sum cryptosystem。

• Merkle -Hellman subset-sum cryptosystem

  $Alice$ 选定一个超级递增序列$\vec R=(r_1,r_2,…,r_n)$和两个大整数$A,B$，其中$B>2r_n,\gcd(A,B)=1$。然后$Alice$ 计算$M_i=Ar_i\ (mod\ B)$，并把$\vec M=(m_1,m_2,…,m_n)$，作为公钥。

  $Bob$ 收到密钥后，令密文为$\vec x$，计算$S=\vec x\vec M$，并给 $Alice$ 发送S。

  $Alice$ 收到密文后，只需要计算$D=A^{-1}S \pmod B$，然后求$D$在集合$\vec R$中的一个表示方法，就可以得到密文$\vec x$。

以上的密码系统，又被称作子集和密码体制或背包密码体制。由于$M$是一个$n$个整数的列表，每个整数有$2n$比特长。明文的长度是$n$，密文的长度是$2n$。那么它的信息扩展比是2:1。和RSA以及D-H密码体系相比，它的公钥占用存储空间大，不过它的加密速度很快，历史上，这使得背包密码系统非常有吸引力。但是当LLL格基规约算法被提出后，基于背包问题的加密系统被发现有根本上的漏洞。

下面我们简单介绍一下子集和问题构造的格，也就是它的攻击方法（又要说邪恶的$Eva$的故事了hhh）。$Eva$想把$S$写成$M$的子集和，她先构造了下面这个矩阵：

取出其中每个行向量，记作$v_1,v_2,v_3,...,v_n,v_{n+1}$，就像之前二维的例子中一样，把这些向量写成线性组合的形式，

既然我们要求的明文$\vec x$​是子集和问题的一个解，而上面的格通过和$(x_1,x_2,x_3,...,x_n,-1)$​​进行点乘运算，可以得到下面这个向量（也就是说$L$中有下面这个向量）

由于$x_i$是0或1，所以这个向量$||\vec t||=O(\sqrt n)$，而我们知道$m_i=O(2^{2n}),S=O(2^{2n})$，于是$L$中的基底长度$||\vec v_n||=O(2^{2n})$，这样，我们就可以认为我们找到的这个向量是L里的一个短向量。所以，$Eva$只需要在$L$中找到一个非零的最短向量，那么就可以认为，找到了我们构造的$\vec t$​，继而恢复明文。

这种在格中找到短向量的算法叫做格基约减算法，其中最著名的就是LLL算法。

向量空间综述

在我们开始之前，我们需要学习 （复习 ) 一些有关向量空间的知识。

• 向量空间：向量空间是一组向量的集合，这个集合对加法和乘法封闭。
• 线性组合：令向量集合$\vec v_1,\vec v_2,...,\vec v_n\in V$​​，那么线性组合就是$\vec w=a_1\vec v_1+a_2\vec v_2+...+a_k\vec a_k$。
• 线性相关与线性无关：有$n$个向量，$a_1\vec v_1+a_2 \vec v_2+…+ a_n \vec v_n= \vec 0$，若可以找到一组不全为$0$​​的实数使这个等式成立，那我我们就说这组向量线性相关，否则线性无关。
• 向量夹角
• 欧几里德范数：也称做向量的长度$||\vec v||=\sqrt {x_1^2+x_2^2+...+x_m^2}$​
• 施密特正交化方法

格的定义和性质

• 定义1：令$\vec v_1,\vec v_2,...,\vec v_n$​是一组线性无关的向量，那么格(lattice)就是​这n个向量的线性组合集，即

  这n个向量是L的基底，基底所有的向量数是L的维度。

对于一个格L，可以有很多组不同的基底，而这些基底可以相互转化。这时就需要转化矩阵$T$，使得$W=TV$，由于$W，T$中的每个元素都是整数，那么我们就要保证$T$中的所有元素都是整数，而其必须满足$detT=±1$。

• 定义2：如果$R^m$​​的一个子集$L$​​对加减法封闭，那么我们就说它是一个加法子群。对$L$​​，如果存在一个正常数$r$​,使得对$L$​中任意一个向量$\vec v$​和$R^m$​中任意一个向量$\vec w$​，都有$|\vec v - \vec w|<r$，那么$L$是离散加法子群。​​​​

换句话说，就是在$L$中任意取一个向量$\vec v$​，​然后在空间中画一个以$r$​为半径的球，如果在这个球里没有$L$里的其他点，那么$L$就是离散加法子群。

• 定理：$R^m$的一个子集$L$是格，当且仅当$L$​是离散加法子群。

• 定义：基本域：令$L$是一个n维的格，向量$\vec v_1,\vec v_2,…,\vec v_n$是它的一组基，与这组基对应的$L$​​的基本域就是：

  而对于在$R^n$中的一个向量$\vec w$，我们就可以把它写成$\vec w=\vec t + \vec v$，其中$\vec t \in F,\quad \vec v$是格$L$的一组基底。我们可以发现格$L$​的所有基本域都有相同的体积，而基本域体积不变是格中一个非常重要的性质。并且基本域的体积又被称作$L$的行列式，即$det L$。