13 SIS 问题与短整数关系#

整理日期：2026-10-16。
前置笔记：04 基本计算格问题：SVP、CVP 与 SIVP、12 q 元格与模线性方程。

沿用记号

$$A=(a_1,\ldots,a_m)\in\mathbb Z_q^{n\times m}, \qquad q\ge2,\quad n\le m.$$

向量按列排列，本文使用欧氏范数。

#1. SIS 的定义与格解释

短整数解问题（Short Integer Solution，SIS）要求：给定 $A$ 和长度界 $\beta>0$，找到

$$\boxed{ x\in\mathbb Z^m\setminus\{0\}, \qquad Ax\equiv0\pmod q, \qquad \|x\|_2\le\beta. }$$

记为 $\mathrm{SIS}_{n,m,q,\beta}$。定义见 Micciancio《Random Lattices and Lattice-Based Cryptography》，Fall 2019，PDF 第 1 页，Definition 1。

按列展开，模方程就是

$$x_1a_1+\cdots+x_ma_m\equiv0\pmod q.$$

因此，SIS 寻找的是列向量之间的一条非零短整数关系：系数是整数，系数向量的长度受到限制。

利用第十二篇的模核格，

$$\Lambda_q^\perp(A) = \{x\in\mathbb Z^m:Ax\equiv0\pmod q\},$$

SIS 等价于在其中寻找长度不超过 $\beta$ 的非零格向量。

这里的 $\beta$ 是绝对长度界。SIS 不要求找到最短向量，也不直接要求满足 $\|x\|\le\gamma\lambda_1$ 这样的近似比。

#2. 参数与平凡解

四个参数分别规定：

• $n$：模线性方程的个数。
• $m$：整数变量的个数，也是模核格的秩。
• $q$：模数。
• $\beta$：允许的最大解长度；在其他参数固定时，增大它会放宽输出要求。

定义中的“非零”指整数向量 $x\ne0$。由于

$$A(qe_i)\equiv0\pmod q, \qquad \|qe_i\|_2=q,$$

当 $\beta\ge q$ 时，直接输出 $qe_i$ 即可。因此，这一定义下具有密码学意义的参数通常需要满足

$$\boxed{\beta<q.}$$

另一方面，给定矩阵 $A$ 后，合法解存在当且仅当

$$\beta\ge\lambda_1\bigl(\Lambda_q^\perp(A)\bigr).$$

所以，排除平凡解与保证短解存在是两项不同要求。

当 $q$ 为素数时，线性消元可以描述模核，但不会自动给出满足指定长度界的整数解。SIS 的额外要求正是对整数系数的长度控制。

#3. 用抽屉原理保证短解存在

考虑映射

$$h_A:\{0,1\}^m\longrightarrow\mathbb Z_q^n, \qquad h_A(u)=Au\bmod q.$$

输入集合有 $2^m$ 个元素，输出集合有 $q^n$ 个元素。若

$$2^m>q^n \quad\Longleftrightarrow\quad m>n\log_2q,$$

则存在两个不同的二元向量 $u,v$，满足

$$Au\equiv Av\pmod q.$$

令 $x=u-v$，便得到

$$x\in\{-1,0,1\}^m\setminus\{0\}, \qquad Ax\equiv0\pmod q, \qquad \|x\|_2\le\sqrt m.$$

因此，

$$\boxed{ m>n\log_2q \quad\Longrightarrow\quad \text{每个 }A\text{ 都存在长度不超过 }\sqrt m\text{ 的非零解}. }$$

这一推导适用于任意整数 $q\ge2$，不要求 $A$ 满行秩。二元输入的模线性映射与碰撞构造见 Regev《Lecture 12: Average-case Hardness》，Fall 2004，§1，PDF 第 2 页，Definition 3。

由此得到一组方便理解的条件：

$$m>n\log_2q, \qquad \sqrt m\le\beta<q.$$

