2.3 SIS 哈希手算：从抽屉原理到抗碰撞

2.3 SIS 哈希手算：从抽屉原理到抗碰撞

短整数解问题（SIS, Short Integer Solution）：给定随机矩阵 A \in \mathbb{Z}_q^{n \times m}，找一个非零的"短"向量 z（系数只取 -1, 0, 1）使 A z \equiv 0 \pmod q。把 A 当公开参数，哈希函数 h_A(x) = Ax \bmod q 的抗碰撞能力恰好等价于 SIS 的难解性。本节用一个 64 输入、25 输出的迷你哈希亲手制造一次碰撞，看清抽屉原理如何变成安全论证。

1996 年，Ajtai 发表的工作给出了格密码的第一块基石，而这块基石不是加密，是一个哈希函数。它比 LWE 早了近十年，逻辑也更为直白：碰撞存在是抽屉原理的必然，找到碰撞却难如登天。承接 2.2 节的 LWE，本节补上它的对偶面孔，并通往第 3 章的安全归约——"找出碰撞"与"解最坏情况格难题"的担保链条正是从 SIS 开始的。

先动手：一个六位输入的迷你哈希

取 n = 2、m = 6、q = 5，公开矩阵：

哈希函数定义在 6 位 0/1 串上：h_A(x) = Ax \bmod 5，输出是模 5 的二维向量。先算两个输入热热手。输入 x = 000001：只有第六位是 1，h = (1, 2)。输入 x = 111111：第一位分量 1+2+3+4+0+1 = 11 \equiv 1，第二位分量 3+0+2+1+4+2 = 12 \equiv 2，h = (1,2)。

两个不同的输入，同一个输出——碰撞到手了。 差向量 z = 000001 - 111111 = (-1,-1,-1,-1,-1,0)，系数全部落在 \{-1,0,1\} 内，且 Az \equiv 0 \pmod 5：你刚刚手工解出了一个 SIS 实例。这个实例当然不堪一击，原因是参数小得离谱——6 位输入只有 64 种可能，输出却只有 5^2 = 25 种，抽屉原理保证碰撞遍地都是，随机挑几十对多半能撞上。参数放大之后图景完全反转：实战取 n=64、m=1024、q=257，输出 512 比特、输入 1024 比特，压缩率一倍；此时碰撞依旧存在（1024 位输入的空间远大于 512 位输出），但每一条候选 z 都对应一个高维格上的短向量搜索——第 6 章那套攻击账本给出的代价是天文数字。

碰撞等价于短向量：一笔严格的账

把上面的观察写成一般命题，只需要两步。

第一步，碰撞产生短向量。 若 x \neq y 且 h_A(x) = h_A(y)，则 A(x - y) \equiv 0 \pmod q。x, y 的分量都是 0 或 1，所以 z = x - y 的分量落在 \{-1, 0, 1\}——短向量，非零，且是 A 的模 q 零化向量。这是 SIS 的一个解。

第二步，短向量产生碰撞。 反过来，任何非零 z \in \{-1,0,1\}^m 满足 Az \equiv 0，取正部为 x、负部取绝对值为 y，则 x \neq y、h_A(x) = h_A(y)。两步合起来：找到哈希碰撞与解出 SIS 是同一件事。于是"该哈希抗碰撞"的断言有了精确含义：SIS 难，则哈希抗碰撞。

还有一处值得动手验证的计数：为什么 m 要比 n \log q 大？短向量 z 的候选总数是 3^m 个，而 Az 的取值至多 q^n 种。若 3^m \le q^n，可能压根不存在短零化向量，哈希会退化；只有 3^m > q^n（等价地 m > n \log_3 q），抽屉原理才保证解存在，进而才谈得上"解存在但难找"。迷你实例里 3^6 = 729 > 25 = 5^2，条件满足，果然一找一个准。Ajtai 的深刻之处在于给出了反向担保：只要找到一次碰撞，就等于解决了任意一个最坏情况下的格近似问题——平均情况的安全性被锚定在最坏情况的难度上，这条思路的完整展开是第 3 章的主戏。

代码：碰撞实验与计数校验

import numpy as np
from itertools import product

q = 5
A = np.array([[1, 2, 3, 4, 0, 1],
              [3, 0, 2, 1, 4, 2]])

def h(x):
    return tuple((A @ np.array(x)) % q)

# 暴力枚举全部 64 个输入，按输出分桶
buckets = {}
for bits in product([0, 1], repeat=6):
    buckets.setdefault(h(bits), []).append(bits)

sizes = sorted((len(v) for v in buckets.values()), reverse=True)
print("桶大小分布:", sizes[:5])        # 最大桶里有 6 个输入
a, b = buckets[h((0,0,0,0,0,1))][:2]   # 随便取同桶的两个输入
print("碰撞对:", a, b, "->", h(a))     # 例如 000001 与 111111 -> (1, 2)
print("短向量 z =", tuple(np.array(a) - np.array(b)))
print("Az mod q =", (A @ (np.array(a) - np.array(b))) % q)   # [0 0]
​

把 q 调成 257、repeat 保持 6 跑变式：桶几乎全是单元素，碰撞消失——输出空间从 25 涨到 66049，抽屉被抽薄了。压缩率与碰撞难度之间的这条拉锯线，就是哈希参数设计的全部内容。

与 LWE 的对偶：一张表看懂

对偶不是比喻而是可以写出的变换：把 LWE 样本的矩阵转置、误差挪到对偶格，SIS 与 LWE 互相派生——第 3.2 节会把这个"转置魔术"算给你看。眼下只需记住分工：要哈希找 SIS，要加密找 LWE，两者共享同一套格攻击成本模型，也因此在第 7 章的标准化名单里并肩出场。

要点速记：SIS 要求短的非零零化向量，碰撞与 SIS 解可以互相转化；m > n \log q 保证解存在，难找才构成安全；迷你实例的每一行算式都能在实战参数上原样重演，只是代价从秒级涨到宇宙级；LWE 管加密、SIS 管哈希，是同一枚硬币的两面。

第 2 章撞墙实验到此收工。第 3 章我们把镜头拉远：这些玩具级难度，凭什么敢代表实战级安全？