Module-Lattice-Based Digital Signature Standard

发表于 4 小时前

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

FIPS 204: Module-Lattice-Based Digital Signature Standard (ML-DSA)。

这份文档固然是NIST（美国国家尺度与技能研究院）发布的尺度文档，但它的前身是顶顶台甫的学术界宠儿——Dilithium（晶体-锂）。为了方便你明白，我会把这份尺度当作一篇“集大成”的论文来讲授，同时联合其背后的学术原理。
一、团体导航

1. 这篇文档到底在讲什么？

办理什么标题：我们如今的数字署名（好比比特币用的ECDSA，网站证书用的RSA）依靠于“大数分解”或“离散对数”困难，这些在将来的量子盘算机面前不堪一击。我们必要一种抗量子攻击的署名方案。
江湖职位：这是NIST（美国国家尺度局）钦定的后量子数字署名尺度，代号 ML-DSA（源自 Dilithium）。在将来几十年里，它将成为互联网安全的基石，代替 RSA 和 ECDSA。
新在那边：相比于早期的格署名（如 GGH），它极其安全且高效。它的焦点创新在于利用了“拒绝采样（Rejection Sampling）”技能，奇妙地办理了格署名中“私钥容易通过署名走漏”的汗青困难，同时克制了复杂的“高斯采样”，只用简朴的匀称采样，非常得当工程实现。

2. 笔墨版蹊径图

第1-3章（Introduction, Terms, Overview）：【略读】。相识配景和术语界说（如什么是KEM，什么是DSA）。
第4章（Auxiliary Algorithms）：【工具箱，查阅即可】。这里界说了哈希函数、数据转换格式。不消死记，用到再翻。
第5-7章（ML-DSA Algorithms）：【必须死磕！！！】。这是焦点。
KeyGen（密钥天生）：怎么造钥匙。
Sign（署名）：怎么盖章。（最难，也是英华）
Verify（验签）：怎么验证章是真的。
第8章（Parameters）：【相识结论】。知道有三个安全品级（44, 65, 87）即可。

二、焦点数学与概念拆解

在进入算法之前，我们要先扫清拦路虎。格暗码的数学门槛看起来高，实在直觉很简朴。
1. Lattice (格) 与 Module (模)

界说：想象一张无穷大的方格纸（二维格），大概高维空间里的点阵。
Module (模)：不消管代数界说。在 ML-DSA 里，你就把它明白为“多项式构成的向量”。
直觉：
平凡格暗码处理处罚的是一堆整数矩阵。
模格（Module Lattice）处理处罚的是一堆多项式。好比 \(3x^2+2x+1\) 这种东西。
为什么用它：由于多项式乘法快（用NTT加快），而且存储空间小。既安全又快。

2. LWE (Learning With Errors) / ML-LWE

界说：给你矩阵 \(A\) 和向量 \(t\)，告诉你 \(t = As + e\)（此中 \(e\) 是很小的噪声），让你求 \(s\)。
直觉（噪声掩护）：
如果不加噪声 \(e\)，解 \(t=As\) 就是初中数学的解方程组，秒破。
加了噪声 \(e\)，这就变成了“在有偏差的丈量数据中规复原始信号”，在格的天下里，这纵然对量子盘算机来说也是极难的。
脚色：掩护公钥的安全性。公钥就是 \(t\)，由于 \(e\) 的存在，没人能算出私钥 \(s\)。

3. SIS (Short Integer Solution) / ML-SIS

界说：给你一个很宽的矩阵 \(A\)，让你找一个短向量 \(z\)，使得 \(Az = 0 \pmod q\)。
直觉（大海捞针）：
满足 \(Az=0\) 的解有无穷多，但绝大多数都“很长”（数字很大）。
想要找到一个由 \(0, 1, -1\) 这种小数字构成的解，就像在大海里捞针一样难。
脚色：包管署名无法被伪造。如果攻击者能伪造署名，等同于他解出了 SIS 标题。

4. Rejection Sampling (拒绝采样) —— ⭐️ 焦点灵魂

干什么用的：防止私钥走漏。
直觉：
假设你的私钥是 \(s\)（好比是数字 100）。
你署名的结果 \(z\) 通常是 \(s\) 加上一个随机数 \(y\)（好比 \(y\) 是 1 到 10 的随机数）。
如果你直接发布 \(z = 105\)，攻击者多看几个 \(z\)，算个匀称值，就把你的 \(s\) 猜出来了！
拒绝采样的做法：署名者在发出 \(z\) 之前，先本身查抄一下：“这个 \(z\) 会不会袒露我的 \(s\)？”。如果会（好比 \(z\) 太大了，大概分布特性太显着），我就把这次署名取消，重新选个 \(y\) 再签一次。直到天生的 \(z\) 看起来跟我的私钥 \(s\) 毫无关系（像个完全的随机数），我才发出去。
脚色：这是 ML-DSA (Dilithium) 与早期被破译的格署名的最大区别。它堵截了署名与私钥的统计接洽。

三、关键构造的逐行表明

ML-DSA 本质上是 Fiat-Shamir 变更 加上 拒绝采样。
1. 焦点定理：Fiat-Shamir with Aborts

人话结论：我们可以把一个“你问我答”的身份认证协议，变成一个“我本身写证实”的数字署名。而且，如果在天生过程中发现数据欠好，允许我“重来”（Abort），安全性不受影响。
构造头脑：
交互式（身份认证）：

Prover（我）发出答应 \(w = Ay\)。
Verifier（你）给我一个挑衅 \(c\)。
Prover（我）算出回复 \(z = y + cs\)。

非交互式（署名）：
没人给我发挑衅 \(c\) 了，怎么办？
我用哈希函数 \(H\) 本身算挑衅：\(c = H(M, w)\)。此中 \(M\) 是我要署名的文件。
如许，\(c\) 就跟文件 \(M\) 绑定了，我也没法作弊（由于哈希是随机的）。

2. NTT (Number Theoretic Transform)

人话结论：一种让多项式乘法变飞快的邪术。
硕士生需知：
平凡多项式乘法是 \(O(n^2)\)，太慢。
NTT 把它变成 \(O(n \log n)\)。
在论文中：你会看到许多 \(\hat{w}\) 这种带帽子的符号，表现这是在“NTT域”的数据。你只要知道这是为了加快就行。

四、方案流程的“白板级表明”

这是你 PPT 的焦点部门。我们把 ML-DSA 的流程画出来。
Step 1: KeyGen (天生钥匙)

天生一个随机矩阵 \(A\)（通过种子 \(\rho\) 天生，省空间）。
随机天生私钥向量 \(s_1, s_2\)（系数很小，好比 -2 到 2）。
盘算公钥 \(t = A s_1 + s_2\)。

注：这就是 ML-LWE 标题，给出 \(A, t\)，求不出 \(s\)。

输出：公钥 \(pk = (A, t)\)，私钥 \(sk = (s_1, s_2)\)。

Step 2: Sign (署名) —— 最关键！

(假设要署名为消息 \(M\))

随机实行：选一个随机掩码向量 \(y\)（系数稍大一点，防走漏）。
盘算答应：算 \(w = A y\)（只取高位，压缩一下）。
天生挑衅：\(c = H(M, w)\)。

哈希把消息 \(M\) 和答应 \(w\) 熔在一起。

盘算候选署名：\(z = y + c \cdot s_1\)。

这是尺度的 Schnorr 署名结构：随机数 + 挑衅 \(\times\) 私钥。

🔴 拒绝采样 (The Check)：

查抄 1：\(z\) 的系数是不是太大了？（如果太大，大概走漏 \(s_1\) 的巨细）。
查抄 2：\(A z - c t\) 的低位部门会不会走漏信息？
如果查抄不通过：扬弃如今的 \(y, z\)，回到第1步重来！

