8.1 NTRU 与 Kyber：两条构造路线

8.1 NTRU 与 Kyber：两条构造路线

NTRU（1996 年）比 LWE 早了近十年，用"小多项式除以小多项式"的环结构直接造加密；Kyber 走的是 MLWE 归约保单路线。两者的格安全本质同源，但工程气质迥异——NTRU 的紧凑血统延续到 Falcon 与 HAWK，把签名尺寸压到 ML-DSA 的零头。本节画对照图、算尺寸账、拆紧凑签名的小字节数原理。

承接第 4 章：你已经造过 Kyber 骨架；本节横着看另一条路线，并回答一个高频问题——"既然格难题是一家，方案为什么不合并成一家"。读完本节，你对第 7 章参数表里"为什么还有备胎"的疑问会一并了结。

结构对照：一张图看懂分野

图：NTRU 与 Kyber 的结构对照

数学上的分野可以一句话戳穿。Kyber 的公钥是"矩阵乘向量加噪声"：t = As + e，安全证明沿着 3.1 节的归约链条走通。NTRU 的公钥是"小除小"：h = g \cdot f^{-1} \bmod q，其中 f, g 的系数小到只有负一、零、一——攻击者若能从 h 里拆出 f 或 g，就落进了"NTRU 格"这个特殊格的短向量搜索，火力阶梯照打。区别在担保的成色：NTRU 最初二十余年只有启发式安全论证（后来对特定参数化补上了与环带误差问题的联系），Kyber 则从第一天就带着最坏情况归约——这是标准选了 Kyber 而非 NTRU 的第一性原因。值得补充的是，NTRU 的解密流程自带一层"噪声过滤"的巧思：用 f 的模 p 逆先把消息层剥出来，小系数性质保证噪声不越界——整套设计与 4.1 节的 q/4 判界异曲同工，只是把判界工作从解密端挪到了密钥结构里。

尺寸账：紧凑的代价谱系

把两条路线的现役与候选选手放上一杆秤（尺寸为字节，均取 NIST 类别一档附近）：

两笔观察。其一，签名的字节鸿沟：Falcon 的约 666 字节对 ML-DSA 的 2420 字节，差距来自机制——Falcon 用 GPV 陷门采样直接"算出"短签名（4.3 节的高斯采样升级版），不需要 ML-DSA 那种为防泄露而放大的响应多项式。HAWK 走得更激进，签名压到约 229 字节，公钥则相应变肥——安全信息守恒，只会在公钥与签名之间搬家。其二，实现的隐形账单：陷门采样需要高精度浮点运算与连续高斯采样，常量时间化极难（6.3 节红线的加强版），这正是 ML-DSA 用尺寸换实现稳健性的深层逻辑。2024 年 10 月 NIST 公布的补充签名征集首批名单里，HAWK 一类紧凑格签名与多变量方案同台，目标直指百字节档——如果你在做区块链或射频场景，这个赛道值得持续盯。

怎么用这个对照

给三条可直接执行的建议。KEM 不必纠结：ML-KEM 已是标准且性能足够，NTRU 系当前主要作为混合组件出现在 SSH 等协议里，跟着协议走即可。签名按预算分：常规场景用 ML-DSA（实现稳健优先）；尺寸敏感且能获得高质量实现审计的场景，评估 Falcon 与 FN-DSA。盯住新候选的两大件：每个新签名都先问"公钥加签名总字节"与"常量时间实现是否已有独立审计"——这两问能滤掉绝大多数宣传泡沫。

为什么标准没让 NTRU 当 KEM 主力

这段历史值得单独立案，因为它示范了标准化如何权衡"好"与"可证明"。NTRU 在 NIST 征集里走到了第三轮备选位，综合表现并不差：性能老练、三十余年无灾难性攻击。落选的逻辑有三层。第一层，担保成色：Kyber 的 MLWE 保单直通最坏情况格难题，NTRU 的论证链至今更依赖参数化经验——对一个要用几十年的标准，条款写法的差异是决定性的。第二层，专利包袱：NTRU 早期专利虽已到期，但二十年的授权史让生态对其"净室程度"心存顾虑，标准化天然偏爱无历史包袱的候选。第三层，实现简单性：ML-KEM 全程整数运算、无高精度采样，工程审计面小；这对"全球都要能安全实现"的标准是硬通货。三条合起来并非否定 NTRU——它在 SSH 混合协商里的现役地位就是价值证明——而是示范了标准的评选不选最炫，选最稳。

问题：Falcon 的高精度采样到底难在哪

拆成两难。难一，连续分布的离散化：Falcon 的陷门采样要在实数域算高斯分布再落到整数格点上，任何舍入误差都可能让输出分布偏离理论形状，进而泄露陷门的方向信息——实现者必须把浮点精度当成密码学参数来管理。难二，采样与时间的解耦：拒绝式采样可以靠重试抹平时间差异，Falcon 的高斯采样没有"重试"这个工具，必须让每次采样的指令流天然与输出无关，掩码化更难。所以 Falcon 的安全实现清单比 ML-DSA 长一截，FN-DSA 标准化推迟到 203 系列之后，实现难度正是主因之一。

顺手把本章的对照方法沉淀成模板——以后遇到任何"新格方案"，按四栏填空即可定位：栏一，困难问题与担保写法（归约到什么、什么档位）；栏二，秘密与误差的形态（短向量还是带噪声方程，决定攻击面）；栏三，尺寸三件套（公钥、私钥、密文或签名）；栏四，实现成熟度（常量时间、审计记录、库支持）。四栏填完，方案在生态里的真实位置就画出来了——这比记住它的名字有用得多。

要点速记：NTRU 小除小、Kyber 噪声乘，同岩层不同担保写法；标准选 Kyber 归因于归约保单的成色；Falcon 与 HAWK 的小签名来自陷门采样，代价是实现与审计难度；安全信息在公钥与签名间守恒，总账不会消失。

下一节从工程分流转入能力纵深：混淆这个"密码学圣杯"为什么倒在了自己的脚手架上。