一堆定理引理懒得在这里写了，用到的时候再查罢。直接整点密码学。
为什么研究格？
格在密码学中的作用与有限域上的椭圆曲线类似，都是一种代数，而在这种代数上有很多密码学家所期望的数学性质，比如后面将会讲到的格密码作为欧几理德空间(向量空间)的离散子集，主要使用的是有限域上的加模、乘模运算，无需使用经典代数里的指数、对数运算等，运算效率会高很多；一些格上的计算问题存在从最坏情况到平均情况的归约，我们将这些计算问题归约到自己的密码方案后，其安全性基于计算问题的最坏情况复杂度，换言之，基于格问题的密码原语总是存在安全性归约且有充分的安全性证明，这是RSA等基于平均情况复杂度的方案所很难做到的，我们无法将整数分解问题归约至RSA。这一点也是很多学者认为格密码可以抵抗量子计算攻击的一个依据，并且这是在其他代数结构里未被发现的一个性质。格还有很多出色的性质，后面有机会会详细讲到。
关于格在密码学中的应用。人们总是过度关注格在抗量子计算攻击中的应用，但实际上利用格可以实现几乎所有的密码原语，可以在”minicrypt“高度，也可以在”cryptomania“高度(平均复杂度的五个世界)。其在许多领域也有关键应用，比如
- 密码分析：格基归约破解RSA
- 编码理论：无线电传输
- 最优化：固定维度下的整数规划
- 密码学：全同态加密
后面有机会可以讲到这些应用。格密码在公钥密码里面的密钥尺寸问题随着近些年新的代数结构不断提出，现在已经可以跟RSA扳扳手腕了，加上其本身具有的计算效率优势，我相信基于格的公钥密码在量子计算机实用化之前就能成为新的工业标准。
格是什么？
格是 $\mathbb{R}^n$ 上的离散子群。关于 $\mathbb{R}^n$：实数域 $\mathbb{R}$ 上的 $n$ 维欧式空间，或者简单点就线性空间，本身对于加法(一般是加法是一个阿贝尔群，直观的说就满足：
- 首先是个集合
- 定义了一个二元运算：加法，满足一些性质
- 封闭性
- 有个单位元，加法是零元
- 每个元素都有有个逆元
- 结合律
- 满足交换律
实数域上的向量空间还需要满足
- 标量乘的封闭性
- 结合律
- 分配律
离散：
\[\exists \varepsilon >0\colon\forall \mathbf{v}_{1},\mathbf{v}_{2}\in \mathcal{L} , \| \mathbf{v}_{1}-\mathbf{v}_{2}\|>\varepsilon\]$\mathbb{Z}^n$就是一个格，离散的(有最短距离1)，子群(构成群的子集)。$\mathbb{Q}^n$就不是。虽然它是$\mathbb{R}^n$的子群，但它不离散，因为：
\[\forall \varepsilon >0,\exists \mathbf{v}_{1},\mathbf{v}_{2}\in \mathcal{L}\colon\|\mathbf{v}_{1}-\mathbf{v}_{2} \| <\varepsilon\]有一说一，这只是形象的但不是格严格的定义，毕竟并不是所有向量空间的离散子群都叫做格，但所有 $\mathbb{Z}^n$ 的线性变换一定是格，也就是下面的定义。
拿矩阵来定义，也就是最普遍的定义一个格的方式。现在很多论文只会给你一个矩阵，但不会告诉你如何用一个矩阵来定义对应的格。一方面来说，这样的定义隐藏了格的细节，也正是最坏情况复杂度到平均情况复杂度的归约所用到的核心思想：模糊格，方便了参数的选择。另一方面，对于我这种菜鸡初学者，需要去了解格的性质，因此需要知道如何从一个矩阵定义一个格。
格的定义可以参考Mathematics of Public Key Cryptography，Prof. Daniele Micciancio’s lecture note和Prof. Oded Regev’s lecture note。需要注意的是密码学中常用的 $q$ 阶随机格和数学里点格的定义不同，对于随机格，同样一个矩阵可以用不同的方法定义一对有微妙对偶关系的格，后文会讲到。毕竟是向量空间的子群，不管怎样定义，都有跟向量空间一样的性质。
点格定义
数学意义上点格的定义：
作用在整数格 $\mathbb{Z}^n$ 上单射(列满秩)的线性变换 $\mathbf{B}\colon \mathbb{R}^{n} \rightarrow \mathbb{R}^{d}$ 所得到的集合 $\mathcal{L}(\mathbf{B})=\mathbf{B}(\mathbb{Z}^n)$。等价的，也可以描述成矩阵列向量的整系数线性组合 $\sum_{i} \mathbf{b}_{i} x_{i}\colon x_i\in\mathbb{Z},\mathbf{B}=\bqty{b_1,…,b_n}$，即列空间的子集。线性变换对应的矩阵 $\mathbf{B}\in \mathbb{R}^{d\times r}$，以其列向量作为格基，其基向量个数，秩(rank)，小于等于空间的维度(dimansion)。有的地方也会把秩叫做维度反过来叫，遇到的话要分辨一下。秩跟$\Lambda$相同的子格叫满秩子格，$\Lambda^{\prime}=\Lambda \cap \operatorname{span}\left(\Lambda^{\prime}\right)$ 叫满子格，类似$\Lambda$在对应空间上的投影。又是满秩子格又是满子格的只有$\Lambda$本身。
基
很多格困难问题实际上就是找基。基和基之间又差一个可逆整数矩阵。所有可逆整数矩阵在矩阵乘法下组成一个群 $GL(n,\mathbb{Z})$，general linear group。然后这个群里的所有的矩阵行列式都为1，所以我们管这种矩阵叫做幺模矩阵。幺模矩阵经过初等列变换可以变为中性元 $\mathbf{I}$，放到格里面就是所有基都可以经过变换变成标准正交基。其实上面所说的这几条都是等价的，最终得到对任意矩阵 $\mathbf{U} \in \mathbb{Z}^{n \times n}$，下面的几种说法都是等价的：
- $\mathbf{U}=\sigma(\mathbf{I})$ 对于一系列初等列变换 $\sigma$
- $\mathbf{U}$ 可逆, i.e., $\mathbf{U} \in G L(n, \mathbb{Z})$
- $\mathbf{U}$ 是幺模矩阵, i.e., $\operatorname{det}(\mathbf{U})=\pm 1$
合起来说，基和基之间差一系列初等列变换，也就是有相同的HNF(Hermite normal form)。咱就可以根据这个判断两组基是否生成的是同一个格。但HNF给的基通常很烂，这就需要施密特正交化。
施密特正交化
所有基都能用，能把坏基变成好基。也能用在LLL攻击里面。
典中典之基础概念，懂的都懂，不懂的回去看书。
