格密码学基础（一）

格（Lattice）

格（lattice）的定义

不是那么标准的定义
有一组线性无关的空间向量$(b_1,b_2,\dots ,b_n)\in {\mathbb{R}}^n$作为基，该组的每个向量若乘以某个整数系数（也就是通过线性变换）所产生的离散基向量生成空间向量集合就称为格。
L ( b 1 , b 2 , … , b n ) = { Σ x i b i ∣ x i ∈ Z } \mathcal{L}\left(b_{1}, b_{2}, \ldots, b_{n}\right)=\left\{\Sigma x_{i} b_{i} \mid x_{i} \in \mathbb{Z}\right\} L(b1​,b2​,…,bn​)={Σxi​bi​∣xi​∈Z}
如果把基向量组合用合成矩阵$B$来表示
L ( B ) = L ( b 1 , b 2 , … , b n ) = ∑ i = 1 n b i ⋅ Z = { B x ∣ x ∈ Z n } \mathcal{L}(B)=\mathcal{L}\left(b_{1}, b_{2}, \ldots, b_{n}\right)=\sum_{i=1}^{n} \mathbf{b}_{i} \cdot \mathbb{Z}=\left\{B x \mid x \in \mathbb{Z}^{n}\right\} L(B)=L(b1​,b2​,…,bn​)=i=1∑n​bi​⋅Z={Bx∣x∈Zn}
帮助理解： 假如把空间里的向量的末端视为一个点，则格就是某空间里面的具有一些规律的离散的点集合，也可以说格是某空间中的一个离散的、具有加法运算的子群。类似这样

值得注意的是：

1. 系数是整数，向量坐标是实数，如果向量坐标也是整数，那么生成的格就称为整数格，有点类似笛卡尔坐标系。
2. 我们可以用线代中学到的基向量变更给这个格找到一组新的基$C$，那么可得$C=AB$，这里$det(A)=\pm 1$。即格的任意两个基可以通过左乘一个特定的矩阵来相互转化，这矩阵是由整数构成的，且它的行列式为$\pm 1$
   证明过程如下，
   
   同时，这种矩阵也称为幺模矩阵
   (unimodular matrix)
   定义: $U\in {\mathbb{Z}}^{n\times n}$，$|U|=\pm 1$，$U$称为幺模矩阵同时它的逆也是幺模矩阵。

如何判定两个格基是否能生成同一个格呢？
当一个格基能通过幺模矩阵进行变换到另一个格基的时候，这两个格基就可以生成相同的格。

基础区域（Fundamental Parallelepiped）

由格基$B$线性组合，系数在$[0,1)$之间组成的一块区域。

P ( B ) = { B x ∣ x ∈ R n , ∀ i : 0 ⩽ x i < 1 } \mathcal{P}(B)=\left\{B x \mid x \in \mathbb{R}^{n}, \forall i: 0 \leqslant x_{i}<1\right\} P(B)={Bx∣x∈Rn,∀i:0⩽xi​<1}
大概像这样，

如何判定给定的向量集是否构成格的“basis”？
由向量生成的"basic parallelepiped"不应该包含除原点外的任何格点，即基础区域与格的交集为0。
如下图

图2(c)中所示的"basic parallelepiped"包含格点 (1，0)，而图2(a)和图2(b)中的基本平行不包含任何非零格点。
一个格的任意基础区域都拥有相同的体积（体积不是狭义的三维体积，可以扩展到n维，如二维是面积，三维是体积）。

行列式（Determinant）

类似于线性空间里，一个格的行列式代表了对应基向量所组成的几何体体积
定义格的行列式作为基础区域的n维体积
$$det(\mathcal{L})=\sum _i{\mathbf{b}}_i\cdot [0,1)=vol(\mathcal{P}(\mathbf{B}))$$
注意
给定任意一组基向量，这个Determinant大小是不变的，也就是无论怎么变换，都能找到这个值，即一个格的任意基础区域体积都相同。它不依赖于计算它的某个具体基础区域，是格的不变量。证明过程如下

格密度

格的密度可以理解为，在空间里任意取一个超球体，然后看这个球体里面覆盖了多少格点，点的数量平均于球体体积，这个就是密度
格的行列式与其密度成反比
$$\begin{gathered} ForallsufficientlylargeS\subseteq {\mathbb{R}}^n: \\ |S\cap \mathcal{L}|\approx \mathrm{vol}(S)/\det (\mathcal{L}) \end{gathered}$$

最短距离与连续最小值

格的一个基本参数是格中最短非零向量的长度，也就是点与点之间的最短距离，为了方便可以把其中一个点设置为坐标轴的原点。
λ 1 = min ⁡ x , y ∈ L , x ≠ y ∥ x − y ∥ = min ⁡ x ∈ L , x ≠ 0 ∥ x ∥

λ1​​=x,y∈L,x=ymin​∥x−y∥=x∈L,x=0min​∥x∥​
记为${\lambda }_1(\mathcal{L})，$同理可定义第二近到第$n$近的${\lambda }_2(\mathcal{L}),{\lambda }_3(\mathcal{L}),\dots ,{\lambda }_n(\mathcal{L})$。

距离函数（Distance Function）与覆盖半径（Covering Radius）