输出：署名 \(\sigma = (z, c)\)。

Step 3: Verify (验签)

规复答应：利用公式 \(Az - ct \approx w\)。

推导：\(Az - ct = A(y + cs_1) - c(As_1 + s_2) = Ay + cAs_1 - cAs_1 - cs_2 = Ay - cs_2\)。
由于 \(s_2\) 很小，\(Ay - cs_2\) 的高位（High Bits）和 \(Ay\) 的高位根本一样。以是验证者能算出近似的 \(w'\)。

哈希校验：算 \(c' = H(M, w')\)。
判断：如果 \(c' == c\) 且 \(z\) 的系数富足小，则通过。

PPT 焦点页发起

画一个流程图：\(y \to w \to c \to z \to \text{Check?}\)。
在 "Check" 那边画一个回旋镖箭头指向开头，标注“Rejection Sampling”。这是灵魂。

五、安全性与参数分析

1. 安全性根基

Key Recovery (偷私钥)：基于 ML-LWE。如果能从 \(t, A\) 算出 \(s\)，就能解 ML-LWE。
Forgery (伪造署名)：基于 ML-SIS。如果能伪造一个合法的 \((z, c)\)，意味着你在不知道 \(s\) 的情况下找到了满足 \(Az - ct \approx w\) 的短向量 \(z\)，这等同于解 SIS。

2. 攻击模子

EUF-CMA：在“顺应性选择消息攻击”下是“存在性不可伪造”的。这是数字署名的最高安全尺度。纵然攻击者让你签了100万个他指定的文件，他也无法伪造第100万零1个文件的署名。

3. 参数防御 (Lattice Reduction)

LLL / BKZ 算法：这是攻击格暗码的“瑞士军刀”，用来在格里找短向量。
防御战略：ML-DSA 的参数（好比矩阵维度 \(k=4, 6, 8\)）是专门选的，使得格的维度富足高，导致 BKZ 算法运行时间凌驾宇宙寿命。
参数选小了会怎样：如果维度太低，BKZ 算法能灵敏找到私钥 \(s\) 大概伪造出 \(z\)，署名体系直接崩塌。

Q: 为什么 ML-DSA 不必要高斯采样？（Falcon 必要）

A: 由于 ML-DSA 利用了拒绝采样技能。我们只必要从匀称分布中采样，然后通过“剔除”不合格的样本，让结果分布变得不依靠于私钥。这克制了高斯采样带来的浮点数运算和侧信道风险，更容易在硬件上实现。

Q: 署名过程中的“拒绝采样”会导致死循环吗？

A: 理论上概率不为0，但在工程参数设置下，匀称只必要实行 4-7 次就能乐成。发生死循环的概率比宇宙扑灭还低。

Q: 这个 "Module" (模) 到底带来了什么优点？

A: 它在“服从”和“安全性”之间做了均衡。纯粹的 LWE（非结构化格）秘钥太大（几十KB），Ring-LWE（环格）结构太强盛概这有潜伏数学缺点。Module-LWE 处于中央，既能利用多项式加快，又可以通过调解维度 \(k\) 机动调解安全品级。

Q: 验签公式里为什么是近似相称 \(Az - ct \approx w\)？

A: 由于 \(t\) 里包罗了噪声 \(e\)，验签时会有“低位偏差”。ML-DSA 的计划极其精妙，它利用 HighBits 和 LowBits 的分解技能，抛弃了大概有偏差的低位，只验证高位，从而实现了严格的精确性（Correctness）。

Q: 这个尺度有什么潜伏的缺点吗？

A: 重要是侧信道攻击。固然算法逻辑安全，但如果硬件实现时，署名的时间、功耗随私钥厘革，照旧会泄密。这是如今工程落地的研究热门。

七、陈诉与复现导向总结

1. 一页 PPT 焦点 Takeaway

FIPS 204 (ML-DSA) 是基于 Module-LWE 和 Module-SIS 的后量子署名尺度。
焦点机制：Fiat-Shamir 变更（将交互转为署名） + 拒绝采样（Rejection Sampling，消除私钥走漏，实现匀称分布）。
上风：速率极快，实现简朴（无高斯采样），是将来几十年纪字署名的“黄金尺度”。

2. 论文评价

不消做后续研究：指“不要试图去改动算法焦点结构”，尺度已定，乱改就是不安全。
值得做后续研究：指“基于该尺度的侧信道分析、硬件加快（FPGA/ASIC实现）以及在现有协议（如TLS）中的集成”。

3. 创新/改进方向Q&A

侧信道防御：研究怎样用掩码（Masking）技能掩护 Sign 过程中的 \(y\) 和 \(s\)，防止能量分析攻击。
故障注入分析：如果署名时被激光照了一下，跳过了“拒绝采样”查抄，会发生什么？怎样防御？
轻量化实现：在资源非常受限的物联网装备（如智能卡）上，怎样裁剪代码体积并保持安全？

严格对齐原文精读“1. Introduction”，“2. Glossary of Terms, Acronyms, and Symbols”，“3. Overview of the ML-DSA Signature Scheme”

本日我们要啃的是 FIPS 204 尺度文档的前三章。这份文档界说了 ML-DSA (Module-Lattice-Based Digital Signature Algorithm)，也就是台甫鼎鼎的 Dilithium 算法的官方尺度化版本。
如果说 ML-KEM (Kyber) 是用来“协商钥匙”的，那么 ML-DSA (Dilithium) 就是用来“盖章”的。在将来的互联网中，每一次身份认证、每一份数字证书、每一次软件更新，都离不开它。
Section 1. Introduction (弁言)

这一章重要回复：为什么我们必要一个新的署名尺度？
1. 逐行精读与直觉

原文："This standard specifies the Module-Lattice-Based Digital Signature Algorithm (ML-DSA)... a suite of algorithms that can be used to generate digital signatures..."

传授直觉：
数字署名就像是网络天下的“手写署名”和“公章”。
作用：

认证 (Authentication)：证实“是我发的”。
完备性 (Integrity)：证实“信没被改过”。
不可诡辩性 (Non-repudiation)：我签了字就不能赖账。

近况：如今我们用的署名（RSA, ECDSA）都是基于“大数分解”或“离散对数”困难。
危急：量子盘算机（Shor 算法）能秒解这些困难。一旦量子盘算机问世，现有的全部身份证、银行卡、网站证书都会刹时失效。
对策：ML-DSA 是 NIST 选定的“抗量子盾牌”。它基于格暗码（Lattice），量子盘算机也啃不动。

原文："ML-DSA is derived from the CRYSTALS-Dilithium digital signature scheme..."

配景：Dilithium 是 NIST 举行的环球 PQC 比赛的优胜者。FIPS 204 是它的“官方转正版”。以后政府和企业都要按这个文档来写代码。

2. 常见误解

误解 1：“ML-DSA 可以用来加密文件。”
改正：不可！ 它是署名算法（DSA），只负责“盖章”。加密要用 ML-KEM。署名 ≠ 加密。
误解 2：“ML-DSA 和 RSA 一样，公钥私钥可以交换。”
改正：不可以。在格暗码中，私钥（Signing Key）包罗的信息远多于公钥（Verification Key），且数学结构完全差别，绝对不能混用。

3. 整节总结

目的：提供一个抗量子的数字署名尺度。
泉源：源自 CRYSTALS-Dilithium。
职位：它是将来几十年的互联网信托基石。

Section 2. Glossary of Terms, Acronyms, and Symbols (术语与符号)

这一章是“游戏规则阐明书”。对于数学底子单薄的你来说，这里是重灾区，但也最关键。
1. 关键术语 (Terms)

Key Pair (密钥对)
Private key (signature key) and Public key (verification key).

直觉：
私钥 (sk)：你的“私章”。只有你有，藏在保险柜里，用来盖章。
公钥 (pk)：你的“印鉴卡”。贴在公告栏上，各人都可以拿来看，用来查对章是不是你盖的。

Security Strength (安全强度)
A number associated with the amount of work... required to break a cryptographic algorithm.

直觉：相当于防盗门的品级。ML-DSA 提供了三个品级（44, 65, 87），数字越大越难破。

2. 关键缩写 (Acronyms)

EUF-CMA (Existential Unforgeability under Chosen Message Attack)

寄义：选择消息攻击下的存在性不可伪造性。
传授直觉（金尺度）：
这是数字署名的最高安全尺度。
想象一个非常淘气的攻击者，他可以让你签任何文件（好比“我同意给攻击者1块钱”），乃至签一百万份。
EUF-CMA 的要求：纵然有了这一百万份署名，攻击者依然无法伪造一份新的、你没见过的文件署名（好比“我同意给攻击者1个亿”）。
ML-DSA 到达了这个尺度。

LWE / SIS / MLWE / MLSIS

直觉：这些是 ML-DSA 的数学地基。
LWE (Learning With Errors)：给你一堆带噪声的方程组，让你求未知数。——用于掩护公钥不走漏私钥。
SIS (Short Integer Solution)：给你一个宽矩阵，让你找一个短向量解。——用于防止伪造署名。
ML (Module Lattice)：表现这些标题是在“多项式向量”上界说的，比平凡整数矩阵更高效。

3. 数学符号 (Symbols) —— 焦点难点拆解

这里我们要创建“模格天下观”。

符号：\(q = 8380417\)
寄义：Modulus.

直觉：这是我们的“时钟刻度”。
为什么是 8380417？
它是一个质数。
\(q = 256 \times 32736 + 1\)。这意味着它满足 \(q \equiv 1 \pmod{256}\)。
作用：这个特别的性子允许我们在上面跑 NTT（快速傅里叶变更的亲戚），让多项式乘法快得飞起。

符号：\(R_q = \mathbb{Z}_q[X]/(X^{256} + 1)\)
寄义：Ring of polynomials.

传授直觉（焦点对象）：
想象一个长度为 256 的数组。
数组里的每个格子，都只能放一个 \(0\) 到 \(8380416\) 之间的整数。
这就是 ML-DSA 的根本粒子。全部的运算（加减乘）都是在操纵这种数组。
多项式乘法：两个数组相乘，不但仅是对应位相乘，而是“卷积”（像两个齿轮咬合转动）。

符号：\(\mathbf{v}\) (Bold lower case) 和 \(\mathbf{A}\) (Bold upper case)
寄义：Vector and Matrix over \(R_q\).

直觉（模格结构）：
\(\mathbf{v}\) (向量)：一竖排的 \(R_q\)。也就是一竖排的数组。这就是“Module”（模）的寄义。
\(\mathbf{A}\) (矩阵)：一个方阵，内里的每个元素都是一个 \(R_q\) 多项式。

符号：\(||\mathbf{w}||_\infty\)
寄义：Infinity norm. The maximum absolute value of coefficients.

直觉：“最大谁人数”。
如果 \(\mathbf{w}\) 是一堆多项式，我们把内里几千个系数全拿出来，看谁的绝对值最大。
作用：这是判断“署名是否合法”的尺子。如果系数太大（凌驾界限），阐明署名大概走漏了信息，必须取消重来。

符号：\(HintBit(r, z)\)
寄义：Helper function.

直觉：“四舍五入的提示”。
在署名验证时，由于有噪声，验证者算出来的数和署名者的数有一点点毛病。\(Hint\) 就像是一个标记：“嘿，这里刚才进位了，你也进一位”。

4. 整节总结

天下观：我们生存在 \(q=8380417\) 的多项式天下里。
工具：我们操纵的对象是多项式向量（Module Lattice）。
安全尺度：EUF-CMA（纵然你骗我签了一万次，你也造不出第一万零一次）。

Section 3. Overview of the ML-DSA Signature Scheme (方案概览)

这是全书的高潮。如果不看算法代码，光看这一章，你也能懂 ML-DSA 是怎么工作的。它基于著名的 Fiat-Shamir with Aborts 框架。
3.1 Digital Signatures (数字署名通用流程)

任何署名方案都分三步：

KeyGen：造公私钥。
Sign(sk, M)：用私钥给文件 M 盖章，得到署名 \(\sigma\)。
Verify(pk, M, \(\sigma\))：用公钥查抄 \(\sigma\) 是不是 M 的章。

3.2 The ML-DSA Scheme (ML-DSA 的焦点逻辑)

这一节通过笔墨形貌了 Dilithium 的灵魂。让我们把它翻译成人话。

焦点机制：Fiat-Shamir with Aborts

这是一个“本身给本身出题”的测验过程。
Step 1: 答应 (Commitment)

Signer (你)：先在家里偷偷选一个随机掩码向量 \(\mathbf{y}\)。
算出 \(\mathbf{w} = \mathbf{A}\mathbf{y}\)（这是对 \(\mathbf{y}\) 的答应）。
直觉：\(\mathbf{y}\) 是你的“暂时私钥”，\(\mathbf{w}\) 是“暂时公钥”。

Step 2: 挑衅 (Challenge)

Signer (你)：把要署名的消息 \(M\) 和刚才算出的 \(\mathbf{w}\) 一起扔进哈希函数。
\(c = H(M, \mathbf{w})\)。
直觉：哈希函数充当了“铁面无私的考官”。它根据你的答应和消息，吐出一道困难 \(c\)。由于哈希是随机的，你没法作弊。

Step 3: 相应 (Response)

Signer (你)：算出 \(\mathbf{z} = \mathbf{y} + c \cdot \mathbf{s}\)。
这里 \(\mathbf{s}\) 是你的长期私钥。
直觉：这就像高中数学题：已知 \(y, c, s\)，求 \(z\)。这构成了线性的关系。

Step 4: 拒绝采样 (Rejection Sampling) —— ✨ 焦点创新 ✨

标题：如果直接把 \(\mathbf{z}\) 发出去，攻击者收到许多个 \(\mathbf{z}, c\)，就能像解方程组一样反推出你的私钥 \(\mathbf{s}\)！由于 \(\mathbf{z}\) 的分布带有 \(\mathbf{s}\) 的形状。
办理：Signer 也是考核员。
算出 \(\mathbf{z}\) 后，你先本身看一眼：“这个 \(\mathbf{z}\) 的系数是不是太大了？是不是袒露了 \(\mathbf{s}\) 的特性？”
如果袒露了：取消！ (Abort)。回到 Step 1，重新选个 \(\mathbf{y}\)，重考。
如果没袒露（看起来像个完全的随机噪声）：通过！ 把 \((\mathbf{z}, c)\) 作为署名发出去。
结果：发出去的署名 \(\mathbf{z}\) 在数学上看起来是匀称分布的，跟私钥 \(\mathbf{s}\) 没有任何统计学上的关联。这就是为什么它能抗攻击。

Step 5: 验证 (Verify)

Verifier (各人)：收到 \((\mathbf{z}, c)\)。
固然不知道 \(\mathbf{y}\) 和 \(\mathbf{s}\)，但他知道公钥 \(\mathbf{t} \approx \mathbf{A}\mathbf{s}\)。
他算 \(\mathbf{A}\mathbf{z} - c\mathbf{t} = \mathbf{A}(\mathbf{y} + c\mathbf{s}) - c\mathbf{A}\mathbf{s} = \mathbf{A}\mathbf{y} = \mathbf{w}\)。
哇！他算出了答应 \(\mathbf{w}\)。然后他查抄 \(H(M, \mathbf{w})\) 是不是即是 \(c\)。如果即是，署名有效。

3.3 Requirements (实现要求)

Pre-hashing (预哈希)：
如果要签一个 1GB 的影戏，直接算太慢。
尺度允许先算影戏的指纹（Hash），再对指纹署名。这叫 HashML-DSA。
Randomness (随机性)：
署名过程必要随机数天生器 (RBG) 来选 \(\mathbf{y}\)。
如果 RNG 坏了（好比总是输出 0），私钥刹时走漏。
确定性署名：为了防这个，尺度保举用私钥和消息派生出 \(\mathbf{y}\)，如许就算没有真随机源也是安全的。

Q: 为什么 ML-DSA 要用“拒绝采样”？

A: 为了堵截署名 \(\mathbf{z}\) 和私钥 \(\mathbf{s}\) 的统计接洽。如果不拒绝，\(\mathbf{z}\) 的分布中央会偏移向 \(\mathbf{s}\)，攻击者可以通过统计匀称值还原私钥。拒绝采样强行把输出分布变成了与私钥无关的匀称分布。

Q: 这里的“模 (Module)”是什么意思？

A: 它是在“服从”和“安全性”之间的折中。纯 LWE（非结构化格）密钥太大；Ring-LWE（环格）结构太强盛概有数学隐患。Module-LWE 允许我们调解维度 \(k\)，既利用了多项式的盘算速率，又生存了类似矩阵的机动性。

Q: 验证方程里的近似相称是怎么回事？

A: 由于公钥 \(\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}\) 里包罗了噪声 \(\mathbf{e}\)。验证时 \(\mathbf{A}\mathbf{z} - c\mathbf{t}\) 实在即是 \(\mathbf{w} - c\mathbf{e}\)。以是验证者算出的 \(\mathbf{w}'\) 和署名者的 \(\mathbf{w}\) 差了一个 \(c\mathbf{e}\) 的低位偏差。ML-DSA 利用了 HighBits/LowBits 分解技能，抛弃低位，只验证高位，从而容忍了这个偏差。

七、陈诉与复现导向总结

1. 焦点 Takeaway (一句话总结)

FIPS 204 (ML-DSA) 是基于 Module-LWE 和 Module-SIS 困难标题的后量子数字署名尺度，它利用 Fiat-Shamir 变更 和 拒绝采样 技能，在包管抗量子安全性的同时，实现了极高的运算服从和易实现性。

2. 值得做后续研究吗？

算法本身：不值得改动（尺度已定）。
工程实现：非常值得。
侧信道分析：非常值得。

3. 创新方向

侧信道防御：研究 ML-DSA 在署名过程（特别是拒绝采样步调）中的功耗走漏。如果攻击者能区分“拒绝”和“担当”的功耗，是否能推断出私钥？
故障注入：如果攻击者在署名时用激光照射芯片，跳过了“拒绝采样”的查抄步调（强行输出不合格的署名），能否利用这些走漏的署名刹时还原私钥？
硬件加快：在 RISC-V 或 FPGA 上计划专用的 NTT 单元，加快 ML-DSA 的署名速率。

严格对齐原文精读“4. Parameter Sets”

如果说前三章是在教你“怎么造车”（算法原理），那么第 4 章就是给你看“车型设置单”（参数集）。
NIST（美国国家尺度与技能研究院）非常知心，并没有只给你一个数学公式让你本身瞎选参数（那样太伤害了），而是为你经心调试好了三款成品。在这一章，我们的使命就是读懂这份设置单，搞清晰这三款产物（ML-DSA-44, 65, 87）到底有什么区别，以及为什么这么计划。
这一章是工程落地的关键。选错了参数，你的体系大概要么慢得像蜗牛，要么脆得像薯片。
Section 4. Parameter Sets (参数集)

1. 逐行精读与直觉

我们先看 Table 1 ，这是全章的焦点。

参数定名：ML-DSA-44, ML-DSA-65, ML-DSA-87

直觉：这就像买衣服的尺码：S, M, L。
44 (Small/Standard)：对应 NIST 安全品级 2。
65 (Medium/High)：对应 NIST 安全品级 3。
87 (Large/Extreme)：对应 NIST 安全品级 5。
数字的寄义：
名字里的数字代表了矩阵 \(A\) 的维度 \((k, l)\)。
ML-DSA-44: \(k=4, l=4\)。
ML-DSA-65: \(k=6, l=5\)。
ML-DSA-87: \(k=8, l=7\)。
传授点评：维度越大，方程组越复杂，破解难度越高，但盘算量和密钥体积也越大。

固定参数 (Constants)
\(q = 8380417\)
a 512th root of unity...

直觉：这是“物理常数”，全部型号都一样。
\(q\) 是模数。它的巨细决定了我们数学天下的界限。
选这个特别的数是为了支持 NTT（快速数论变更）。如果改了这个数，整个加快引擎就废了。

焦点参数详解 (The Knobs)

\((k, l)\) - 维度

作用：决定了标题的规模。
直觉：解一个 4 元方程组难，照旧解一个 8 元方程组难？显然是 8 元。这是调治安全性的主旋钮。

\(\eta\) (Eta) - 私钥噪声范围

数值：2, 4, 2。
作用：私钥系数的取值范围（比方 \(\pm 2\) 或 \(\pm 4\)）。
直觉：这是私钥的“埋伏程度”。如果是 0，那就是没有噪声，一算就出来了。\(\eta\) 越大，私钥的空间越大，越难猜。但 ML-DSA-65 选了 4，而 87 选了 2，这是为了均衡安全性与拒绝采样的服从。

\(\tau\) (Tau) - 挑衅的汉明权重

数值：39, 49, 60。
作用：挑衅多项式 \(c\) 中 \(\pm 1\) 的个数。
直觉：这是验证者出的“考题难度”。
如果 \(\tau\) 太小（考题太简朴），攻击者容易蒙混过关（伪造署名）。
如果 \(\tau\) 太大（考题太难），连合法的署名者都很难算出一个合格的答卷（拒绝采样通过率变低，署名变慢）。

\(\gamma_1, \gamma_2\) - 掩码范围与舍入范围

作用：控制署名过程中随机掩码的巨细和抛弃低位的程度。
直觉：
\(\gamma_1\) (掩码巨细)：就像你是要在 100 平米的房间里藏针，照旧在 1000 平米的房间里藏针。范围越大，私钥藏得越好，但也导致署名结果（坐标）数字越大。
\(\gamma_2\) (低位截断)：为了压缩署名，我们要丢掉一些数据的“尾数”。这个参数决定了丢多少。

\(d\) - 公钥压缩位

数值：13。
直觉：公钥 \(t\) 原来很大，我们把每个系数的低 13 位直接砍掉，只发高位。这极大地减小了公钥尺寸。

安全品级 (Security Categories)

ML-DSA-44 (Category 2)：
对标：SHA-256 / AES-128。
寄义：破解它的难度 \(\ge\) 暴力破解 AES-128。这是如今的“基准线”，得当大多数贸易应用。
ML-DSA-65 (Category 3)：
对标：AES-192。
寄义：比基准更强。NIST 保举它作为通用尺度（既快又富足安全）。
ML-DSA-87 (Category 5)：
对标：AES-256。
寄义：军工级/绝密级。用于掩护国家秘密。代价是署名最大，速率最慢。

Table 2: 尺寸表 (Sizes)

这是一张“代价表”（代价）。
| 型号 | 私钥 (Bytes) | 公钥 (Bytes) | 署名 (Bytes) | 评价 |
| | | | | |
| 44 | 2560 | 1312 | 2420 | 最小巧，得当物联网 |
| 65 | 4032 | 1952 | 3309 | 性价比之选 |
| 87 | 4896 | 2592 | 4627 | 巨无霸，带宽斲丧大 |

传授直觉：
注意到了吗？署名的尺寸 (Signature Size) 宏大于传统算法（ECDSA 只有 64 字节）。这是格暗码的通病——“大胖子”。
ML-DSA-65 的署名有 3.3KB。如果你在计划一个极低带宽的卫星通讯协议，这大概是个标题。

2. 常见误解 (Common Misconceptions)

误解 1：“ML-DSA-44 不安全，由于它数字最小。”
改正：大错特错！ Category 2 (AES-128) 在可预见的将来都好坏常安全的。除非你有极其特别的超高安全需求（如核武器控制），否则 44 完全够用。不要盲目寻求大数字。
误解 2：“我可以本身修改参数，好比搞个 \(k=5\)。”
改正：绝对克制！ 暗码学尺度不是乐高积木。这些参数之间有着极其玄妙的数学制衡（好比拒绝采样率、安全性归约的紧致性）。你本身乱改一个参数，大概会导致整个安全性崩塌，大概署名死循环。只能在三款套餐里选，不能单点。
误解 3：“ML-DSA-87 比 44 慢许多。”
改正：在盘算速率上，实在差别没有那么大（通常在 2 倍以内）。重要的开销差别在于传输带宽（公钥和署名的巨细）。如果你的瓶颈是网络而不是 CPU，那么选 87 会很痛楚。

3. 整节总结 (Summary)

三大套餐：
ML-DSA-44：轻量级，对标 AES-128，得当资源受限情况。
ML-DSA-65：保举款，对标 AES-192，均衡了安全与性能。
ML-DSA-87：重装甲，对标 AES-256，用于极高安全场景。
焦点权衡：
通过调治矩阵维度 \((k, l)\) 来提拔安全性。
代价是通讯开销（公钥/署名变大）显着增长。
计划哲学：全部参数集共用同一个模数 \(q=8380417\) 和多项式环结构，这意味着同一套硬件/软件代码可以通过简朴的参数设置支持全部安全品级。这对于芯片计划非常友爱。

4. 猜测创新 (Innovation Outlook)

参数微调与侧信道：

研究差别参数集在侧信道攻击（Side-Channel Attacks）下的体现差别。好比，ML-DSA-87 的运算量大，会不会更容易走漏功耗特性？

更激进的压缩：

如今的参数集在署名巨细上照旧偏大（2.4KB - 4.6KB）。有没有大概通过改进数学结构（好比引入新的格结构），在保持安全性的条件下，把署名压缩到 1KB 以内？（这通常是顶级聚会会议的课题）。

顺应性实现：

在物联网装备上，怎样动态选择参数？大概计划一种机制，让拥有差别算力的装备协商利用差别的参数集？

严格对齐原文精读“5. External Functions”

如果说第 4 章是“选购指南”，那么 第 5 章：External Functions（外部函数） 就是教你“怎么开车”。
在这一章里，我们要界说用户直接调用的谁人接口（API）。
你会发现，这一章的函数（KeyGen, Sign, Verify）并没有包罗焦点的数学运算（好比矩阵乘法、拒绝采样），它们更像是一个“尽职尽责的管家”。它们负责：

找零钱（天生随机数）。
查抄证件（查抄输入长度是否合法）。
整理衣冠（把消息打包成特定格式）。
末了把准备好的东西交给“内务总管”（Internal Functions，第 6 章）行止理处罚。

这种“外包（Wrapper）”计划模式在工程上极其告急，由于它把“随机性处理处罚”和“确定性盘算”完满分离了，方便测试和验证。
5. External Functions (外部函数概览)

1. 逐行精读与直觉

原文："The signing, verifying, and key generation functions can be split into "external" and "internal" components..."

传授直觉：
External (外部)：面向用户的。负责脏活累活（天生随机数、报错、查抄长度）。
Internal (内部)：面向数学的。它是确定性的（Deterministic）。只要输入确定，输出就肯定确定。
为什么这么分？ 为了好做 CAVP 测试（暗码算法验证项目）。测试机构可以给 Internal 函数喂固定的随机数，看输出对不对。如果全混在一起，每次跑结果都不一样，测试职员会疯掉。

5.1 ML-DSA Key Generation (密钥天生)

这是 Alice 拿到的一键天生按钮。
1. 逐行精读与直觉

Algorithm 1 ML-DSA.KeyGen()

Line 1: \(\xi \leftarrow \mathbb{B}^{32}\)

直觉：这是整套体系的第一推动力。
\(\xi\) (Xi) 是一个 32 字节（256 bit）的种子。
\(\leftarrow\) 这个箭头表现“从随机数天生器（RBG）里抽样”。这必须是真随机大概暗码学安全伪随机。如果这一步被黑客猜测了，反面全部数学掩护都白搭。

Line 2-4: if \(\xi\) = NULL then return \(\perp\)

直觉：防呆计划。万一你的硬件随机数发生器（RNG）坏了，大概体系太忙没天生出来，绝对不能拿着全 0 大概空值去天生密钥。必须立刻报错（\(\perp\) 代表错误）。

Line 5: return ML-DSA.KeyGen_internal(\(\xi\))

直觉：只要种子 \(\xi\) 没标题，就把它扔给第 6 章的内部工厂 KeyGen_internal。工厂会用这颗种子“长”出公钥 \(pk\) 和私钥 \(sk\)。

5.2 ML-DSA Signing (署名)

这是 Bob 用私钥给文件盖章的过程。
1. 逐行精读与直觉

Algorithm 2 ML-DSA.Sign(sk, M, ctx)
Input: Private key \(sk\), message \(M\), context string \(ctx\).

Ctx (上下笔墨符串)：这是个新面貌。它的作用是防止跨域攻击。
好比你在“淘宝”签了一个名，你不渴望这个署名被拿到“京东”去用。你可以在 \(ctx\) 里写上 "Taobao" 或 "JD"。默认是空的。

Line 1-3: if \(|ctx| > [cite_start]255\) then return \(\perp\)

直觉：上下文不能太长，最长 255 字节。这是为了格式尺度化的限定。

Line 5: \(rnd \leftarrow \mathbb{B}^{32}\)

直觉（焦点点：Hedged vs Deterministic）：
这里天生了一个 32 字节的随机数 \(rnd\)。
Hedged (对冲模式 - 默认)：每次署名都天生新的 \(rnd\)。纵然私钥一样、消息一样，签出来的名也不一样。这能极大地防御侧信道攻击（Side-Channel Attack）。
Deterministic (确定性模式 - 可选)：如果你没有随机数天生器（好比在某些嵌入式芯片上），就把 \(rnd\) 设为全 0。这时署名是确定的（像 Ed25519 那样）。但 NIST 猛烈发起用 Hedged 模式。

Line 6-8: Check randomness failure

直觉：同上，随机数天生失败就报错。

Line 10: \(M' \leftarrow\) BytesToBits(IntegerToBytes(0, 1) || IntegerToBytes(ctx, 1) || ctx) || M

直觉（打包行李）：
在把消息 \(M\) 交给内部函数之前，我们要给它穿上一层“外衣”（Padding）。
IntegerToBytes(0, 1)：这个 0 是“域分离字节” (Domain Separator)。它告诉内部函数：“嘿，我是平凡署名，不是 Hash 署名哦”。（反面 HashML-DSA 这里会是 1）。
IntegerToBytes(ctx, 1) || ctx：把上下文长度和内容也拼进去。
目的：确保差别用途的署名（平凡 vs Hash，差别 ctx）天生的输入 \(M'\) 绝对差别，互不干扰。

Line 11: \(\sigma \leftarrow\) ML-DSA.Sign_internal(sk, \(M'\), rnd)

直觉：打包好的 \(M'\) 和随机数 \(rnd\) 交给内部函数去算数学题。

5.3 ML-DSA Verifying (验签)

这是任何人用公钥查抄署名真伪的过程。
1. 逐行精读与直觉

Algorithm 3 ML-DSA.Verify(pk, M, \(\sigma\), ctx)

Line 1-3: Check context length

直觉：验签时也要查抄上下文长度。

Line 5: \(M' \leftarrow\) BytesToBits(...)

直觉：验证者必须按完全雷同的方式把 \(M\) 打包成 \(M'\)。
如果署名者用了 \(ctx="Login"\)，验证者也必须用 \(ctx="Login"\)，否则拼出来的 \(M'\) 不一样，算出来的哈希就不一样，验签就会失败。

Line 6: return ML-DSA.Verify_internal(pk, \(M'\), \(\sigma\))

直觉：交给内部函数去算。注意，验签不必要随机数，它是完全确定性的。

5.4 Pre-Hash ML-DSA (预哈希版本)

这一节办理了“大文件署名”的标题。
1. 为什么必要 Pre-Hash？

场景：你要签一个 4GB 的 ISO 镜像文件。
直接签 (ML-DSA)：你必要把这 4GB 数据全部读进内存，拼接到 \(M'\) 里，然后塞给内部函数。这在只有 64KB 内存的智能卡上是不大概的。
预哈希签 (HashML-DSA)：
你先用 SHA-256 算出 4GB 文件的指纹（Hash），只有 32 字节。
然后你只对这 32 字节的指纹举行署名。
优点：无论文件多大，署名函数的输入永世很短。

2. HashML-DSA 的构造 (Algorithm 4 & 5)

Algorithm 4 HashML-DSA.Sign(sk, M, ctx, PH)
Input: PH (Pre-Hash Function, e.g., SHA-256).

Line 11-22 (Switch PH)

直觉（贴标签）：
不但要算哈希，还要记下“你是用什么算法算的”。
OID (Object Identifier)：这是一串身份证号，用来标记哈希算法。
SHA-256 的 OID 是 2.16.840.1.101.3.4.2.1。
SHA-512 的 OID 是 2.16.840.1.101.3.4.2.3。
\(PH_M \leftarrow PH(M)\)：算出大文件的哈希值。

Line 23: \(M' \leftarrow\) ... IntegerToBytes(1, 1) ... || OID || \(PH_M\)

直觉（关键差别）：
注意开头的谁人 1！
平凡署名这里是 0。Hash 署名这里是 1。
Domain Separation (域分离)：这包管了纵然你签的消息 \(M\) 刚好即是某个文件的哈希值，平凡署名的结果和 Hash 署名的结果也绝对不一样。攻击者无法肴杂这两种模式。
OID 的作用：防止“算法更换攻击”。如果只签哈希值，攻击者大概找另一个弱哈希算法天生碰撞。把 OID 签进去，就锁定了必须用 SHA-256。

常见误解 (Common Misconceptions)

误解：“HashML-DSA 就是先做 SHA-256，然后调 ML-DSA.Sign。”

改正：错！如果你只是本身在外貌做一次 SHA-256，然后调平凡 Sign，那你是在做 ML-DSA.Sign(Hash(M))，这时间域分离字节是 0。
而 HashML-DSA.Sign 会把域分离字节设为 1，而且会拼入 OID。这两者天生的署名是不通用的。必须严格调用对应的 API。

误解：“Context string (\(ctx\)) 是为了增长随机性。”

改正：不是。随机性由 \(rnd\) 负责。\(ctx\) 是为了业务逻辑隔离（Domain Separation）。好比“登录署名”和“交易业务署名”可以用差别的 \(ctx\) 防止混用。

误解：“验证署名时不必要 \(ctx\)。”

改正：必须必要。署名时用了什么 \(ctx\)，验签时必须提供千篇同等的 \(ctx\)，否则验不外。

整节总结 (Section Summary)

分层架构：FIPS 204 接纳了“外部包装 + 内部逻辑”的分层计划。

External：处理处罚随机数、输入查抄、格式拼接（Padding）。
Internal：处理处罚纯数学运算。

两种模式：

ML-DSA (Pure)：直接签消息。得当短消息。域分离字节为 0。
HashML-DSA (Pre-hash)：先哈希再签。得当大文件或受限硬件。域分离字节为 1，且包罗 OID。

随机性：默认利用 Hedged 模式（私钥+随机数），防止侧信道攻击。
安全性：通过严格的格式拼接（Prefixing）和域分离，防止了差别模式、差别哈希算法之间的肴杂攻击。

猜测创新 (Future Innovation)

上下文的尺度化管理：

如今的 \(ctx\) 是由应用层任意填的。有没有大概计划一套结构化的 Context 尺度，让它能携带更多语义（好比时间戳、逾期时间），从而把这些逻辑从应用层下沉到署名层？

更高效的 Pre-hash 方案：

如今的 HashML-DSA 必须把 OID 硬编码进去。对于新兴的哈希算法（好比 SHA-3 变体），能否计划一种更通用的编码方式，而不必要每次都改尺度？

硬件卸载 (Offloading)：

External Functions 里的数据拼接（Padding）和 OID 注入涉及大量的内存拷贝。在超高速网络卡（NIC）上实现 ML-DSA 时，怎样计划电路让这些拼接操纵零拷贝（Zero-copy）完成？

严格对齐原文精读“6. Internal Functions”

如果说第 5 章是“怎么开车”（API 接口），那么 第 6 章：Internal Functions（内部函数） 就是带你钻进车底，看“引擎是怎么转的”。
这一章是整本尺度文档的心脏。全部的暗码学邪术——格的构造、拒绝采样循环、Hint 的天生与利用——全都在这里。
对于做学术研究大概底层实现的工程师来说，这一章必须逐行死磕。
6. Internal Functions (内部函数概览)

原文："The signing, verifying, and key generation functions can be split into "external" and "internal" components..."

传授直觉：
这里界说的函数（KeyGen_internal, Sign_internal, Verify_internal）是确定性的大概纯数学的。
它们不负责从操纵体系申请随机数（那是外部函数的事），它们只负责拿着给定的质料（随机种子）做菜。
这种计划是为了可测试性（Testability）。如果我也能给你同样的种子，我就能复现你天生的密钥，这对调试代码至关告急。

6.1 ML-DSA Key Generation (Internal) - 造锁的焦点

这一节陈诉怎样从一颗种子，变出一把公钥和一把私钥。
1. 逐行精读与直觉

Algorithm 6 ML-DSA.KeyGen_internal(\(\xi\))
Input: \(\xi \in \mathbb{B}^{32}\) (32字节种子)

Line 1: \((\rho, \rho', K) \leftarrow H(\xi || \dots)\)

直觉（一生三）：
把输入的种子 \(\xi\) 扔进哈希函数（XOF），扩展出三个新的随机数：

\(\rho\) (Rho)：公钥的种子。用来天生谁人巨大的矩阵 \(A\)。它是公开的。
\(\rho'\) (Rho Prime)：私钥的种子。用来天生秘密向量 \(s_1, s_2\)。绝密！
\(K\)：署名用的种子。以后署名时会用到它来派生随机数。绝密！

Line 3: \(\hat{A} \leftarrow \text{ExpandA}(\rho)\)

直觉（无中生有）：
还记得矩阵 \(A\) 吗？它是一个巨大的多项式矩阵（好比 \(6 \times 5\)）。如果直接存，得好几 KB。
ExpandA 就像《我的天下》里的舆图天生器。只要给它种子 \(\rho\)，它就能在全部人的电脑上及时天生出千篇同等的矩阵 \(A\)。
\(\hat{A}\)：谁人小帽子 \(\hat{}\) 表现这个矩阵是在 NTT 域（频域）天生的。这为了反面乘法算得快。

Line 4: \((s_1, s_2) \leftarrow \text{ExpandS}(\rho')\)

直觉（制造私钥）：
用 \(\rho'\) 天生两个秘密向量 \(s_1\) 和 \(s_2\)。
它们的系数都很小（好比 \(\pm 2\) 或 \(\pm 4\)），符合小系数分布。这就是我们的私钥本体。

Line 5: \(t \leftarrow \text{NTT}^{-1}(\hat{A} \circ \text{NTT}(s_1)) + s_2\)

焦点公式：\(t = A s_1 + s_2\)
直觉（LWE 困难）：
这就是著名的 Module-LWE 方程。
\(t\) 是公钥。\(A\) 是公开矩阵。\(s_1, s_2\) 是私钥（也是噪声）。
攻击者看到 \(t\) 和 \(A\)，想求 \(s_1\)，就像在满是噪声的无线电信号里还原原始语音，极难。

Line 6: \((t_1, t_0) \leftarrow \text{Power2Round}(t)\)

直觉（公钥压缩）：
算出来的 \(t\) 每个系数大概是 13-bit 或 23-bit（取决于 \(q\)）。
我们不必要把完备的 \(t\) 发给别人。我们把它拆分：
\(t_1\) (High Bits)：高位。作为公钥发布。
\(t_0\) (Low Bits)：低位。作为私钥的一部门存起来（署名时有效）。
这就像我告诉你“如今约莫是 12 点”，而不说“12 点 05 分 32 秒”。省空间。

Line 8-10: Encode and Pack

直觉：把天生好的东西打包成字节串 \(pk\) 和 \(sk\)。

6.2 ML-DSA Signing (Internal) - 署名的灵魂

这是整个算法最复杂、最精妙的部门：拒绝采样循环 (Rejection Sampling Loop)。
1. 逐行精读与直觉

Algorithm 7 ML-DSA.Sign_internal(sk, M', rnd)

Line 1-5: Decode sk and Expand A

直觉：把私钥解包，把矩阵 \(A\) 重新天生出来。

Line 6: \(\mu \leftarrow H(tr || M', 64)\)

直觉：把消息 \(M'\) 转化成一个固定长度的指纹 \(\mu\)。

Line 10: while \((z, h) = \perp\) do

直觉（死循环的开始）：
这就是“拒绝采样”。
署名就像是在“探索”。我们实行天生一个署名，如果不合格（大概走漏私钥），就丢掉重来（Rejection），直到天生一个完满的署名为止。

Line 11: \(y \leftarrow \text{ExpandMask}(\rho'', \kappa)\)

直觉（随机掩码）：
天生一个暂时的随机向量 \(y\)。它的系数在 \((-\gamma_1, \gamma_1)\) 之间。
\(y\) 的作用是掩护私钥 \(s_1\)。

Line 12-13: \(w \leftarrow A y\), \(w_1 \leftarrow \text{HighBits}(w)\)

直觉（答应）：
算出 \(w = Ay\)。这叫“答应”。
\(w_1\) 是 \(w\) 的高位。我们只把高位拿去天生挑衅，防止 \(w\) 的微小扰动改变挑衅。

Line 15: \(\tilde{c} \leftarrow H(\mu || w_1, \dots)\)

直觉（自出题）：
用消息 \(\mu\) 和 答应 \(w_1\) 一起哈希，天生一个“挑衅” \(\tilde{c}\)。
这就相当于：我向天发誓（答应），针对这件事（消息），我担当挑衅。

Line 16: \(c \leftarrow \text{SampleInBall}(\tilde{c})\)

直觉：把哈希值 \(\tilde{c}\) 变成一个希罕的多项式 \(c\)（只有 \(\pm 1\) 和 \(0\)）。这就是谁人用来乘私钥的小系数多项式。

Line 20: \(z \leftarrow y + c s_1\)

直觉（焦点相应公式）：
这就是最经典的署名公式（Schnorr 情势）。
\(z\) (署名) = \(y\) (随机掩码) + \(c\) (挑衅) \(\times\) \(s_1\) (私钥)。
如果没有拒绝采样，攻击者网络许多组 \((z, c)\)，算个匀称值，\(y\) 被抵消，直接算出 \(s_1\)。

Line 21: \(r_0 \leftarrow \text{LowBits}(w - c s_2)\)

直觉：这是为了反面算 Hint 做准备。盘算低位部门的偏差。

Line 23: if \(||z||_\infty \ge \gamma_1 - \beta\) or ... then continue

直觉（安检门 1：防止走漏巨细）：
\(z = y + c s_1\)。如果 \(c s_1\) 很大，那么 \(z\) 也会变大。
如果 \(z\) 超出了 \(y\)原来的范围（\(\gamma_1\)），那攻击者一看：“嚯，这数这么大，肯定是你私钥 \(s_1\) 把它顶出来的”。
对策：如果 \(z\) 太大，立刻烧毁，重来！ 我们只发布那些看起来和 \(y\) 一样“平凡”的 \(z\)。

Line 26: \(h \leftarrow \text{MakeHint}(\dots)\)

直觉（Hint 的邪术）：
验证者手里只有压缩过的公钥 \(t_1\)（丢了低位 \(t_0\)）。
他在验证时算出的 \(w'\) 会和署名者算出的 \(w\) 有一点点毛病。
Hint (\(h\)) 就是一串“提示位”，告诉验证者：“兄弟，这几个位置刚才进位了，你本技艺动修正一下”。
没有这个 Hint，验证者算出的 \(w'\) 的高位大概和署名者的 \(w_1\) 对不上。

Line 28: if Hint is too big ... then continue

直觉（安检门 2：防止走漏形状）：
如果 Hint 里的 1 太多（阐明进位太多，也就是偏差太大），这也会走漏私钥的信息，大概导致署名太长放不下。
对策：Hint 太多，烧毁，重来！

Line 33: Encode signature

直觉：好不容易闯过两道安检，终于得到了安全的 \(z\) 和 \(h\)，打包输出。

6.3 ML-DSA Verifying (Internal) - 验签的原形

验证者要把公钥和署名联合，看看能不能还原出挑衅 \(c\)。
1. 逐行精读与直觉

Algorithm 8 ML-DSA.Verify_internal(pk, M', \(\sigma\))

Line 9: \(w'_{Approx} \leftarrow A z - c t_1 \cdot 2^d\)

直觉（还原现场）：
验证者想算 \(w = A y\)。
但他不知道 \(y\)，他只知道 \(z = y + c s_1\)。
以是他算：\(A z - c t \approx A(y + c s_1) - c(A s_1) = A y = w\)。
但他还没有完备的 \(t\)，只有高位 \(t_1\)。以是算出来的是一个近似值 \(w'_{Approx}\)。

Line 10: \(w'_1 \leftarrow \text{UseHint}(h, w'_{Approx})\)

直觉（修正偏差）：
利用署名里带的 Hint (\(h\))，把谁人“近似值” \(w'_{Approx}\) 的高位修正成精确的 \(w'_1\)。
这就像你算出来是 11.9，Hint 告诉你“进一位”，你就把它修正成 12.0（对应的高位）。

Line 12: \(\tilde{c}' \leftarrow H(\mu || w'_1, \dots)\)

直觉（重算挑衅）：
用修正后的 \(w'_1\) 和消息 \(\mu\)，本身重新算一遍哈希值 \(\tilde{c}'\)。

Line 13: return \([[ ||z||_\infty < \gamma_1 - \beta ]]\) and \([[ \tilde{c} = \tilde{c}' ]]\)

直觉（终极审判）：
条件 1：署名 \(z\) 必须富足短（防止伪造）。
条件 2：我算出来的挑衅 \(\tilde{c}'\) 必须和署名里带的 \(\tilde{c}\) 千篇同等。
如果都满足，阐明署名是真的。

常见误解 (Common Misconceptions)

误解：“拒绝采样只是为了让署名变小。”

改正：不！它是为了安全性。如果不拒绝那些“特别”的署名，私钥 \(s_1\) 的统计特性就会走漏。拒绝是为了堵截 \(z\) 和 \(s_1\) 的统计接洽。

误解：“Hint 是私钥的一部门，不能给人看。”

改正：Hint 是公开的，它包罗在署名里。它走漏的信息少少（只走漏了哪些位置发生了进位），在安全证实里是可控的。

误解：“\(w'_{Approx}\) 和 \(w\) 是一样的。”

改正：不一样。它们之间差了一个 \(c t_0\)（公钥低位带来的偏差）和一个 \(c s_2\)。\(UseHint\) 的作用就是消除这些偏差对“高位提取”的影响。

整节总结 (Section Summary)

KeyGen：基于 Module-LWE。焦点是天生 \(t = A s_1 + s_2\)，并把 \(t\) 拆分为高位 \(t_1\)（公钥）和低位 \(t_0\)（私钥）。
Sign：

构造：Fiat-Shamir 变更。
焦点：拒绝采样。不绝实行随机掩码 \(y\)，直到天生的署名 \(z\) 和 Hint \(h\) 既安全又短小。

Verify：

焦点：利用公钥和署名还原答应 \(w\)。
关键点：利用 Hint 机制消除由于公钥压缩带来的舍入偏差。

猜测创新 (Innovation Outlook)

更快的拒绝采样：

如今的循环匀称要跑 4-5 次才气乐成一次。有没有办法通过改进分布或参数，让它匀称 1.1 次就乐成？这能极大提拔署名速率。

无 Hint 的署名：

Hint 机制增长了复杂度和署名巨细。有没有大概计划一种不必要 Hint 的格署名方案（好比 Falcon，但 Falcon 必要高斯采样，很难实现）？大概改进数学结构让偏差天然消除？

针对 Hint 的侧信道：

UseHint 和 MakeHint 涉及条件分支。在某些硬件上，这是否会走漏信息？这是一个非常渺小但前沿的攻击面。

严格对齐原文精读“7. Auxiliary Functions”

如果说第 6 章是“引擎焦点”，那么 第 7 章：Auxiliary Functions（辅助函数） 就是我们的“超等工具箱”。
这一章也是全书最长、最噜苏的一章，包罗了从 Algorithm 9 到 Algorithm 49 共 41 个函数！别被这个数量吓到。这些函数并不是复杂的暗码学逻辑，它们大多是“搬运工”和“翻译官”。
它们负责：

数据转换：把数字变成字节，把字节变成数字。
打包压缩：把疏松的数据挤在一起省空间。
采样：从随机流里变出多项式。
数学运算：谁人神奇的 NTT（快速乘法）就在这里。

对于做工程实现的同砚，这一章是查阅频率最高的字典。对于做理论的同砚，你必要重点明白 Hint（提示位） 和 NTT 的直觉。
我们把这 41 个函数分成 6 个工具包来讲授。
7.1 Conversion Between Data Types (数据范例转换)

这是最底子的“翻译”工作。我们要在“数学天下”（\(0 \sim q-1\) 的整数）和“盘算机天下”（0101 的字节省）之间往返切换。
1. 底子转换 (Alg 9 - 13)

IntegerToBits / BitsToInteger: 整数 \(\leftrightarrow\) 比特串。
IntegerToBytes / BitsToBytes: 整数/比特串 \(\leftrightarrow\) 字节串。
直觉：
这就是你在 C 语言里写的 memcpy 大概位移操纵。
关键点：FIPS 204 欺压利用 Little-Endian（小端序）。即低位字节在前。这跟人类的阅读风俗相反，写代码时极容易搞反。

2. 采样转换 (Alg 14 - 15)

Algorithm 14 CoeffFromThreeBytes(b0, b1, b2)

目的：把 3 个字节（24 bits）变成一个模 \(q\) 的整数（\(q \approx 2^{23}\)）。
直觉（拒绝采样）：
3 个字节能表现 \(0 \sim 2^{24}-1\) (16,777,215)。
我们的 \(q = 8,380,417\)。
怎么映射？简朴，如果算出来的数 \(< q\)，就担当；如果 \(\ge q\)，就扬弃（返回 \(\perp\)）。
这里的 \(b_2\) 还要把最高位抹成 0（由于我们只必要 23 bits），这叫 b2'.

Algorithm 15 CoeffFromHalfByte(b)

目的：把半个字节（4 bits, \(0 \sim 15\)）变成一个小系数（如 \(-2 \sim 2\)）。
直觉：
同样是拒绝采样。如果 \(b\) 映射出的数在合法范围内（好比 \(\eta=2\) 时是 \(-2 \dots 2\)），就担当；否则扬弃。

3. 比特打包 (Alg 16 - 19)

SimpleBitPack / BitPack:
直觉：“挤牙膏”。如果一个数只必要 3 bits，而你用一个 8-bit 的字节存它，就浪费了 5 bits。Pack 函数把这些小整数紧凑地排在一起，不留缝隙。
Simple 版用于 \(t_1\)（范围从 0 开始）。
平凡版用于 \(s_1, s_2\)（范围是负数到正数，好比 \(-\eta \sim \eta\)）。它会先做一个偏移 \(b - w_i\) 把负数变成正数再打包。

4. Hint 打包 (Alg 20 - 21)

Algorithm 20 HintBitPack(h)

配景：Hint 向量 \(h\) 是一个极其希罕的向量（大部门是 0，少少数是 1）。
直觉（希罕压缩）：
如果直接存 0101，太浪费。
我们只存 “1 在哪儿”（索引值）。
好比 00100010，我们就存 [2, 6]。
\(y\) 的前 \(\omega\) 个字节存索引，后 \(k\) 个字节存“每一行有几个 1”。

7.2 Encodings of Keys and Signatures (密钥与署名的编码)

这部门是把上面打包好的零件组装成终极的成品（字节串）。
1. 公钥与私钥 (Alg 22 - 25)

pkEncode: 把种子 \(\rho\) 和打包好的 \(t_1\) 拼起来 \(\rightarrow\) 公钥 \(pk\)。
skEncode: 把 \(\rho, K, tr\) 和打包好的 \(s_1, s_2, t_0\) 拼起来 \(\rightarrow\) 私钥 \(sk\)。
直觉：这就是序列化（Serialization）。

2. 署名 (Alg 26 - 27)

sigEncode: 把挑衅哈希 \(\tilde{c}\)、相应 \(z\)、提示 \(h\) 拼起来 \(\rightarrow\) 署名 \(\sigma\)。
直觉：注意，这里的 \(z\) 利用 BitPack 压缩的，由于 \(z\) 的系数范围是已知的 \((-\gamma_1+1, \gamma_1)\)。

7.3 Pseudorandom Sampling (伪随机采样)

这是造物主的工具包。怎样从一串随机种子，变出各种形态的多项式。
1. SampleInBall (Alg 29)

目的：天生挑衅多项式 \(c\)。它必须非常希罕，只有 \(\tau\) 个非零系数（\(\pm 1\)）。

直觉（洗牌算法）：
这是一个 Fisher-Yates 洗牌的变体。
天赋生 256 个位置的列表。
像发牌一样，随机选 \(\tau\) 个位置，把它们标记为 \(\pm 1\)（符号也是随机的）。
剩下的位置满是 0。

2. RejNTTPoly (Alg 30)

目的：天生矩阵 \(A\) 里的多项式。

<ul>直觉：
调用 CoeffFromThreeBytes。
也就是从随机流里每次抓 3 个字节，看看能不能构成一个 \(

Module-Lattice-Based Digital Signature Standard

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

张春