3.1 最坏情况保单：归约链条漫步
3.1 最坏情况保单：归约链条漫步
安全归约是一份逻辑担保：若存在能在现实时间内破解方案的算法，就能把它改造成解决某个公认数学难题的算法——而那个难题被挑的是最坏情况下也难的版本。本节沿着"破解密文 → 区分 LWE 样本 → 解最坏情况格难题"这条链走一遍，看清保单的每一行条款。
承接第 2 章：四大难题已经在手，但"难题"与"方案安全"之间还隔着一纸契约，本节就是把契约摊开来读的一节，读完你将获得评价任何密码方案安全声明的通用格式，并通往 3.2 节的难题等价网络。
保单的格式：一个假设换一个结论
安全归约的标准句式长这样：假设问题 X 在时间 T 内不可解，则方案在敌手模型 M 下以优势 ε 不可破。读的时候盯三处。第一处是 X 是什么——是"平均情况随机实例"还是"最坏情况任意实例"，格密码的独特卖点在于归约的终点常常是最坏情况，等于把安全性系在整个学科的难度共识上，而不是系在"随机实例恰好难"的祈祷上。第二处是 T 的量级——归约通常有开销，"若破方案需 2^{60} 步则解难题需 2^{50} 步"这类损耗会直接吃掉安全边际，参数估算必须把它算进去。第三处是归约本身是经典还是量子——Regev 的原始归约是量子的，意味着"量子计算机也攻不破"这句声明用的是量子归约；后来 Peikert 在 2009 年给出了到 GapSVP 的经典归约，保单从此分经典与量子两个险种。
用保险的语言重述一遍：RSA 的保单写的是"大数分解难"，而且只保"随机生成的数难分解"，某种意义上它的安全性还与"分解设备价格"这样的工程现实挂钩；格密码的保单写的是"任意一个 n 维格，只要你能在它上面近似求解最短向量，你就能破解我的方案"。前者赌随机性，后者赌最坏情况——这就是为什么学界对格方案的长期信心更强。
漫步链条：从一次解密查询到最坏情况格
把"破解 Kyber"这类坏消息沿链条传导，每一环都是一次严格构造。下图是全链视图，我们逐环下蹲检查。
图：安全归约链条——破解方案传导到最坏情况难题
逐环看接缝。第一环，方案到 LWE：第 4 章你会看到 Kyber 的密文组件恰好长成 (A, As + e) 的样子——敌手若能区分密文与均匀随机串，这个区分器拿去喂 LWE 实例就是现成的判定算法，方案构造时就把两件事焊死在一起。第二环，判定到搜索：直觉是对每个候选 s' 把样本"去噪重随机化"，用判定器当裁判逐坐标二分；标准参数下两者多项式时间互归约。第三环，搜索 LWE 到格难题：Regev 的构造把 LWE 样本反过来喂给一个假想的格难题求解器，采样误差的统计性质保证了"求解器若在最坏实例上成功，就能分辨 LWE 与随机"。
保单的免赔条款：近似因子与参数的距离
最坏情况担保有一行小字：近似因子。归约到的是"近似 \tilde{O}(n/\alpha) 倍的 GapSVP"这类问题，\alpha 是噪声率（误差宽度除以 q）。噪声越相对小，\alpha 越小，近似因子越大，保额越薄；所以效率派总想把噪声压小、把 q 拉大，安全性却要求噪声别太薄——第 7 章参数表里每一处 \eta 与 q 的搭配，都是这条拉锯线的落锤。此外归约有 紧度 差异：紧归约损耗几个比特，松归约可能损耗几十个比特，这直接解释了为什么同一套参数在不同口径的估算下安全位数有出入——那不是谁算错了，是保单条款不同。
动手感受一下因子的量级：Kyber512 的 n 折合 512、噪声率大约 \eta\sqrt{2\pi}/q 量级，折算的近似因子在数千到数万之间——即归约保的是"近似几千倍的最短向量问题"这个难度，而这个近似档位的格问题，目前无论经典还是量子算法都只能望其项背。2.1 节那句"维数是护城河"，在这里换算成了可审计的条款。
最后值得记住的视角：归约链条也是风险传导图。链条右端若出现突破（某个近似档位的格难题有了新算法），传导到左端就是"某类参数全面告急"；链条中段（判定到搜索、方案到 LWE 的焊点）出问题，则只影响特定构造。给参数做风险分级时，先画自己方案的归约链，再标注每一环的"历史承压记录"——这一步做完，你对"哪些消息该慌、哪些消息只是标题"会有一目了然的判断。
三个经典误读，逐个拆掉
误读一："归约是双向的，所以方案破不了"。归约的方向是"破解方案则难题可解"，它的逆（难题难则方案安全）才是我们想要的那一半；但这一半的强度受归约紧度与近似档位约束。正确的读法是把安全声明当成条件句，再用第 3.3 节的账本对条件本身估价，两层合起来才是一份完整评估。误读二："最坏情况难等于所有实例都难"。最坏情况归约保证的是"存在难实例且随机实例以压倒性概率难"，不排除个别实例存在结构捷径——这正是参数要用随机采样、且要避开已知的坏结构（如某些弱多项式）的原因。误读三："归约到量子难题意味着必须先造出量子计算机才安全"。方向反了：量子归约声明的是"即便对手拥有量子计算机，破解仍意味着解难题"，它是对更强对手的覆盖，不是对更弱对手的让步。
问题：为什么 SIS 的归约早于 LWE 十年
1996 年 Ajtai 证明的是 SIS 型问题与最坏情况格近似的联系，但它直接给出的是哈希与承诺类原语，加密还需要"带陷门的可逆性"这块拼图。Regev 2005 年引入 LWE 的贡献正在于此：误差让解码成为可能，秘密向量让陷门有了着力点，加密、KEM、FHE 的整条生产线随后陆续开动。读标准文档时若看到"归约到 SIVP"与"归约到 GapSVP"两种措辞，对应的就是这两代技术：前者源自 Ajtai 谱系，后者出自 LWE 谱系的判定版。
把本章与第 2 章的难度直觉接上线，归约的价值还有一层"资产属性"：分析者对格难题持续多年的投入（第 6 章的算法、估算工具的打磨）会自动加厚所有归约到它的方案的担保，而方案设计者无需改一行代码。反观那些把安全性系在自有私有难题上的设计，每一次相关分析都可能是独立的坏消息。选择"把鸡蛋放进最被广泛研究的难题里"，看似拥挤，实为理性——被攻击得最多的难题，才是被理解得最透的难题。
下一节把镜头转向难题之间的关系：这些担保品之间能不能互相兑换？答案是能，而且兑换构造可以亲手做。