给定一个任意点$\mathbf{t}$（可以不在格上），定义距离函数$\mu (\mathbf{t},\mathcal{L})$为这个点到附近的格点的最短距离。
$$\mu (\mathbf{t},\mathcal{L})=\underset{\mathbf{x}\in \mathcal{L}}{\min }\Vert \mathbf{t}-\mathbf{x}\Vert$$
可以通过移动$\mathbf{t}$位置得到这个格中最大的$\mu$，这个就称为覆盖半径（Covering Radius）
$$\mu (\mathcal{L})=\underset{\mathbf{t}\in span(\mathcal{L})}{\max }\mu (\mathbf{t},\mathcal{L})$$
注意$\mu$是点到格点的最短距离，如果把点换为格点，以每个格点为圆心画圆并逐步扩大，直到这些圆正好完美的覆盖所有空间的时候，这个半径就是最大的$\mu$，即覆盖半径了。

格的Smoothing

假如将上述的圆，改变为叠加圆形范围内取值的随机噪音，而当达到覆盖半径的时候将会出现取值分布很不平均的问题，那么为了解决此问题就需要smooth一下格。
理论上当半径到无限大的时候，得到的分布是很完美的，但是这种构造就没了意义，所以就出现了一个Smoothing的半径最大上限，该上限由格中距离最大的最短向量${\lambda }_n$来决定的，大于这个距离之后，必然会覆盖其他的格点。

Minkowski定理

凸集定理（Convex body theorem）
用于寻找一个格点周围最近的其他格点的。
给出一个Lattice中最短向量的一个上限值。
$${\lambda }_1(\mathcal{L})\le \sqrt{n}r=\sqrt{n}\cdot \det (\mathcal{L}{)}^{1/n}$$
假如把格的Determinant对应空间压缩为一个立方体，那么该立方体的对角线长度就是$\sqrt{n}r$，对角线的另一头必然是下一个格点（但不一定是最近的格点），所以肯定要小于等于这个对角线的长度
第二定理
给出一个对于其他最短向量${\lambda }_i$的一个取值上限
$${\lambda }_1(\mathcal{L})\le {\left(\prod _i{\lambda }_i(\mathcal{L})\right)}^{1/n}\le \sqrt{n}\cdot \det (\mathcal{L}{)}^{1/n}$$
第二定理指出全部$n$个最短向量的几何平均数，小于之前的对角线长度，由于任意一个格的Determinant对应空间的Parallelepiped是不规则的，所以用几何平均数能很好约束Parallelepiped边的长度

格中难题

最短向量问题（SVP）

定义
在格中需找一个最短的非零格点

可以理解为：寻找一组整数与基向量线性组合使得组合后的向量的长度最短。或者，理解为给定一个基的格，找到一个这个基构成的格点，使得这个点距离坐标原点距离最近。
宽松版（$SV{P}_{\gamma }$）：找到$\gamma$倍距离就行
判定版（GapSVP）

最短独立向量问题（SIVP）

定义
给定一个格，找到n个线性无关的向量，并且这些向量的长度都要小于定于最长的最短向量。
宽松版（$SIV{P}_{\gamma }$）：找到$\gamma$倍距离就行
判定版（GapSIVP）

最近向量问题（CVP）

定义
在离散线性集合中逼近目标向量的问题
给定一个不在格中的目标向量，在各种寻找一个向量使得该向量与目标向量距离最近。

可以理解为：给定一组格基向量，和一个目标向量，很难找到一组整数与基向量线性组合使得组合后的向量距离目标向量最近。或者，理解为给定连续空间中任意一个点，找到距离这个点最近的格点。这个距离一定是小于等于覆盖半径的。

还有一种定义是给定一个格，一个随机点和搜索距离，并且假设覆盖半径小于等于搜索距离，CVP问题就是找到一个合理的格点并且这个点到随机点的距离小于等于搜索距离。
宽松版（$CV{P}_{\gamma }$）：找到$\gamma$倍距离就行
判定版（GapCVP）

格基约减算法（Lattice Basis Reduction）

在上述问题中，都需要输入格的基，来形成一个格，从而找到相应的值。同一个格有很多基，有些基是短的，尽可能垂直的，称为“好”的基。而有些基又是长的，且方向接近于同一方向或相反方向的，称为“坏”的基。比如整数格${\mathbb{Z}}^n$就是一个“好”的基，在它上面解决CVP问题，只需要通过上下取整即可。

所以，需要将“坏”基转变为“好”基，目标是找到一组非常接近垂直基，这个过程称之为 格基约减，就是为了发现一组又短又垂直的基。

比较常见的算法就是施密特正交化，即输入一组基，通过反复迭代最后输出一组垂直的基，这组基能够张成与输入基相同的空间。由于格的系数都是整数，所以应用于格的时候需要把系数进行四舍五入的取整到最近整数。

施密特方法高度依赖向量的顺序问题，不同的基向量顺序将导致不同的结果，为解决这个问题，诞生了LLL算法，但LLL算法只是一次考虑两个向量，由此又诞生了BKZ算法。

参考

• 格密码理论与应用实践
• 【格理论与密码学】周福才，徐剑编著
• yue佬专栏里的格文章