【格密码学习笔记(二十二)】格同构问题(LIP)

因为，看到在NIST发布了3个PQC算法之后，又开始了新的一轮[1]算法的提交，然后翻了一下，他们所基于的困难问题，这次，所采用的困难问题就比较多元化了，翻了一下，其中有一个是采用了格同构的问题，借着这个机会，捎带着学习学习吧，当然，本篇文章呢，先不讲提交的算法，先来看看究竟什么是格同构问题。

在介绍，格同构问题之前呢，我们先来回顾一下，究竟什么是同构。

预备知识

同构

对于同构这个概念呢，我们其实很早就接触过了，想想，最开始我们古人在没有发明文字之前，采用的结绳计数，比如今天，捡到了3个苹果，然后，就在绳子上面打上3个绳结，然后第二天，捡到了5个苹果，之后在绳子上打上5个绳结，我么来看最终两天的苹果总数，实际上就是3+5=8个，然后，对于苹果来说，我们当天就吃完了，因此呢，我们要依靠每次数苹果来记录这个个数呢，是不太现实的，因此，我们可以用数绳结的办法，也就计算3+5=8个绳结，来表示苹果的个数，这里，实际上就采用了同构的思想，将苹果的累加运算，映射到绳结的累加运算，数学当中的同构呢，实际上就是对于上面例子中的一个抽象，可以用稍微严格一点的定义来描述。

假设给定两个集合如果存在一个双射，并且，在这个映射之后，保留运算结构，那么我们就称是同构的。我们来看几个，我们之前学过的同构的例子。

群同构

两个群和是同构的，当且仅当存在一个双射对于所有的有

向量空间的同构

两个向量空间同构，当且仅当，存在一个双射，对于所有的以及标量c，有且

二次型

二次型是一个关于向量的齐次二次多项式。在n维实向量空间中，一个二次型Q可以表示为：

其中，是一个n维的列向量，是一个的对称矩阵。

格相等

对于两个格基如果存在一个幺模矩阵使得

那么，我们称这两个格是相等的。

格同构问题

好了，现在，我们来看一下具体什么是格同构问题，根据前面对于同构的理解，我们是需要找到一个映射，使得两个格基之间存在着一定的关系，具体的定义如下。

给定两个格如果这两个格同构，当且仅当我们可以找到一个正交变换使得

这里，我们呢采用格基来表示，也就是对于两个矩阵可以找到一个正价变换使得

这里，我们可以非常容易的采用代数的知识，得到

但是呢，我们在来根据，刚才提到的格相等的概念，我们可以针对于右乘一个幺模矩阵，那么这两个格是相同的，也就是

到这里，这个问题就变得困难了，我们称这个问题为格同构问题(Lattice Isomorphism Problem, LIP)。

因为，现在，我们所有讨论的正交矩阵，都是在实数上的，因此，我们要想办法，将其映射到整数上面，具体需要怎么做呢，就需要用到我们在开头补充的基础知识，二次型。

二次型

我们，首先将格基转换为对应的格拉姆矩阵(Gram Matrix)，也就是

然后，对应的格同构问题，就变成了，我们只需要找到一个幺模矩阵U使得

这里，主要用了一个等价变换，也就是经过正交变换和幺模矩阵的变换后的等价，也就是如果，对于我们有

因此，我们就找到了一个等价的变换。

那么，这么做，有什么好处呢，我们就不需要处理正交矩阵了，我们只需要处理幺模矩阵U。

这里，我们通过一个例子，来看一下，假设，这里我们有两个格基

然后，我们对应计算它的格拉姆矩阵

以及

然后，我们可以找到一个幺模矩阵

这里，我们可以计算

我们，可以找到一个正交变化

这个，读者，可以自行验证一下，矩阵的正交性，这里我们可以得到

因此，我们找到了对应的正交变换，也就是证明了，这两个格确实是同构的。

密钥封装算法[3]

然后，我们来看一下，这里面的密钥封装机制，这里我们需要三个算法，分别是密钥生成，密钥封装以及密钥解封装算法，接下来，我们分别来看一下。

轴线呢，我们来看用到的一些辅助的函数，令是一个映射，具体如下

这里的是一个类似于kdf的函数，实际上是将两部分值，映射到一个固定长度的伪随机值的函数。

密钥生成算法

首先，生成一个基础的格基S，这里S需要满足一定的条件(解码半径是格最短向量的一半)，然后生成一个随机的幺模矩阵，计算

这里，P是公钥，U是私钥。

封装算法

1. 采集随机误差向量

2. 计算

3. 选择随机数

4. 通过计算得到封装之后的key

最终输出(c, k)，其中

解封装算法

1. 计算

其中满足

如果不满足，则返回失败。

1. Z以及y, 恢复k

好了，到这里，我们就获取出来，最终的key了，到这里，相关算法也就解释的差不多了。

总结

本篇文章，我们学习了一个新的问题，也就是格同构的问题，这也是在NIST提交的新的数字签名算法的基础，我们成功的换到了一个新的问题之上。由于个人的水平有限，这个只是我个人的理解，难免会有理解不到位的地方，也欢迎读者和我交流，快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见。

参考资料

1. https://csrc.nist.gov/projects/post-quantum-cryptography/
2. https://arxiv.org/pdf/1311.0366
3. https://eprint.iacr.org/2021/1332.pdf
4. https://eprint.iacr.org/2023/194.pdf
5. https://epubs.siam.org/doi/pdf/10.1137/1.9781611973402.29
6. https://www.esat.kuleuven.be/cosic/events/math-pqc/wp-content/uploads/sites/10/2024/08/presentatie.pdf
7. https://indico.math.cnrs.fr/event/9364/attachments/4433/6601/02%20Mureau_Guilhem.pdf
8. https://scholarlypublications.universiteitleiden.nl/access/item%3A3564782/view
9. https://hawk-sign.info/hawk-spec.pdf