什么是 SIS#

SIS 全称 Short Integer Solution，本质上其实是一个数学问题（对相关内容感兴趣的请自行搜索，这里不做过多赘述）。但是由于是在后量子密码学的范畴里面，而且是以抽象代数、线性代数、数论等内容为基础，所以说有一定的上手难度，初学理解起来会比较困难，这也包括我。说实话我之前第一次接触 SIS 的时候其实也是很懵的，但是经过这段时间的学习，自己有了一些新的理解。

后量子密码与格#

后量子密码虽然听起来很高深，但是实际上也确实一点都不简单（小小整个活 hh）。说白了就是在以格的基础上进行的相关构造。

那什么是格呢？简单来说就是一组高维空间中的离散点集（好吧其实这个说法蛮抽象的，一点都不简单）。换个说法类比：学过线性代数的都知道，三维或者二维空间的任意一个位置是由坐标 (X, Y) 进行表示的，XY 都是实数。但是在格这里，XY 被换成了整数。可以这样简单理解，但是更准确地说：格是某组线性无关基向量的整数系数组合构成的点集，而不仅仅是整数格子点。

在这个基础上有了向量，坐标表示和线代是一样的，然后在这个的基础上就可以进行相关数学困难性问题的构造，并以这些问题为基础，有了 SIS 等一系列问题的产生和应用。

为什么是”困难”问题#

但是不知道各位有没有想过一个问题：既然底层和线代关系这么大，那为什么说是数学困难性问题？毕竟如果是大学里面纯线代的话，其实数学层面普通计算谈不上困难性。这就要牵扯到格的相关定义和具体的 SIS 问题了。

首先，SIS 问题是建立在格的基础之上的。看格的定义你会发现，形式上和普通线代是很类似的，最大的区别就是多了一个高维空间中的离散点集。这个区别有什么影响呢？其实这会带来一些和线代里面不同的东西：

第一个区别：Z-模 vs 实数域。 因为是离散点集，所以基础是建立在群上面的（这里不懂的自己可以先想想）。由于满足交换律，所以也隶属阿贝尔群。但是仔细想想会发现：线代里面都是实数域，是在域上面的计算；而这里是阿贝尔群，加上从定义推导出来也隶属整数环，所以是一个阿贝尔群 + 整数环的结构，也就是所谓的 Z-模——满足数乘，但是不满足除法（这里说的有点快，不懂得可以自己琢磨一下）。但是现代里面实数域就不一样，这是第一个区别。

第二个区别：mod 运算。 光有抽代层面的区别还不够，仔细看 SIS 问题会发现，这里面有一个 mod，这是啥嘞？了解过数论会知道这就是数论里面的一个运算符，也就是模幂运算，而且由于运算性质的特殊性，和传统加减乘除是不一样的（我是之前最开始接触 RSA 的时候了解到的这个，并不是 SIS 这里，所以提前有一点了解）。

这就导致了一个问题：很多传统运算方法和思路在这里是不成立或者说要发生改变的。举个简单的例子：基于整数的运算实际上就不是在整数域上面，而是在整数环；模 q 运算把无限大的整数空间映射到有限集合 {0,1,…,q-1}，因此方程 A·x ≡ 0 (mod q) 的解在整数上会周期性重复，解集是一个格，这是第二个主要区别。

SIS 问题的定义#

说了这么多，咱们重新来看一看 SIS。首先说明，SIS 问题是：

给定一个随机矩阵 A 和模数 q，寻找一个非零整数向量 x，使得 A·x ≡ 0 (mod q)，并且向量 x 的长度（欧几里得范数或无穷范数）不超过一个给定的界 β（此处欧几里得范数和无穷范数概念如若不懂请自行搜索）。

这是定义的问题本身。

求解思路：从坏基到好基#

这时候就有人想问了：你既然说这个 mod 是一个循环运算的结果，往上搜又发现方程的解是在一个具体的格基空间里面，这感觉不太理得清楚啊？别急，咱们一步一步来。

首先关于 mod：这个运算结构确实特殊这没错，但是并不意味着我们没有办法进行处理。事实上，方程 A·x = 0 (mod q) 在整数上等价于 A·x = kq 对某个整数 k 成立，因此解集可以看作一个格。你看，这就是一个典型的线代问题——通过相关线代知识我们可以用变量把这个 x 的解求出来。但是因为存在变量，所以 x 不是一个值，而是一个解空间，这就是格基空间的来历。我们要做的就是在这个空间里面寻找我们想要的符合要求的向量，由于已经是解空间了，所以找到的向量天生就满足原方程。

那具体要怎么寻找呢？这就是目前国际上研究的一个热门领域，我这里只说一个大致的主流思路：

1. x 的解求出来是有变量没错，也是一个解空间没错，但是解空间是有基向量的，而通过纯解原方程得到的基向量会很”斜”，导致我们不容易求解。
2. 此时就要先通过相关计算方法把坏的格基变得好一点，也就是尽量正交（为什么说尽量？因为是在高维空间中的离散点集，按照传统线代求出来的严格正交的向量坐标可能不是整数），这一步的目的是方便我们构造初始的好的候选向量，方便后续还原回去。
3. 然后在好基的基础上引入随机的向量，并进行筛选（这一步的目的是在候选向量中找到尽可能更好的向量）。
4. 之后反过来代回原来的坐标系中，才可以求得对应向量。至于解出来的符不符合要求，就是另外一码事了。

总之，以上只是我个人关于 SIS 问题的一些理解，如果有细节出错或者不严谨的地方也欢迎各位老师指出。后续会有考虑继续学习相关知识出类似的文章，如果有老师有相关的好的建议也欢迎提出来，我将万分感激！

原文发布于知乎（2026-04-27），收录于《桂电密码学本科生的密码学学习笔记》系列，作者：亦梦。