3.2 问题之间的桥：等价性与互归约

3.2 问题之间的桥：等价性与互归约

互归约是难题之间的兑换渠道：把 A 问题的实例改造成 B 问题的实例，解出 B 再翻译回 A，两步的开销都可控制，则"B 不比 A 容易"。本节亲手做两座桥——把 2.1 节的 CVP 实例嵌入三维变成最短向量问题（Kannan 嵌入），把 2.3 节的 SIS 解变成 LWE 样本间的短依赖——等价性从名词变成你手上可复算的动词。

上一节说方案的安全性被锚在某一个难题上；本节补全图景：这些难题彼此相连，攻击者从任何一个方向挖隧道，最终通向的是同一片岩层。读完本节，第 6 章攻击代码里那步"升维嵌入"你将一眼认出它的出身。

先动手：把最近向量问题嵌入高一维

2.1 节我们解过一道 CVP：格由 b_1 = (4,1)、b_2 = (2,3) 张成，目标 t = (7,4)，真解是最近的格点 (6,4)。Kannan 嵌入的思路：把这道题改写成高一维的 SVP——新增一个维度，把目标点"钉"进去，再用一个精心挑选的小系数 M 把答案与噪声分开。构造出来的三维基：

第三行就是目标点 t 抬高 M 倍后的样子。现在问：\mathcal{L}(B') 里最短的向量是谁？枚举一下三类候选。第一类，第三坐标为 0 的向量：它们恰好是原格 \mathcal{L} 的成员，最短的是 (2,-2,0)，长度平方 8。第二类，第三坐标为 kM（k = \pm 1）的向量：形如 (t - v, 2)，其中 v \in \mathcal{L}，长度平方 \|t-v\|^2 + 4，取 v = (6,4) 时最小，等于 1 + 4 = 5。第三类，|k| \ge 2：光第三坐标就贡献 16，出局。

冠军是 (1, 0, 2)，长度平方 5——它的前两维正是 t - (6,4)。也就是说：解出嵌入格的 SVP，摘下第三坐标，最近格点 (6,4) 就躺在答案里。M 的挑选规则就藏在刚才的枚举里：M 要大于目标到格的距离（否则答案混进别的 v），又小于最短向量长度（否则原格向量抢走冠军）。这道桥是单向的收费桥：CVP 付费换 SVP，而它在攻击工程里就是第 6 章"原始攻击"（primal attack）的核心零件——把 LWE 密钥恢复问题嵌入升维后交给 BKZ，你将在 6.2 节看到完整流水线。

另一座桥：SIS 的短依赖与 LWE 的对偶

把 2.3 节的战利品翻出来再看一眼。我们在 A = \begin{pmatrix} 1&2&3&4&0&1 \\ 3&0&2&1&4&2 \end{pmatrix} \bmod 5 上找到过短向量 z = (-1,-1,-1,-1,-1,0) 满足 Az \equiv 0。把 Az 展开成列组合：z_1 c_1 + z_2 c_2 + \cdots + z_6 c_6 \equiv 0 \pmod 5，其中 c_j 是 A 的第 j 列。代入验证：-c_1 - c_2 - c_3 - c_4 - c_5 = -(1+2+3+4+0,\; 3+0+2+1+4) = -(10, 10) \equiv (0,0)，成立。

换个视角立刻不一样了：把这六列看作六个"样本向量"，那么 z 说的是——这批样本之间存在一组系数极小的模 q 线性依赖。如果有人把 A 的转置当成一个 LWE 实例的样本矩阵发给攻击者，攻击者梦寐以求的东西正是这样的短依赖：拿到它，代入解密关系即可把秘密剥出来。SIS 解（找短依赖）与 LWE 攻击（利用短依赖）在这里咬合成同一枚齿轮——这就是所谓 SIS 与 LWE 互为对偶的算术内核。矩阵转置、误差搬家，两道难题共享同一片"对偶格"岩层；2.3 节表格里那句"LWE 管加密、SIS 管哈希"，此刻有了机制层面的解释。

搜索与判定：同一个问题的两张考卷

LWE 的搜索版（求出 s）与判定版（分辨样本与均匀随机）也是一座双向桥，标准参数下多项式时间互归约。搜索到判定方向的直觉值得动手模拟：给定一个判定预言机，把它当裁判用。对每个候选秘密 s'，把样本改写为 (a_i,\; b_i - \langle a_i, s' \rangle)——若 s' 猜中，新样本的第二分量恰好等于误差 e_i，整体分布是"秘密为零的 LWE"；若猜错，第二分量等于 e_i + \langle a_i, s - s'\rangle，多出一项貌似均匀的偏移。于是逐候选喂给裁判，点头的那张考卷就是答案。骨架三行：

for s_prime in 候选空间:                    # 实际实现按坐标二分，非暴力
    T = [(a_i, b_i - <a_i, s_prime>) for i in 1..m]
    if 判定预言机说 T 像 秘密为零的 LWE:
        return s_prime
​

反向（判定到搜索）的构造要用到高斯消元配合重随机化，篇幅所限不展开，只需记住结论：在 q 较大、误差温和的标准参数区，两张考卷同难度——所以安全声明里写判定版不等于偷工减料。

等价性的工程含义

三座桥合起来解释了第 6 章的一个现象：攻击 LWE 的文献里全是"找短向量"的语言——因为经过这些桥，加密问题已被兑换成了格上的几何问题，攻击者的全部火力都倾泻在 SVP/CVP 的近似算法上。

问题：SVP 能反向归约到 CVP 吗

本节的 Kannan 桥是 CVP 换 SVP 的单向道；反向的直接归约并不对称——SVP 给的是"全域最短"，CVP 问的是"指定目标附近"，前者信息量更集中。实操里 CVP 实例走嵌入桥化成高一维的特殊 SVP（最短向量恰好是嵌入差），这也解释了为什么攻击代码库里往往只有一个 SVP 求解器：所有问题经过桥的改造，最后都汇流到这一个入口。

要点速记：Kannan 嵌入把 CVP 变成高一维 SVP，M 的取值区间由目标距离与最短向量长度夹出；SIS 的短零化向量就是 LWE 样本的短依赖，对偶格是两者的公共岩层；搜索与判定 LWE 在标准参数下同难度；归约桥是攻击代码可复用的根源。

难题已连成一张网，下一节给这张网标价：维度与模数，各值多少安全位数。