4.2 签名上手：Fiat-Shamir 与 Dilithium

4.2 签名上手：Fiat-Shamir 与 Dilithium

Fiat-Shamir 变换把"证明者知道秘密"的交互式问答，用哈希压成非交互签名；拒绝采样则保证签名的响应不泄露秘密的统计信息。Dilithium（FIPS 204 的 ML-DSA）把两者架在 Module-LWE 与 Module-SIS 之上，本节推演它的骨架流程，并逐项验算"拒绝"的数学余量——那道 \gamma_1 - \beta 的界，是整个方案安全性的闸门。

承接 4.1 节：加密的核心是"用盲化多项式藏住消息"；签名的核心反过来了——公开地证明自己握有某个短秘密，同时不泄露它的任何一个比特。这两件事共享同一个环、同一套噪声经济学，读完本节再进 4.3 节的密钥派生，格原语的三大件就集齐了。

骨架：一次三步的问答

签名协议的雏形是一个三步交互（Sigma 协议）。公私钥：私钥是两个短多项式 s_1, s_2（系数落在 [-\eta, \eta]），公钥 t = A s_1 + s_2，其中 A 是公开的随机环元素矩阵。签名者证明自己知道 s_1，流程如下：

1 承诺：随机取短多项式 y，计算 w = A·y，发送 w
2 挑战：验证方随机发 c（或用 c = H(消息 || w) 非交互化）
3 响应：z = y + c·s1，发送 z

验证：检查 A·z 是否等于 w + c·t，并检查 z 的范数足够小
​

验证等式自己就能核：A \cdot z = A \cdot y + c \cdot A s_1 = w + c \cdot (t - s_2)，若忽略 s_2 的存在（正式方案把它折进承诺），等式成立即证明响应者"知道 c \cdot s_1 对应的那个短量"。把第 2 步的挑战换成哈希，验证方就消失了——这就是 Fiat-Shamir：哈希函数扮演随机挑战者，攻击者想操纵挑战就得攻破哈希，而哈希可以随便选抗碰撞的格哈希（2.3 节正好是现成的）。

麻烦在哪：响应会说话

初版方案有个致命细节：z = y + c \cdot s_1 的分布不是均匀的——y 是均匀的，但叠加了 c \cdot s_1 之后，分布整体朝着 s_1 的方向偏。采集足够多签名做统计，攻击者能像听诊一样把 s_1 从分布偏移里"听"出来，历史上多个早期格签名正栽在这里。

Lyu-Shamirski（后更名 Lyubashevsky，业界简称 LS）给出的解法漂亮而反直觉：发现响应"说漏嘴"时，当场作废重来。签名者算出 z 后先自查：若 \|z\|_\infty \ge \gamma_1 - \beta，丢弃本次 y，重抽再签（所以这类方案叫 Fiat-Shamir with aborts，带放弃的 Fiat-Shamir）。只要 y 的系数均匀取自 [-(\gamma_1 - 1), \gamma_1 - 1] 且拒绝阈值卡在 \gamma_1 - \beta，输出分布就与 s_1 统计独立——秘密被"藏进了重试里"。

动手验算：那道 130994 的闸门

把 ML-DSA-44（对应 NIST 类别二，旧称 Dilithium2）的参数代进去验一遍。模数 q = 8380417 = 2^{23} - 2^{13} + 1；环维 N = 256；\eta = 2，故 s_1 每个系数在 [-2, 2]；挑战 c 恰有 \tau = 39 个非零系数（各为 \pm 1）；\gamma_1 = 2^{17} = 131072。逐项算：

• c \cdot s_1 单个系数的最坏取值：39 个非零项同号叠加，39 \times 2 = 78。这就是界 \beta = \tau \cdot \eta = 78 的来历——不是拍出来的数，是乘出来的数。
• 接受阈值：\gamma_1 - \beta = 131072 - 78 = 130994。任何响应系数摸到 130994 及以上，整张签名作废重签。
• 重签概率估算：y 每个系数均匀分布在宽度约 2\gamma_1 的区间，"撞线"比例约 \beta / \gamma_1 \approx 0.06\%；一份签名含 l \times N = 4 \times 256 = 1024 个系数，全部幸存的概率约 (1 - 0.0006)^{1024} \approx 54\%——平均签不到两次就成一次，代价可忽略，换来的是响应分布与秘密彻底解耦。

验证端还要一道检查：由 z 反推的 w' = A z - c \cdot t 与承诺 w 的差距必须落在 \gamma_2 = (q-1)/88 = 95232 的低范数区内（配合一个"提示" hint 修正高位），否则同样拒绝。这条检查封的是伪造路径：没有 s_1 的人想让等式成立，只能掏出一个短向量解——那就是在解 3.2 节桥接过来的 SIS，难度由第 3 章的账本担保。拒绝采样的余量结构见下图。

图：拒绝采样的余量闸门

对照官方参数与尺寸

三笔对照账。对照 ECDSA：P-256 签名 64 字节、公钥 32 字节，ML-DSA-44 大了一个多数量级——这是格签名为抗量子付的现价，也是第 8 章"百字节签名"新征集存在的理由。对照 Kyber：同为类别一档位，Kyber 密文 768 字节，Dilithium 签名 2420 字节——签名天然比加密重，因为要携带完整的响应多项式。对照 Falcon：同为格签名，Falcon-512 签名约 666 字节，靠的是 GPV 陷门采样而非拒绝采样（代价是实现难度陡增，需浮点采样防侧信道）——两条技术路线的取舍在 8.1 节展开。实现层面最后提醒一句：签名的全部循环必须常量时间，"作废重签"的次数也属于可观测信息，别让计时器替你签出秘密。

要点速记：Fiat-Shamir 用哈希替随机挑战者，格哈希可就地取材；响应分布会泄露秘密，拒绝采样把泄露关进重试里；\beta = \tau \cdot \eta 与 \gamma_1 - \beta 全是可手算的数；ML-DSA 签名 2420 字节起，贵在响应、重在抗量子。

下一节把这套原语推向更高阶的功能：公钥不再是随机串，而是你的身份乃至你的属性集合。