因为之前用了大量的coppersmith和要自造格子的题，觉得继续摸鱼抄脚本已经没有前途了

(`ヮ´ )σ`∀´) ﾟ∀ﾟ)σ “就我还不会格密码┭┮﹏┭┮”

所以决定开始系统学习一下

Lattice的历史

Lattice（格）在很早以前就被各大数学家研究了一遍。代表人物有Lagrange，Gauss和Minkowski等等。最近的几十年内，Lattice在密码学、通讯、密码分析上有了很大的应用价值，是非常火的一个领域。

近代Lattice时间线：

  • 1982：LLL basis reduction theorem
    • 使用Lattice来做Cryptanalysis
  • 1996：Ajtai-Dwork
    • 第一次把Lattice中Average-case与Worst-case的复杂度问题关联起来
      提出了使用Lattice构造的One-way Function与CRHF（Collision Resistant Hash Function）
  • 2002：找到了Average-case/worst-case复杂度之间的关系，基于Lattice的协议变得更加高效
  • 2005：Regev提出了LWE，并且发现其量子抵抗性
    • 提出PKE，IBE，ABE，FHE等等的可能性

Lattice是什么

个人理解，Lattice（格）就是一个n维空间$\mathbb{R}^n$，而这个空间是由规律分布的、离散的点构成的。

最简单的Lattice就是Integer Lattice（整数格）。整数格中最简单的就是基于笛卡尔坐标系的基底$\vec{e_1}$,$\vec{e_2}$······组成的格。

接下来就是完全类比于线性代数中的n维空间，（线代没学好的哭哭咧😣

而这个“n维空间”的一组基向量就可以称为这个格的基。

如果系统性的定义一下Lattice的话，那么我们可以说Lattice是$\mathbb{R}^n$这个空间中的一个离散的、具有加法运算的子群（A discrete additive subgroup）。

同时，格和基完全满足线性代数中的线性变换。

Lattice的一些基本性质

我们知道，在一个线性空间里面，一个空间$V$的Determinant（行列式）$det(V)$代表了这个空间所有的基向量$b_i$所组成的几何体的体积。在二维空间里，两个基向量$b_1$,$b_2$组成的平行四边形的面积就是这个空间的Determinant。

这个性质完全适用于Lattice，对于n维完全类比。

值得注意的是，无论我们怎么更换基向量，Determinant的大小，即基向量组成的多面体的体积是相同的。给定任意的一组基向量，我们都可以有效的找到这个Lattice空间的Determinant。

Lattice的密度

我们可以用一个Lattice的Determinant来衡量这个格的点阵分布的密度。

首先，我们把上一部分基向量组成的多面体的中心挪到原点上来。这样，空间$P$仍然保持相同的体积。

随后，我们可以把这个多面体复制多份，然后平移到每一个Lattice中的点上。这样我们就会得到很多份$P$，并且这些多面体可以平分整个多维空间$\mathbb{R}^n$。

4.1

此时，我们如果在这个空间中任意的画一个球体（多维空间即超球体），然后可以数数看这个球体中覆盖了多少Lattice里的点。点的数量平均于球体的体积，就是这个格的密度了。

最短距离

我们一般用$λ_1$来定义整个格中点与点之间最短的距离。一般为了方便理解，我们就把其中的一个点设置成坐标轴0点，然后$λ_1$就变成了距离$O$点距离最近的格点。

而这些$λ$需要遵守一个非常简单的规则：
$$
λ_1\leλ_2\leλ_3\le\cdots\cdots\leλ_n
$$
一个特殊的例子就是笛卡尔坐标系下的整数格$\mathbb{Z}^n$，因为所有的基向量全部都长度相等，并且相互垂直，所以$λ_1=λ_2=⋯=λ_n=1$。

距离函数和覆盖半径

给定任意的点$t$（可以不在格点上），定义距离函数$μ(t,L)$为这个点到最近格点的距离。

我们可以左右移动这个点$t$，就可以得到这个格中最大的$μ$，称之为覆盖半径。

据二维笛卡尔坐标系为例，则为向量$i$,$j$,$i-j$所围成的三角形的外接圆半径。

6.1

从另一方面理解覆盖半径，即为在每一格点作圆（三维及以上类比），不断增大圆的半径，圆与圆之间的空隙也就不断缩小，直到半径等于覆盖半径时，整个空间完全被覆盖。

6.2
6.3

Lattice的光滑化

在上一个概念中，将作圆改为叠加一个圆形的随机噪声，在圆的半径达到覆盖半径之前，空间上都会有空白区域，但在达到覆盖半径之后，因为圆和圆之间会有重叠部分，所以噪声分布很不均匀，这时就需要对其进行光滑化。值得注意的是，要获得最光滑的空间，我们的半径要无限大，即一个圆能覆盖整个空间，这样的构造是无意义的。

所以我们规定一定要有一个巫妖王光滑化半径的上限
$$
||r||\le log(n)·\sqrt{n}λ_n
$$

Minkowski凸集定理（Convex body theorem）

二维即为高中数竞所学的闵可夫斯基定理，主要理解其高维意义：

在多维空间内有一个凸集$C$，令其包含原点。若$vol(C)>2^n$，则这个凸集必含有异于原点的一个格点。

在整数格$\mathbb{Z}^n$中非常好理解，因为以原点出发到所有下一个点这段距离构成的空间，恰好就是$2^n$，所以说任何凸集（集合的表面不能有凹陷）只要体积大于$2^n$，那就一定会溢出这段空间，进而覆盖某个非0的格点。通过Pigeonhole Principle（鸽子洞原理）就是抽屉原理哒就可以很生动的理解了。

然后通过线性变换将整数格变为新格，该定理仍然成立。

Minkowski定理最重要的用处就是给出一个Lattice中最短向量的一个上限值。
$$
λ_1(L)≤\sqrt{n}r=\sqrt{n}det(L)^{1/n}
$$
理解：如果把这个Lattice的Determinant对应的空间压缩成一个立方体，那么这个立方体的对角线长度就是$\sqrt{n}r$。因为对角线的另一头就是下一个格点了（但不一定是最近的格点），所以$λ_1$肯定要小于等于这个对角线的长度。

Minkowski第二定理

Minkowski第二定理给出了对于其他短向量$λ_i$的一个取值上限。
$$
λ_1(L)\le\left(\prod_iλ_i(L)\right)^{1/n}\le\sqrt{n}·det(L)^{1/n}
$$
第二定理指出，全部$n$个最短向量的几何平均数，一定会小于等于我们之前给出的$\sqrt{n}r$这个对角线的长度。这个其实就是对于上面我们说的把一个任意的Determinant对应的空间压缩成一个等边长的立方体的话，对角线就是$\sqrt{n}r$这么长。然而现实中一个任意Lattice的Determinant空间是一个不规则的Parallelepiped，所以边长肯定各不相同。但是因为体积是一样的，所以我们用几何平均数的方法就可以很好的约束这个Parallelpiped每个边的长度。