格密码学习笔记(一)

前情提要

作为一个又菜又喜欢密码学的渣渣，之前一直想仔细看看有关格密码的知识，但是一直也没完整的去看，只是零碎的看了一点点，然后呢，本系列文章其实是我学习过程当中的一个笔记，因此本系列文章可能会比较枯燥，我尽量补充我在学习过程当中遇到的一些问题的资料和理解，当然因为我个人的水平非常有限，有些概念可能理解的不到位，如果哪里理解的不对，欢迎研究这方面的读者指正。

预备知识

对于格密码，其中前置的数学知识内容还是蛮多的，因此如果要理解本系列文章的内容，可能需要一点点的数学基础，包括不限于高等代数(线性代数)、抽象代数的部分内容，其中可能也要用到一点点分析的内容(预估不会太多，因为我这分析相当于没学)，当然，如果涉及到理论，我可能也会给出一些前期的解释，但是如果这个解释实在要补的东西太多的话，那么就不会去解释了，因为解释起来可能会偏离文章的内容。

格的定义

通常来说，格有两种定义形式，第一种可以采用抽象代数的内容来定义，也就是通过群来去定义一个格。

• 「定义1」: 格是上的一个离散子群

我们来仔细看下这个定义，可以分为两部分，第一个是离散，那么先来看下什么是离散。

顾名思义，我们可以将其理解为不连续，这种不连续如何用数学方式来表示一下呢，我们需要借助分析里面的一点点概念。

❝

对于，对 使得.

❞

上面这个定义没有那么好理解，我们来通过一个具体的例子来看一下，找一个大家大概率见过的一个格，也就是，这里我们画一下这个格的一个图。

注意这里的坐标做了一定的缩放，因此比例不是正好的，我们可以发现，对于任意的向量，我们可以找到一个满足上面的例子，下面来简单证明一下吧，我们采用欧氏距离来证明，当然采用其他的也可以。

令那么我们可以得到他们的距离

因为两个向量不同，那么我们不妨假设，其他情况同理可得，我们可以得到，从而可以得到，注意到所有的向量坐标都为整数，这样就证明完成了。

我们再来看一个不是格的例子，我们考虑这个空间，也就是所有的有理数构成的空间，这样我们就无法找到这样一个使得上面的式子成立，这里就不证明了，通过有理数的「稠密性」很容易发现这一点。

接下来呢，我们再看看一下有关格的第二个定义。

• 「定义2」: 令是一个n维的欧几里得空间，我们定义在上的格的集合如下:

其中k个向量是线性无关的，并且要求，其中k我们称之为格的秩，然后n称之为格的维度。这个向量序列我们称之为格的一组格基，通过下面的矩阵来表示。

因此呢，我们可以通过格基的形式来表达格的定义，具体如下:

我们再来看一个例子，考虑如下的两个向量。

上面两个点的整系数组合构成了上图当中的所有点，然后对于同一个格来说，基不是唯一的，我们同样的可以找到另一组格基。

虽然两个的网格看起来有些差异，但是最终所有的交点是完全一样的，因此我们可以说这两个格是一样的，也就是。

其中，当k = n的时候，我们称之为格是满秩的，在接下来相关文章的讨论中呢，如果不做特殊说明，我们只考虑「满秩的格」，然后对于格基向量的范围，我们也限定在「整数」当中，当一个格满秩当且仅当

等于整个欧几里得空间。通过可以看出，张成的空间并不依赖于格基，也就是说如果两组格基对应的格相同也就是.

但是，是不是所有的格基的组合都是同一个呢，显然不是的，我们还是用上面的一个例子，考虑下面的一组向量。

我们可以发现，上面那一组基是不能够表示出来的，不信的读者可以自行尝试一下。那么问题来了，如何判断是不是格的一组格基呢，首先来看一个新的定义。

❝

「定义3」: 「Fundamental Parallelepiped」(目前这个词我没有找到比较好的翻译，因此这个词用英文表示，不翻译了).令$ mathbf{B}^{prime} = left.[ mathbf{b}{1}^{prime}, ldots mathbf{b}{n}^{prime} right.]   mathbf{b}_{i}^{prime} in mathcal{L}(mathbf{B}) subset mathbb{R}^{n}  mathbf{B}^{prime}$的Fundamental Parallelepiped如下

❞

注意，这里是一块面积，其中，为了更加直观，我们来看一个图来辅助下理解，这块我刚开始看实际上也理解好久，结合了多个资料，最终才搞明白这个说的是什么。

然后，我们可以得到如果也是格的一组格基，当且仅当不包含除原点之外的任意一个格点，通过正经一点的表达方式来表达，那就是:

令为一个秩为n的格，如果是格的一组格基当且仅当.

通过上面的描述呢，我们其实并没有找到比较好的方案来判定两个格基是否是同一个格，那么接下来，我们来看另一个方案。如果两个格基和可以表示成为的形式，其中并且那么我们称这两个格是一样的，有关矩阵其实他有个名字叫做幺模矩阵，有关这个矩阵的知识，咱们下一篇文章再来仔细的聊一下，因为里面涉及到的东西还是挺多的，并且这个也是比较重要的，个人看法。

总结

我这又开了一个新的系列，又给自己挖了一些的坑，说实话，这个系列心里也没底，但是发现这东西还是比较有意思的，因此想通过这种方式来记录下，要是到我看不懂的地方，那可能这个就被我咕咕掉了，希望这次不要是开始就是结束，最后呢，感谢各位读者的支持，如果也对这个感兴趣的话，也欢迎和我交流，最后分享下最近再看的一点东西，最近发现道德经还是挺有意思的，因此呢，这个系列的文章，文末就都搞一段道德经的原文作为结束吧。

❝

道可道，非常道；名可名，非常名。无名天地之始，有名万物之母。故常无欲，以观其妙；常有欲，以观其徼。此两者同出而异名，同谓之玄，玄之又玄，众妙之门。

❞

参考资料

• https://eprint.iacr.org/2023/032.pdf^[1]
• https://eprint.iacr.org/2015/938.pdf^[2]
• https://eprint.iacr.org/2023/032.pdf^[3]
• https://web.eecs.umich.edu/~cpeikert/pubs/slides-qcrypt.pdf^[4]
• https://www.cryptool.org/download/ctb/CTB-Chapter_Lattice-Introduction_en.pdf^[5]
• https://zhuanlan.zhihu.com/p/334421256?utm_medium=social&utm_oi=1185283654737149952^[6]
• https://cims.nyu.edu/~regev/teaching/lattices_fall_2009/^[7]
• https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/index.html^[8]
• https://zhuanlan.zhihu.com/p/161411204^[9]
• https://cseweb.ucsd.edu/~daniele/papers/bookChap1.pdf^[10]
• https://doc.sagemath.org/html/en/reference/modules/sage/modules/free_quadratic_module_integer_symmetric.html^[11]
• 道德经【老子】

Reference