它们同时保证短解存在，并排除 $qe_i$ 这样的平凡解。这些条件是存在性与非平凡性的条件，尚不能据此判断计算安全性。

抽屉原理只保证某处存在碰撞，没有提供高效找到碰撞的方法。

#4. 随机实例与 SIS 困难假设

密码学通常研究均匀随机矩阵

$$A\leftarrow U\!\left(\mathbb Z_q^{n\times m}\right)$$

上的 SIS，而不只是某一个特定矩阵上的搜索任务。这里每个矩阵元素都独立、均匀地取自 $\mathbb Z_q$。

在渐近表述中，以 $n$ 为安全参数，将其他参数写为

$$m=m(n),\qquad q=q(n),\qquad\beta=\beta(n),$$

并使输入长度关于 $n$ 多项式有界。这样的随机实例族见 Micciancio–Regev《Worst-case to Average-case Reductions based on Gaussian Measures》，2005-12-14 作者稿，§5.1，PDF 第 17 页，Definition 5.3。

对选定的参数族，SIS 困难假设要求：任意概率多项式时间算法在上述随机实例上成功找到合法短解的概率都是可忽略的。概率同时计入矩阵的抽样和算法自身的随机性。

其中，可忽略函数 $\operatorname{negl}(n)$ 满足：对任意常数 $c>0$，当 $n$ 充分大时，

$$\operatorname{negl}(n)<n^{-c}.$$

因此，讨论 SIS 困难性时必须同时说明参数、范数、实例分布和成功概率。短解存在是前提；能否高效找到它，是另一个问题。

#5. 哈希碰撞如何给出 SIS 解

继续使用第三节中的映射

$$h_A(u)=Au\bmod q, \qquad u\in\{0,1\}^m,$$

并把均匀随机选取的 $A$ 作为公开的哈希密钥。

计算 $h_A(u)$ 只需要矩阵乘法与模运算。寻找碰撞则要求找到

$$u\ne v, \qquad h_A(u)=h_A(v).$$

任何这样的碰撞都会给出

$$\boxed{x=u-v}$$

作为一个 $\mathrm{SIS}_{n,m,q,\sqrt m}$ 解，因为它非零、满足模方程，且长度不超过 $\sqrt m$。

因此，如果某个高效算法能以非可忽略概率找到随机 $h_A$ 的碰撞，那么将其输出相减，就能以相同概率解决对应的随机 SIS 实例。于是，

$$\boxed{ \mathrm{SIS}_{n,m,q,\sqrt m}\text{ 困难} \quad\Longrightarrow\quad \{h_A\}\text{ 具有碰撞抗性}. }$$

这正是从短整数关系建立碰撞抗性哈希的基本思路。见 Regev，§1，PDF 第 1–2 页，Definition 2–3，以及 Micciancio，§1，PDF 第 3 页关于 $X-X$ 的说明。

这里使用的是“碰撞产生 SIS 解”这一方向。一般 SIS 解未必具有 $\{-1,0,1\}$ 坐标，因此不能直接将任意短解拆成上述二元输入域中的一对碰撞。

当 $m>n\log_2q$ 时，碰撞必然存在；碰撞抗性要求的是高效算法难以找到它。

#6. 与最坏情况格问题的联系

SIS 的困难性还与最坏情况到平均情况归约有关。

例如，Micciancio–Regev 在特定参数族上给出了从最坏情况近似 SIVP 到随机 SIS 的归约。其含义是：如果能以非可忽略概率高效求解随机 SIS，就能高效解决该定理对应的一般格上的最坏情况近似问题。见 Micciancio–Regev，§5.3，PDF 第 25 页，Theorem 5.16。

这种联系依赖具体的参数条件与近似因子，不能仅由 $\beta<q$ 或短解存在性推出。完整归约将在后续结合高斯分布和平滑参数学习。

#引用此笔记

• 00 概览与阅读路线
• 14 LWE 问题与带噪线性方程