密码学基础之格理论基础

这篇文章中的大部分基础知识都是摘自 《An  Introduction to  Mathematical  Cryptography》中的第七章：Lattices and Cryptography。对其中的内容进行了一些删减和整合，旨在向初学者介绍一些基础的格理论知识，不过仍需要读者掌握一定的线性代数基础知识。

首先是格 （Lattice）的定义：我们设有 个 维的相互线性独立的向量 ，那么由 生成的格 就是这些向量的所有系数为整数的线性组合。

对应的，这样一组向量则称为格 的基 (basis)。

所以格和向量空间是很像的，不过由于“系数为整数”的要求，使得相对于连续的向量空间，格是由一系列离散的格点组成的。形如下图，格中的格点应该是无限多的，并且任一维度中，相邻格点之间的距离是固定不变的。（下面我们会再具体做说明）i

我们再用一个”生动形象“的🌰来说明：

首先我们定义一个坐标系的原点作为参照。

于是我们就可以定义一个一维向量（如果将点与点之间加上箭头的话大家可能会熟悉些）

然后这个一维向量通过一系列”系数为整数“的线性组合（），那么它就可以生成一个一维的格

如果此时我们引入一个在这个维度之外的向量

那么同样的，取原来维度中的任一向量和这个向量作为基进行各种线性组合（），于是就可以生成一个二维的格

同理，我们还可以生成三维的格，

四维的、五维的等等也都可以（不过显然这不再是我们能够用图像表示出来的了）

相信到这里大家对格应该有一个大致的认识了（很简单的嘛），那么我们继续后面的话题。对于一个格 来说，他的基并不是唯一的，任何能够生成格 的向量集合 都可以称为 的格基。显然 的任意格基中所包含的向量数量是相等的，而格 的维度也正是由格基中向量的数量所决定。那么格基之间是否可以相互转换呢？

我们设 的两组格基 。那么由于它们都是 的格基，因此其中的每一个向量也都在格上， 即 ，那么显然对于任意的 ，其都可以由格基 表示，于是有

并且由于格的性质，所有的系数 都是整数。我们将这些系数提取出来，就可以得到一个系数矩阵

那么式子就可以记为 ，如果我们想用 表示 ，那么就是 。

注意到由于 ，而 中所有元素均为整数，因此有 。根据线性代数中的知识我们有 ，而伴随矩阵 的计算过程中又不涉及任何的除法，于是 中的元素都是整数，因而 中的元素也均为整数。

因此我们得到一个结论， 的任意两个格基都可以通过一个行列式为 的整数矩阵进行相互转换。

第二颗🌰，我们考虑一个三维的格 ，其一组格基为 ，我们将其写为矩阵的形式

        然后我们构造三个也在 中的向量：，我们将这些系数取出来，构成系数矩阵 :

于是由向量 构成的矩阵 为：

由于矩阵 的行列式为 ，因此向量 也是 的一组格基，而 的逆矩阵为

矩阵 则揭露了如何用 表示 ：

了解了上述内容后，我们可以还从另外一个角度定义格：设 维的实数空间 中的一个子集 ，其在加法运算下满足封闭性，于是我们可以称之为 可加子群，如果对于 中的任意向量 ，存在一个常数 ，满足

则称 为 可加离散子群。更形象点说，（以 3 维为例）对于 中的任一元素 ，在其周围半径为 的空间内都没有其他元素。

定理：当且仅当 下的一个子集 是可加离散子群，我们称 为格。

对于那部分没有格点的空间，我们称之为格 的基本域（fundamental domain），记为

下图展示了一个二维格的基本域

有了基本域的概念，结合 中的格点，我们就可以表示实数空间 中的任意向量 了，记为

另外，根据图片，结合前面我们对线性代数的学习，我们可以很自然的想到，对于 维的格 ，设 为 的基本域。那么 的度量（volume）就是 的行列式 (determinant）记为 。

如果我们把格基的各个向量视为 的各个边，那么在各个向量长度不变的情况下，当且仅当各个向量相互正交时， 取得最大值。于是我们引出 Hadamard’s 不等式：

当各个向量越趋于正交，不等式则越趋于相等。

如果对于 的某一格基 ，我们记其对应的基本域为 ，再设 ，记

于是我们有

而我们在前文提到， 的不同格基可以通过一个行列式为 的整数矩阵进行相互转换，即 。于是我们不难得出， 的任意基本域的度量都相等。形象点来说，就是所有格点周围的空间大小都是相同的。

那么对于格基础理论的介绍就到此为止了，对于感兴趣还想要继续深入了解的读者可以自行查阅相关数学书籍。下一篇文章将介绍一些格中经典的数学问题，以及对应的密码学场景。