CRYSTALS-Dilithium：A Lattice-Based Digital Signature Scheme

眸胝 · 4 天前

如果说 Kyber 是后量子时代的“信使”（负责传钥匙），那么 Dilithium 就是后量子时代的“公章”（负责数字签名）。在 NIST 的后量子密码标准化进程中，它也是最终获胜的签名标准之一（即 FIPS 204 / ML-DSA）。
【论文基本信息】

论文标题：CRYSTALS-Dilithium: Digital Signatures from Module Lattices
作者：Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, Damien Stehlé
来源：TCHES 2018 (IACR Transactions on Cryptographic Hardware and Embedded Systems) / NIST PQC Submission

一、整体导航

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

解决什么问题：我们需要一个抗量子攻击的数字签名方案。以前的格签名（如 BLISS）虽然快，但用了高斯采样（Gaussian Sampling），不仅难实现，还容易遭受侧信道攻击（容易泄密）。Dilithium 就是为了解决这个问题而生的。
江湖地位：它是“基于模格的 Fiat-Shamir 签名”的集大成者。它在安全性、速度、实现难度之间取得了完美的平衡，现在已经是 NIST 的ML-DSA 标准。
新在哪里：
彻底抛弃高斯采样：改用简单的均匀采样（Uniform Sampling），通过巧妙的拒绝采样策略保证安全。这让它非常容易在硬件和软件上安全实现（Constant-time）。
模格（Module Lattice）：和 Kyber 一样，使用了模格结构，兼顾了 Ring-LWE 的效率和 Standard-LWE 的灵活性。
极致压缩：通过一种叫做“高低位分解 + Hint”的技术，把公钥和签名压缩得非常小。

2. 文字版路线图

1. Introduction：【略读】。了解它为什么比 BLISS 和 Falcon 好（更易实现，无高斯采样）。
2. Preliminaries：【必须死磕】。定义了模格、Module-LWE、Module-SIS。这些是安全根基。
3. The Dilithium Scheme：【核心中的核心】。这节详细讲了如何构造签名。特别是“拒绝采样”的逻辑和“Hint”机制，这是 Dilithium 的灵魂。
4. Implementation & Performance：【选读】。如果你做工程，看它如何用 NTT 加速；做理论的可以略过。
5. Security Analysis：【重点】。分析了它为什么是安全的（LWE + SIS）。

二、核心数学与概念拆解（零基础直觉版）

1. Module-LWE 和 Module-SIS

角色：Dilithium 的两条腿。缺一条就走不动。
Module-LWE (Learning With Errors)：
干什么用的：保护公钥的安全性。
直觉：给你 $A$ 和 $t = As + e$，你算不出私钥 $s$。这就保证了就算你把公钥 $t$ 贴满大街，私钥也是安全的。
Module-SIS (Short Integer Solution)：
干什么用的：保护签名不被伪造。
直觉：给你一个很宽的矩阵 $A$，让你找一个短向量 $z$ 使得 $Az = 0$（或者某个特定值）。在格上找“短”向量极难。如果攻击者能伪造签名，等同于他解出了 SIS 问题。

2. Fiat-Shamir with Aborts (带中止的 Fiat-Shamir)

干什么用的：把一个“交互式身份认证协议”变成“非交互式数字签名”。
直觉流程：

承诺：我心里想个随机数 $y$，告诉你 $w = Ay$。
挑战：你给我出一道题 $c$（在签名里，这个 $c$ 是由消息的哈希生成的）。
响应：我算出 $z = y + cs$ 给你看。

Problem：$z = y + cs$ 可能会泄露私钥 $s$ 的信息！比如 $s$ 是 100，我发出去的 $z$ 总是偏向 100。
Aborts (中止/拒绝)：为了不泄露 $s$，我算出 $z$ 后先自己看一眼。如果 $z$ 的分布看起来“不像”一个纯随机数（比如太大或太小），我就作废这次签名，换个 $y$ 重来。直到生成的 $z$ 看起来跟 $s$ 毫无关系。

3. Uniform Sampling vs. Gaussian Sampling

历史包袱：以前的算法（BLISS）要求 $y$ 和 $z$ 服从高斯分布（正态分布）。这在电脑上很难画准，画不准就会泄密。
Dilithium 的创新：我们只用均匀分布（就是扔骰子，每个面概率一样）。
怎么做到的？通过精心设计的拒绝采样参数，让输出的签名 $z$ 也是均匀分布的。
好处：写代码极其简单，不容易被黑客通过统计电量/时间（侧信道）偷走私钥。

4. "High Bits" and "Low Bits" (高低位分解)

干什么用的：压缩公钥和签名大小。
直觉：
假设公钥里的一个数是 12345。
我只发给你“高位” 12300。省了空间。
但验签的时候，这点误差（45）会导致校验失败。
MakeHint：我在签名里附带一个极小的“提示 (Hint)”，告诉你“哎，刚才这里进位了，你自己修一下”。
这样既省了空间，又保证了正确性。这是 Dilithium 最精妙也最难懂的地方。

三、关键定理 / 构造解释

1. Identification Scheme to Signature

人话结论：Dilithium 本质上是一个“证明我知道私钥 $s$”的零知识证明，通过哈希函数变成了签名。
核心思想：
私钥是 $s$。
签名是 $(z, c)$，满足 $Az - ct \approx w$。
验证者算出 $w' = Az - ct$，然后检查 $c$ 是否等于 $H(M, w')$。
这里的 $\approx$ 是因为公钥 $t$ 有噪声，且经过了压缩。

2. LWE + SIS Hardness

人话结论：想伪造签名？你要么能解开 LWE，要么能解开 SIS。
证明逻辑：
Key Recovery (偷私钥)：等同于解 Module-LWE。
Forgery (伪造)：如果你能造出一个合法的 $(z, c)$，意味着你在不知道 $s$ 的情况下找到了满足方程的短向量，这等同于解 Module-SIS（找短向量冲突）。

3. Correctness with Hints

人话结论：就算公钥和中间变量被压缩（扔掉了低位），靠着 Hint 也能 100% 验证成功。
构造思想：
验证者计算 $Az - ct$ 时，其实是在重构承诺 $w$。
由于 $t$ 只有高位，算出来的 $w$ 也是近似的。
Hint 的作用就是告诉验证者：在把近似的 $w$ 恢复成高位 $w_1$ 时，哪些系数需要 $+1$ 或 $-1$ 修正。

四、方案流程“白板级解释”

这是 PPT 的核心页（Step 1, 2, 3）。
Step 1: KeyGen (生成钥匙)

生成随机矩阵 $A$（用种子 $\rho$）。
生成私钥向量 $s_1, s_2$（系数很小，比如 -2 到 2）。
计算 $t = As_1 + s_2$。
压缩：把 $t$ 的低位扔掉，只留高位 $t_1$。
公钥：$(A, t_1)$。私钥：$(s_1, s_2, t_0)$。

Step 2: Sign (签名) —— 最容易出问题的一步

随机尝试：选一个随机掩码向量 $y$（系数稍大）。
承诺：算 $w = Ay$。取其高位 $w_1$。
挑战：$c = H(M, w_1)$。把消息 $M$ 和 $w_1$ 绑在一起哈希。
计算：$z = y + cs_1$。
拒绝采样 (The Check)：

检查 1：$z$ 的系数是不是太大了？（如果太大，可能泄露 $s_1$ 的大小）。
检查 2：低位运算会不会导致进位错误？
如果检查不通过：作废！回到第1步重来（这就是 Rejection）。

Hint：计算 Hint $h$，用来辅助验证者恢复 $w_1$。
输出：签名 $\sigma = (z, h, c)$。（注：实际标准中 $c$ 可以从其他推导，通常存 $\tilde{c}$）。

Step 3: Verify (验签)

重构：利用公钥 $t_1$ 和签名 $z$，计算 $w' \approx Az - ct_1 \cdot 2^d$。
修正：利用 Hint $h$ 和 $w'$，恢复出准确的高位 $w_1$。
哈希：计算 $c' = H(M, w_1)$。
对比：如果 $c' == c$ 且 $z$ 的大小符合要求，通过。

创新点：

拒绝采样消除了高斯采样。
Hint 机制允许极高比例的公钥压缩。

五、安全性与参数分析

基于什么问题：

机密性基于 Module-LWE。
不可伪造性基于 Module-SIS（Self-Targeting MSIS）。

攻击模型：

考虑了量子计算下的 Grover 搜索和格规约攻击。
EUF-CMA（选择消息攻击下的存在性不可伪造）。

参数防 BKZ：

核心参数是格维度 $k$（比如 4x4, 6x6, 8x8）。
选取的参数使得 BKZ 算法需要的 Blocksize 极大（> 600），导致计算复杂度超过 $2^{128}$ 或更高。

短板：

如果 $k$ 选小了，Shortest Vector Problem (SVP) 会变得容易，攻击者能直接从公钥算出私钥。

六、与相关工作的对比

1. 对比经典工作

Vs. RSA/ECC：
优势：抗量子！
代价：签名大（2KB vs 64Bytes），公钥大。
Vs. Falcon (另一主要格签名)：
优势：Dilithium 实现简单，全是整数加减乘，硬件友好。Falcon 需要浮点数高斯采样，极难在硬件上安全实现。
代价：Dilithium 签名比 Falcon 大（Falcon 是格签名里最小的）。
Vs. SPHINCS+ (哈希签名)：
优势：Dilithium 速度快几个数量级，签名也小得多（SPHINCS+ 签名有几十 KB）。
代价：安全性依赖格假设，SPHINCS+ 只依赖哈希（更保守）。

2. 导师可能问的 5 个问题

Q: 为什么 Dilithium 不需要高斯采样？

A: 因为它使用了拒绝采样技术，强制丢弃掉边缘分布，使得输出的签名 $z$ 服从均匀分布，切断了与私钥的统计联系。

Q: Hint 到底是干嘛的？

A: 用来处理公钥压缩带来的舍入误差。它告诉验证者如何修正计算出的近似值，以恢复准确的高位信息。

Q: 拒绝采样会导致死循环吗？

A: 理论上概率不为0，但在工程参数下，平均尝试 4-7 次就能成功，概率极低。

Q: Module-LWE 比 Ring-LWE 好在哪？

A: 灵活性。调整安全性只需要改变维数 $k$，不需要重新设计多项式环和 NTT 算法。

Q: Dilithium 抗侧信道攻击吗？

A: 它的设计本身是 Constant-time 的（无高斯采样），比 BLISS 好防得多。但硬件实现时仍需注意拒绝采样过程的功耗泄露。

七、汇报与复现导向总结

1. 核心 Takeaway (PPT 一页纸)

Dilithium (ML-DSA) 是 NIST 标准化的后量子签名方案。
核心机制：Fiat-Shamir with Aborts + Module-LWE/SIS。
工程亮点：
无高斯采样：实现简单，防侧信道。
Hint 压缩：极致减小公钥/签名尺寸。
NTT 加速：软件运行速度极快。
结论：它是目前最均衡、最适合大规模部署的后量子签名。

2. 值得做后续研究吗？

算法本身：已标准化，魔改空间不大。
值得做的方向：
侧信道分析：在嵌入式设备上，拒绝采样循环的功耗特征是否会泄露信息？
故障注入：如果跳过验签步骤或拒绝采样步骤会怎样？
硬件加速：RISC-V / FPGA 上的高效实现。

严格对齐原文精读“ Abstract”，“1 Introduction”

如果说 Kyber 是后量子时代的“信使”（负责传钥匙），那么 Dilithium 就是后量子时代的“公章”（负责数字签名）。在 NIST 的后量子密码标准化进程中，它最终胜出并成为了 ML-DSA (FIPS 204) 标准。
Abstract (摘要) —— 30秒电梯演讲

1. 逐行精读与直觉

原文："In this paper, we present the lattice-based signature scheme Dilithium... part of the CRYSTALS suite..."

教授直觉：
开门见山：我叫 Dilithium（锂），是 CRYSTALS 家族的成员（Kyber 的兄弟）。
地位：我是来竞选 NIST 标准的。

原文："The design of the scheme avoids all uses of discrete Gaussian sampling and is easily implementable in constant-time."

核心卖点 1：无高斯采样 (No Gaussians)
直觉（重中之重）：
在 Dilithium 之前，最厉害的格签名叫 BLISS。它很快，但它需要生成一种叫“高斯分布”的随机数（这就好比要求你扔飞镖，必须精准地让 95% 的飞镖落在靶心红点，5% 落在外圈，这很难控制）。
痛点：在电脑上画高斯曲线非常难，且容易被黑客通过“画图的时间”或“耗电量”猜出你的飞镖落点（侧信道攻击）。
Dilithium 说：我不用高斯分布了！ 我只用均匀分布（就是普通的扔硬币，正反面概率一样）。这让代码极好写，而且天生安全。

原文："...public key that is 2.5X smaller than the previously most efficient lattice-based schemes that did not use Gaussians..."

核心卖点 2：小巧
直觉：
以前不用高斯采样的方案（如 bimodal lattice signatures），公钥特别大，像背着石头的巨人。
Dilithium 通过数学优化，把这个石头削掉了一半多（2.5倍），变得身轻如燕。

原文："...significantly improve the running time of... the number theoretic transform (NTT)."

核心卖点 3：极速
直觉：
还是那个老朋友 NTT（格密码的涡轮增压引擎）。作者不仅用了它，还改进了它，让它比以前更快了。

1. Introduction (引言) —— 格签名的江湖恩怨

这一章梳理了格签名的进化史。
1.1 格密码的分类 (The Landscape)

原文："Lattice-based cryptography... strong security guarantees... efficiency..."

直觉：格密码是目前最有希望的抗量子方案。
两大流派：

Hash-and-Sign (GPV 框架)：像 Falcon。做法是：把消息哈希成一个点，然后在格子上找一个离这个点最近的格点作为签名。

优点：签名极小。
缺点：实现极难（需要复杂的浮点运算），容易因精度问题泄密。

Fiat-Shamir (Lyubashevsky 框架)：像 Dilithium。做法是：交互式证明我知道私钥，然后变成非交互签名。

优点：实现简单（主要是加减乘）。
缺点：签名稍大。

1.2 为什么放弃高斯采样？(The Gaussian Trap)

原文："The most efficient schemes... required sampling from a discrete Gaussian distribution..."

教授直觉（详细拆解）：
BLISS 的困境：BLISS 方案为了让签名极小，强行要求随机数满足高斯分布。
后果：这导致它在硬件实现时非常痛苦。你需要维护一个巨大的查找表，或者运行复杂的概率算法。黑客只要拿个示波器在旁边测一下你采样的耗时，私钥就可能漏了。
Dilithium 的觉醒：为了安全和工程落地，必须砍掉高斯采样。虽然这会让签名稍微变大一点（理论上的代价），但换来的是绝对的实现安全性（工程上的胜利）。

1.3 如何不用高斯也能做签名？(Rejection Sampling)

原文："Our scheme... is based on the 'Fiat-Shamir with Aborts' technique..."

核心技术：Fiat-Shamir with Aborts
直觉（核心逻辑）：
想象你在考场上。
普通 Fiat-Shamir：你做了一道题，答案是 $z$。但这个 $z$ 带有你的个人习惯（私钥特征）。老师（验证者）一看卷子就能猜出你是谁。
With Aborts (带中止)：
你算出答案 $z$ 后，先自己偷偷看一眼。
如果 $z$ 带有你的个人特征（比如字迹太潦草，或者数字太大），你就把卷子撕了（Abort），重新做一遍。
直到你做出一份看起来完全像标准答案（均匀分布）的卷子，再交上去。
结果：老师看到的卷子都是完美的标准格式，猜不出你的任何特征。这就是 Dilithium 保护私钥的方法。

1.4 模格的平衡 (Module Lattices)

原文："...Digital Signatures from Module Lattices..."

教授直觉：
这和 Kyber 的理由一模一样。
Ring-LWE（环格）：只有一根粗管子，虽快但太死板。
Module-LWE（模格）：捆在一起的几根细管子。
Dilithium 选择了模格，这样我们就可以通过增加管子的数量（$k=4, 6, 8$）来轻松调整安全等级，而不需要重写底层代码。

1.5 压缩公钥 (Key Compression)

原文："...public key that is 2.5X smaller..."

技术剧透：
为什么不用高斯采样，公钥还能变小？
因为 Dilithium 引入了一种“高低位分解 + Hint”的技术。
直觉：公钥 $t$ 是一个大数。我只给你 $t$ 的高位（大概值）。验签的时候，这点误差会导致算不对。于是我在签名里藏一个小纸条（Hint），告诉你“刚才进位了”。这样既省了公钥空间，又保证了正确性。

常见误解 (Common Misconceptions)

误解：“没有高斯采样，安全性会降低。”

纠正：不会。安全性是基于 LWE 和 SIS 困难问题的。去掉了高斯采样，只是改变了证明的方式（参数变大了一点），但只要遵循拒绝采样规则，私钥就不会泄露。实际上，去掉了高斯采样，侧信道安全性反而大大提高了。

误解：“Fiat-Shamir 就是零知识证明。”

纠正：Fiat-Shamir 是把交互式的零知识证明（Sigma 协议）变成非交互式签名的一种转化方法（Transform）。Dilithium 的本体是一个 Identification Scheme，通过 Fiat-Shamir 变成了 Signature Scheme。

误解：“模格（Module）比环格（Ring）慢。”

纠正：理论上慢一点点（因为是矩阵运算），但因为有了 NTT 加速，且 Module 结构更利于并行计算，实际工程实现中差别微乎其微。

整节总结 (Section Summary)

如果让你在组会 PPT 上讲这一部分，核心 Takeaway 是：

背景：格签名以前很难搞，BLISS 虽然好但有“高斯采样”这个致命工程弱点。
Dilithium 的定位：一个工程友好型的格签名方案。
三大法宝：

Uniform Sampling (均匀采样)：取代高斯采样，杜绝侧信道隐患，简化实现。
Fiat-Shamir with Aborts：通过“撕卷子”策略，防止私钥泄露。
Module Lattices：平衡了效率与灵活性。

结果：比同类无高斯方案小 2.5 倍，速度极快，且已经在 NIST 竞赛中获胜。

展望创新 (Innovation Outlook)

虽然这是 Introduction，但我们可以看到未来的优化方向：

签名尺寸：虽然比以前小了，但 2KB+ 的签名比起 RSA/ECC 还是太大了。能不能通过更激进的 Hint 压缩进一步减小？
侧信道：虽然去掉了高斯采样，但拒绝采样循环（Rejection Loop）本身的时间长短是否会泄露信息？（例如：私钥某些位是 1 时，拒绝率是否更高？）

严格对齐原文精读“2 Basic Operations”

我们将分四块来啃：2.1 环运算，2.2 NTT（快速乘法），2.3 哈希（生成随机对象），以及最烧脑的 2.4 高低位分解与 Hint（压缩技术）。
2.1 Ring Operations (环运算) —— 定义我们的“数字世界”

1. 逐行精读与直觉

原文："We let R and $R_q$ respectively denote the rings $\mathbb{Z}[X]/(X^n+1)$ and $\mathbb{Z}_q[X]/(X^n+1)$... n will always be 256 and q will be the prime $8380417$..."

教授直觉（数据结构）：
$R$ 和 $R_q$：别被“环（Ring）”吓到。在代码里，这就是一个长度为 256 的数组。
$X^n+1$：这定义了数组怎么做乘法（多项式乘法）。如果乘出来次数超过了 256，比如到了 $X^{256}$，就把它换成 $-1$。这叫“负循环卷积”。
$q = 8380417$：这是我们的“时钟刻度”。数组里的每个数字都不能超过它。
为什么是这个怪数？ 因为 $8380417 = 256 \times 32736 + 1$。它满足 $q \equiv 1 \pmod{2n}$，这是使用 NTT 加速算法的硬性要求。

原文："Modular reductions... centered reduction modulo q..."

教授直觉（正负数表示）：
在模 $q$ 的世界里，数字是绕圈的。
标准模 ($r \bmod q$)：结果在 $[0, q-1]$。比如 $q=10$，$-1$ 变成 $9$。这是计算机存储的方式（无符号整数）。
中心模 ($r \bmod^{\pm} q$)：结果在 $[-(q-1)/2, (q-1)/2]$。比如 $q=10$，$-1$ 还是 $-1$（或者 $-1 \equiv 9$）。这是数学分析时用的，因为我们需要衡量数字的“大小”（绝对值）。

原文："Sizes of elements... $||w||_\infty = \max_i ||w_i||_\infty$..."

教授直觉（尺子）：
无穷范数 ($||\cdot||_\infty$)：就是“最大值”。
给你一个多项式（数组），你扫一眼里面所有的数（取绝对值后），最大的那个数就是这个多项式的“大小”。
作用：Dilithium 的安全性全靠“拒绝采样”。如果算出个签名的某个系数太大（超过了界限），我们就要把它扔掉。这把尺子就是用来量这个的。

2. 常见误解

误解：“$q$ 是为了安全性选的大质数。”
纠正：不完全是。$q \approx 2^{23}$ (23 bits) 其实很小（相比 RSA 的 2048 bits）。选它主要是为了效率（NTT 友好）和空间（刚好塞进 3 个字节还有富余）。
误解：“向量和矩阵里的元素是数字。”
纠正：是大坑！ Dilithium 是 Module-Lattice。
Matrix $A$ 的每一个元素 $A_{i,j}$ 本身就是一个多项式（长度 256 的数组）。
所以一个 $4 \times 4$ 的矩阵其实包含了 $4 \times 4 \times 256$ 个整数。

2.2 NTT domain representation (NTT 域表示) —— 速度引擎

1. 逐行精读与直觉

原文："Our modulus q is chosen such that there exists a 512-th root of unity r modulo q... multiplication is pointwise there."

教授直觉（频域魔法）：
普通乘法：两个多项式相乘，复杂度是 $O(n^2)$（慢）。
NTT 乘法：

把多项式 $f$ 变身成 $\hat{f}$（NTT 变换）。
把多项式 $g$ 变身成 $\hat{g}$。
算 $\hat{h} = \hat{f} \times \hat{g}$。注意！这步是点乘（对应位置直接乘），复杂度 $O(n)$（极快）。
把 $\hat{h}$ 变回 $h$（INTT 变换）。

结论：NTT 是格密码能跑在手机上的根本原因。在 Dilithium 中，矩阵 $A$ 是直接在 NTT 域生成的，省去了变身的过程。

2.3 Hashing (哈希) —— 造物主

1. 逐行精读与直觉

原文："Hashing to a Ball... $B_{60}$... inside-out version of the Fisher-Yates shuffle..."

教授直觉（洗牌算法）：
目标：生成一个“挑战多项式” $c$。它必须非常稀疏（只有 60 个非零位），且非零位只能是 $\pm 1$。
SampleInBall：

先拿一个全是 0 的数组。
用哈希函数（SHAKE）吐出乱码。
根据乱码决定把哪 60 个位置变成 $\pm 1$。
Fisher-Yates：这是一种经典的洗牌算法，保证这 60 个位置是绝对随机均匀分布的，没有偏差。

原文："Expanding the Matrix A... ExpandMask..."

直觉（省空间）：
公钥矩阵 $A$ 很大（几 KB），如果直接发给别人太占带宽。
ExpandA：我们只发一颗 32 字节的种子 $\rho$。接收方用这个函数，像《我的世界》地图生成器一样，自己在本地“长”出整个矩阵 $A$。

2.4 High/Low Order Bits and Hints (高低位与提示) —— 核心黑科技

这是 Dilithium 最难懂、也是最精彩的设计。请打起十二分精神。
1. 逐行精读与直觉

原文："To reduce the size of the public key... extract 'higher-order' and 'lower-order' bits..."

教授直觉（压缩的代价）：
公钥 $t = As + e$ 是个大数（每个系数 23 bits）。
为了省流，Dilithium 说：“我只发给你高位（比如高 10 bits），低位我扔了。”
后果：验证者验签时，算出来的结果会和真实结果有误差。
致命伤：这点误差平时没啥，但如果正好遇到进位（比如 $0.9 + 0.2 = 1.1$，四舍五入变成 1，但如果 $0.9$ 被截断成 $0$，算出来就是 $0.2$，四舍五入是 0），验签就会失败！

原文："...produce a 1-bit hint h... essentially the 'carry' caused by z..."

核心机制：Hint (小纸条)
签名者（Alice）拥有私钥，她能算出精确值。
她预判一下：“哎呀，验证者（Bob）只有公钥的高位，他算这个位置的时候，因为缺少低位，肯定会算错进位。”
于是，Alice 在签名里附带一个 Hint $h$（就像传个小纸条）：“喂，第 5 个系数记得进位 1！”
Bob 收到 Hint 后，强制修正他的计算结果，从而验证成功。

2. 关键函数拆解 (Figure 3)

这几个函数是考试必考点，也是代码实现的核心。

Power2Round(r, d)

功能：把 $r$ 切成两半。
$r = r_1 \cdot 2^d + r_0$。
直觉：最简单的位运算切割。用于压缩公钥 $t \to (t_1, t_0)$。

Decompose(r, \alpha)

功能：也是切成两半，但是按 $\alpha$ 切，不是按 2 的幂切。
细节：$r = r_1 \cdot \alpha + r_0$。
为什么要有两个切法？ Power2Round 是为了压缩公钥（简单粗暴）；Decompose 是为了签名过程中的拒绝采样和 Hint 生成（更精细，要处理 $\pm$ 边界）。

MakeHint(z, r, \alpha)

功能：Alice 运行。判断 $r$ 和 $r+z$ 的高位是否一样。
逻辑：如果不一样（发生了进位），就输出 1，否则输出 0。

UseHint(h, r, \alpha)

功能：Bob 运行。
逻辑：如果收到 $h=1$，即使我算出来的 $r$ 看起来不该进位，我也强行让它进位（或退位），恢复出正确的高位。

3. 常见误解

误解：“Hint 会泄露私钥。”
纠正：Hint 确实包含了一点点关于 $z$ 的信息，但在设计上，这点信息量极小，且非线性，无法用来反推私钥。
误解：“Power2Round 和 Decompose 是一样的。”
纠正：不一样！Power2Round 是逻辑切割（$2^d$），Decompose 是算术切割（$\alpha = 2\gamma_2$）。在代码里混用会导致 catastrophic failure。

整节总结 (Section Summary)

这一章为 Dilithium 打造了四件兵器：

环 $R_q$：定义了 $256$ 维、模 $8380417$ 的数学世界。
NTT：让多项式乘法飞起来的加速器。
SampleInBall：生成稀疏、均匀挑战 $c$ 的洗牌机。
High/Low Bits & Hints：Dilithium 的灵魂。通过丢弃低位压缩公钥，再通过 Hint 机制修补进位错误，从而在“极小公钥”和“正确性”之间取得了完美平衡。

展望创新 (Innovation Outlook)

作为研究生，你在这一章可以发掘的创新点：

NTT 硬件加速：$q=8380417$ 是定死的，能不能在 FPGA/ASIC 上设计专用电路，让 NTT 跑得比 CPU 快 100 倍？
Hint 压缩：目前的 Hint 是一个稀疏向量，用简单的编码存储。有没有更高效的压缩算法（如霍夫曼编码的变体）能把 Hint 压得更小，从而减小签名尺寸？
侧信道防御：UseHint 函数里有 if 分支（条件执行）。在某些嵌入式芯片上，这可能会泄露信息。能不能把它改写成无分支 (Constant-time) 的位运算逻辑？（这在工程上非常有价值）。

严格对齐原文精读“3 Signature”

这一章是整篇论文的“总装车间”。在前两章我们制造了所有的零件（模格、NTT、哈希、Hint），现在我们要把它们组装成一套完整的、可运行的签名系统。
这里包含了三个核心算法：KeyGen（生成钥匙）、Sign（签名）、Verify（验签）。这里的流程图（Figure 4）是所有 Dilithium 代码实现的直接依据。
3. Signature (签名方案总览)

1. 逐行精读与直觉

原文："The Key Generation, Signing, and Verification algorithms... are presented in Fig. 4."

教授直觉：
别说话，先看图（Figure 4）。这是这一章的“圣经”。
作者提到这是一个“确定性 (Deterministic)”的版本。
什么是确定性？ 以前的签名（如 ECDSA）如果在签名时随机数生成器坏了（比如总是输出同一个数），私钥就会立刻被黑客算出来（索尼 PS3 就是这么被破的）。
Dilithium 的做法：它不依赖当时的随机数，而是用私钥和消息通过哈希算出随机数。这样即使硬件随机数坏了，签名也是安全的。

原文："...public key size is reduced by a factor of around 2.5... outputs $t_1 := Power2Round(t, d)$ as the public key..."

核心策略：公钥压缩
在标准 LWE 中，公钥是 $t = As + e$。
Dilithium 说：$t$ 太大了！我们把它切成两半：
$t_1$ (高位)：发布出去作为公钥。
$t_0$ (低位)：只有签名者自己知道（放在私钥里），或者干脆丢掉（其实这里为了签名效率保留了）。
后果：验证者只有 $t_1$，他算出来的结果会有误差。这就像我告诉你“现在是 12 点多”，你不知道是 12:01 还是 12:59。

Algorithm Gen (密钥生成)

这是 Alice 在家做的事。
流程拆解：

生成种子：$\rho$（用于生成 $A$），$K$（用于确定性签名），以及私钥种子。
生成矩阵与私钥：

$A \leftarrow \text{ExpandA}(\rho)$。
$(s_1, s_2)$：私钥向量，系数值很小（$\eta$）。

计算 LWE 样本：

$t = As_1 + s_2$。这是核心方程。

压缩公钥：

$(t_1, t_0) := \text{Power2Round}(t, d)$。
$t_1$：公钥的一部分。
$t_0$：私钥的一部分（这点很重要！虽然它是 $t$ 的一部分，但在 Dilithium 里它被归类到 $sk$ 中，用于后续计算 Hint）。

打包：

$pk = (\rho, t_1)$。
$sk = (\rho, K, tr, s_1, s_2, t_0)$。其中 $tr$ 是公钥的指纹，用于防止替换攻击。

Algorithm Sign (签名)

这是最复杂的部分，包含了拒绝采样循环。
逐行拆解：

Line 10: $\mu \leftarrow CRH(tr || M)$

直觉：先把消息 $M$ 和公钥指纹 $tr$ 绑在一起哈希成 $\mu$。这确保了签名是针对“这个公钥”和“这条消息”的。

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

直觉（死循环）：这就是拒绝采样。我们在不断尝试，直到生成一个完美的签名。

Line 13: $y \leftarrow \text{ExpandMask}(...)$

直觉：生成一个随机掩码 $y$。它是保护私钥的盾牌。

Line 14-15: $w := Ay$; $w_1 := \text{HighBits}(w, 2\gamma_2)$

直觉（承诺）：算出 $w$，并取它的高位 $w_1$。这是我们要向验证者“承诺”的值。

Line 16: $c \in B_{60} := H(\mu || w_1)$

直觉（挑战）：把消息 $\mu$ 和承诺 $w_1$ 一起哈希，生成挑战多项式 $c$。这个 $c$ 很稀疏（只有 60 个 $\pm 1$）。

Line 17: $z := y + cs_1$

直觉（响应）：这是标准的 Schnorr 签名格式。$z$ 是对挑战的响应。

Line 18: $(r_1, r_0) := \text{Decompose}(w - cs_2, 2\gamma_2)$

直觉（检查准备）：
这里为什么是 $w - cs_2$？因为 $Ay - cs_2 = A(z - cs_1) - cs_2 = Az - c(As_1 + s_2) = Az - ct$。
验证者那边算的是 $Az - ct$。所以签名者要模拟验证者的视角，检查这个值是否会出问题。

Line 19: if $||z||_\infty \ge \gamma_1 - \beta$ or $||r_0||_\infty \ge \gamma_2 - \beta$ ... then restart

直觉（安检门）：
条件 1 ($z$)：$z$ 不能太大，否则会泄露 $s_1$ 的大小信息（拒绝采样核心）。
条件 2 ($r_0$)：这是为了正确性。如果低位 $r_0$ 太大，意味着加上一点点误差就会导致高位 $r_1$ 发生进位。验证者没有低位信息，一旦进位，他就永远算不对了。所以如果 $r_0$ 处于“危险边缘”，我们直接放弃这次签名，重来！

Line 21: $h := \text{MakeHint}(-ct_0, w - cs_2 + ct_0, 2\gamma_2)$

直觉（生成小抄）：
验证者没有 $t_0$（公钥低位），所以他算出来的值和真实值差了一个 $ct_0$。
签名者计算：如果加上这个 $ct_0$，会不会导致高位变化？
如果会，就在 $h$ 里记一笔：“这里进位了”。

Line 22: if $||ct_0||_\infty \ge \gamma_2$ or #1s in h > $\omega$ ... then restart

直觉（最后的检查）：
如果 $ct_0$ 造成的干扰太大（本身就超过了容错范围），或者需要的小抄 $h$ 太多（签名太大了放不下），也得重来。

Algorithm Verify (验签)

验证者拿着 $pk$ 和 $\sigma=(z, h, c)$。
逐行拆解：

Line 27: $w'_1 := \text{UseHint}(h, Az - ct_1 \cdot 2^d, 2\gamma_2)$

核心魔法：
验证者想算 $w_1$（$Ay$ 的高位）。
*但他只有 $z$ 和 $t_1$。
他计算 $Az - c t_1 2^d$。这个值大约等于 $Ay$。
误差来源：主要误差是 $-ct_0$（因为 $t_1 2^d = t - t_0$）。
UseHint：利用签名里带的 $h$，修正这个近似值，奇迹般地还原出了一模一样的 $w_1$。

Line 28: return ... $c = H(\mu || w'_1)$

直觉：
如果还原出的 $w'_1$ 和签名者当初用的 $w_1$ 一样，那么哈希出来的 $c$ 也应该一样。
如果一样，签名有效。

3.1 Correctness (正确性证明)

为什么 UseHint 能还原 $w_1$？

原文："The verifier computes $UseHint_q(h, Az - ct_1 \cdot 2^d, 2\gamma_2) = HighBits_q(w - cs_2, 2\gamma_2)$"

数学推导：
验证者手里的值：$v = Az - c t_1 2^d = Az - c(t - t_0) = (Az - ct) + ct_0$。
因为 $z = y + cs_1$ 且 $t = As_1 + s_2$，所以 $Az - ct = A(y+cs_1) - c(As_1+s_2) = Ay - cs_2 = w - cs_2$。
所以验证者手里的值其实是：$(w - cs_2) + ct_0$。
Hint 的作用：签名者生成的 Hint 是基于 $r = w - cs_2 + ct_0$ 和 $z = -ct_0$ 的关系。
只要 $ct_0$ 足够小（不超出容错范围），Hint 就能告诉验证者如何消去 $ct_0$ 的影响，从而恢复出 $w - cs_2$ 的高位。
而在拒绝采样步骤 19 中，我们已经保证了 $r_1 = w_1$（即 $w - cs_2$ 的高位等于 $w$ 的高位）。
闭环达成：验证者恢复出了 $w_1$。

3.2 Number of Iterations (效率分析)

原文："The expected number of repetitions is between 4 and 7."

直觉：
拒绝采样虽然安全，但代价是慢。平均需要跑 4 到 7 次循环才能生成一个合格的签名。
这主要是因为我们需要 $z$ 和 $r_0$ 同时落在安全区间内。这是一个概率事件。
公式：概率 $\approx e^{-256 \cdot \beta (k/\gamma_1 + k/\gamma_2)}$。参数 $\gamma_1, \gamma_2$ 选得越大，通过率越高，但安全性越低（因为泄露的信息越多）。这是一个权衡。

常见误解 (Common Misconceptions)

误解：“签名就是 $(z, c)$。”

纠正：在 Dilithium 里，签名是 $(z, h, c)$。那个 $h$（Hint）至关重要，没有它验证者算不出正确结果。

误解：“验证者算出的是 $Ay$。”

纠正：验证者算出的是 $Ay - cs_2$ 的高位。但因为我们在签名时检查了 $LowBits(Ay - cs_2)$ 很小，所以数学上保证了 $HighBits(Ay - cs_2) = HighBits(Ay)$。这是极其微妙的一步。

误解：“公钥里的 $t_1$ 是精确的。”

纠正：$t_1$ 是有损压缩后的值。正是因为这个损耗，我们才需要 Hint 机制来填补验证时的鸿沟。

整节总结 (Section Summary)

架构：基于 Fiat-Shamir 变换，引入了公钥压缩和 Hint 机制。
Sign：核心是拒绝采样循环。

既要保证 $z$ 不泄露私钥（安全）。
又要保证 $Ay - cs_2$ 的低位不发生溢出（正确性）。
还要生成 Hint 来辅助验证者纠错。

Verify：

核心是利用 UseHint 和压缩后的公钥，重建挑战 $c$。

代价：签名过程是不确定的（平均 4-7 次循环），但验证过程是确定且极快的。

展望创新 (Future Innovation)

减少循环次数：目前的 4-7 次循环是性能瓶颈。有没有办法通过改进分布或参数，让期望次数降到 2 以下？（这可能需要更大的参数）。
确定性签名与侧信道：虽然算法逻辑是确定性的（通过 seed 派生随机数），但循环次数是不确定的。攻击者可以通过统计循环次数（时间长短）来推测私钥吗？（Timing Attack）。这是一个非常前沿的研究点。
更小的 Hint：目前 Hint 采用稀疏编码。有没有更高效的编码方式能进一步压缩签名大小？

严格对齐原文精读“4 Security”

如果说前几章是“设计图”和“总装车间”，那么 第 4 章：Security（安全性） 就是“法庭辩护”。
在密码学里，光把算法造出来是不够的，你必须在数学上证明它是安全的。这一章作者要面对最严厉的质询：“你凭什么说你的签名造不了假？你凭什么说私钥算不出来？”
我们重点关注：Dilithium 到底依赖什么数学难题？以及它是如何证明“没人能伪造签名”的？
4. Security (安全性总览)

1. 逐行精读与直觉

原文："The standard security notion for digital signatures is UF-CMA security... A slightly stronger security requirement... is SUF-CMA..."

教授直觉（安全标准）：
UF-CMA (选择消息攻击下的不可伪造性)：这是及格线。意思是：即使我（攻击者）让你签了 100 份文件，我也造不出第 101 份新文件的签名。
SUF-CMA (强不可伪造性)：这是优秀线。意思是：即使我有了文件 $M$ 的签名 $\sigma$，我也造不出针对同一份文件 $M$ 的另一个合法签名 $\sigma'$。
Dilithium 的承诺：我是 SUF-CMA 安全的。这意味着签名不仅难伪造，而且具有“唯一性”（在某种意义上），这对某些应用（如区块链）很重要。

原文："...security of the scheme is based on a non-interactive problem that’s a convolution of a lattice problem with a cryptographic hash function."

核心逻辑（安全铁三角）：
Dilithium 的安全性不是建立在沙滩上的，而是由三根柱子支撑：

MLWE (Module-LWE)：保护私钥不被算出来。
MSIS (Module-SIS)：防止签名被伪造。
SelfTargetMSIS：这是 Fiat-Shamir 结构的特有问题，是哈希函数和格问题的结合体。

4.1 Assumptions (三大数学假设)

这一节定义了“我们假设敌人解不开哪些难题”。
1. MLWE (Module-LWE) —— 保护钥匙

原文："The MLWE Problem... distinguish... $(A, t)$ from random."

直觉：
公钥 $t = As_1 + s_2$。
难题：给你 $A$ 和 $t$，你能算出 $s_1$ 吗？或者你能分辨出这个 $t$ 是算出来的，还是我瞎写的乱码？
作用：如果这个问题很难，那么私钥就是安全的。攻击者看公钥就像看天书，根本推导不出私钥。

2. MSIS (Module-SIS) —— 防止伪造

原文："The MSIS Problem... finding short vector y such that $[I|A] \cdot y = 0..."

直觉：
SIS 是 Short Integer Solution（短整数解）。
难题：给你一个很宽的矩阵，让你找几个短向量，把它们加加减减组合起来，结果刚好等于 0。
在签名中的角色：如果你能伪造签名，本质上你就是找到了一个满足方程 $Az - ct = w$ 的解。这等价于你在格上找到了一个“短向量”。
作用：如果 SIS 很难，那么伪造签名就很难。

3. SelfTargetMSIS —— 哈希的魔法

原文："The SelfTargetMSIS Problem... find y, M such that $H(... y || M) = c$..."

教授直觉（借力打力）：
这是 Fiat-Shamir 签名特有的难题。
攻击者想要伪造签名 $(z, c)$，他必须先算出 $w = Az - ct$，然后还要保证 $H(M || w) = c$。
这是一个“自己以此之矛，攻以此之盾”的死循环：为了算 $c$ 你需要 $w$，为了算 $w$ 你需要 $c$。
除非你能破解哈希函数（找到碰撞），或者你能解开底层的 SIS 问题，否则你走不出这个循环。

4.2 Signature Scheme Security (安全性证明)

这一节展示了如何把“攻破 Dilithium”转化为“攻破上述数学难题”。
1. QROM 与 Tightness (量子世界的不完美)

原文："...reduction is not tight... security in the quantum random oracle model (QROM)."

直觉：
Tight (紧致)：如果算法被破了，数学难题肯定被秒杀。
Non-tight (非紧致)：如果算法被破了，数学难题可能被破，也可能没被破（或者需要花巨大代价才能破）。
Dilithium 的现状：在量子世界（QROM）里，证明是不紧致的。这意味着理论上我们要把参数设得更大一点来弥补这个“缝隙”。
但是！ 作者指出，目前没有任何已知的攻击能利用这个“缝隙”。历史上所有的 Fiat-Shamir 签名（如 Schnorr）都有这个问题，但几十年来都安然无恙。所以 Dilithium 依然敢用现在的参数。

2. 具体的安全归约 (Equation 6)

公式：$Adv_{Dilithium} \le Adv_{MLWE} + Adv_{SelfTargetMSIS} + Adv_{MSIS}$

直觉：
攻破 Dilithium 的难度 $\approx$ 攻破 MLWE 的难度 $+$ 攻破 MSIS 的难度。
只要这三个积木里有一个还要命地硬，整个大厦就不会倒。

3. Strong Unforgeability (强不可伪造性)

原文："...adversary sees a signature (z, h, c)... and then only changes (z, h)."

直觉：
怎么防止攻击者拿到你的签名后，改改里面的 $z$ 和 $h$，搞出一个“新”签名？
关键在于 Hint：前面的 Lemma 1 证明了，对于固定的 $c$ 和公钥，合法的 $z$ 和 $h$ 几乎是唯一的（或者说很难找到另一个）。
所以攻击者没法微调签名，这就实现了 SUF-CMA。

4.3 Concrete Security Analysis (具体的硬度)

光有理论不行，还得算算具体的破解成本。
1. Core-SVP Hardness (把格问题当萝卜切)

原文："...assume the adversary can run the asymptotically best algorithms known... BKZ..."

教授直觉：
我们假设攻击者有无限内存，用的是世界上最好的格基规约算法 (BKZ)。
Core-SVP：这是衡量格密码强度的标尺。
比如 Dilithium-3（推荐参数），破解它需要运行 Blocksize 为 475 的 BKZ 算法。
这相当于 $2^{125}$ 的量子比特操作成本。
结论：在可预见的未来，哪怕有了量子计算机，这也算不出来。

2. SIS vs LWE (谁是短板？)

原文："...MLWE problem is a low-density knapsack, while MSIS is a high-density knapsack instance."

直觉：
Dilithium 的安全性取决于这两个问题的短板。
实际上，对于推荐参数，MLWE（偷私钥）和 MSIS（伪造签名）的难度是平衡的，没有明显的短板。

常见误解 (Common Misconceptions)

误解：“证明不紧致（Non-tight）意味着不安全。”

纠正：不紧致只是意味着“理论证明”和“实际参数”之间有空隙。在密码学工程中，只要没有已知的攻击路径利用这个空隙，且安全余量足够大（比如 Dilithium 选的参数都很保守），通常被认为是安全的。不要看到 Non-tight 就慌。

误解：“SelfTargetMSIS 就是 SIS 问题。”

纠正：它比 SIS 更难。因为它强制要求输出的哈希值匹配。它结合了哈希函数的抗碰撞性和格的困难性。这其实是 Fiat-Shamir 签名的核心安全保障。

误解：“Dilithium 是基于 LWE 的。”

纠正：准确说是基于 Module-LWE 和 Module-SIS。只提 LWE 是不完整的，因为不可伪造性主要依赖 SIS。

整节总结 (Section Summary)

安全模型：Dilithium 达到了 SUF-CMA（强不可伪造）标准，在 QROM（量子随机预言机）模型下是安全的。
三大基石：

MLWE：保密性（Key Recovery）。
MSIS：防伪造（Forgery）。
SelfTargetMSIS：Fiat-Shamir 结构的特有保障。

量化指标：通过 Core-SVP 方法估算，推荐参数达到了 NIST Level 2/3/5 的安全要求，足以抵抗已知的量子攻击算法（Grover, BKZ）。

展望创新 (Innovation Outlook)

作为研究生，这一章指出了几个前沿方向：

Tight Reduction：有没有办法设计一个新的格签名，在 QROM 下也是 Tight 的？（这通常需要改变构造，不只是调参数）。
针对 SIS 的新攻击：论文提到 SIS 的 $l_\infty$ 范数分析可能不是最优的。如果你能找到一种针对无穷范数 SIS 的更优攻击算法，那将是轰动性的成果（当然，Dilithium 的参数留了余量）。
侧信道下的安全性证明：目前的证明假设是黑盒的。如果攻击者能通过侧信道泄露一点点 $y$ 的信息，安全性会下降多少？这需要 Leakage-Resilient Cryptography 的理论支持。

严格对齐原文精读“5 Implementation Details”

如果说前几章是在“黑板上推导公式”，那么 第 5 章：Implementation Details（实现细节） 就是带你走进“精密加工车间”。
在这里，数学家退场，工程师登场。我们要解决的问题是：“如何把那些漂亮的数学公式，变成在真实 CPU 上跑得飞快、且不会被黑客窃听的代码？”
这一章充满了“脏活累活”：比特怎么排？内存怎么省？怎么防止 CPU 偷懒泄密？虽然琐碎，但这是 Dilithium 能打败其他算法、成为 NIST 标准的关键原因——它不仅理论强，工程落地更是极其优秀。
我们把这章拆解为：数据表示、哈希工厂、打包压缩、防侧信道、以及极致速度（AVX2）。
5.1 NTT domain representation (NTT 域表示)

这是关于“数据存储格式”的规定。
1. 逐行精读与直觉

原文："Natural fast NTT implementations do not output vectors with coefficients in the order $a(r), a(r^3), \dots, a(r^{511})$... we define the NTT domain representation... to have coefficients in the order as output by our reference NTT."

教授直觉（乱序存储）：
想象你要整理一副扑克牌。
正常顺序：A, 2, 3, ..., K。
NTT 算法的特性：为了追求极致速度，NTT 算法跑完之后，吐出来的结果是乱序的（Bit-reversed order，比特反转序）。
Dilithium 的决策：既然乱序算得快，那我们就不整理了！
ExpandA 的优化：我们在生成公钥矩阵 $A$ 时，直接生成这种“乱序”的数据。这样在做乘法时，就不需要先做一次 NTT 变换了，省了一大笔时间。这叫“原生支持乱序”。

5.2 Hashing (哈希工厂)

这一节讲述如何用哈希函数（SHAKE）像变魔术一样变出各种数学对象。
1. Hashing to a Ball (生成挑战 c)

原文："...maps $\mu || w_1$ to $c \in B_{60}$... inside-out version of the Fisher-Yates shuffle..."

直觉（洗牌发牌）：
我们的目标是生成一个只有 60 个非零位（$\pm 1$）的稀疏多项式。
SHAKE-256 是我们的发牌员。它吐出一串随机字节。
前 8 个字节：决定了这 60 个非零位的正负号。
后续字节：决定了这 60 个非零位的位置。
拒绝采样：如果发牌员给出的位置已经有牌了（位置冲突），我们就再抽一张。直到凑齐 60 个不同的位置。这保证了分布的绝对均匀。

2. Expanding A and y (生成矩阵与掩码)

原文："ExpandA maps a uniform seed $\rho$ to a matrix $A$... in NTT domain representation."

直觉（并行流水线）：
生成矩阵 $A$ 需要海量的随机数。
这是一个并行的过程。矩阵的每一个元素（多项式）都是独立生成的。
拒绝采样：SHAKE 吐出 3 个字节，我们看它能不能拼成一个 $< q$ 的整数。如果能，收下；如果不能（比如拼出了 8380420，大于 8380417），扔掉重来。

5.3 Data layout (数据打包)

这是为了省空间做的“压缩打包”。
1. 逐行精读与直觉

原文："The public key... stored as the concatenation of the bit-packed representations... Secret key... Signature..."

教授直觉（宜家平板包装）：
在数学里，一个系数是一个整数（比如 13-bit）。但在计算机里，最小单位是字节（8-bit）。
如果直接存，13-bit 就要占 2 个字节（16-bit），浪费 3-bit 空气。
Bit-packing (位打包)：把这些数字像俄罗斯方块一样紧紧挤在一起，不留缝隙。
Example：私钥里的 $s_1$ 系数范围是 $-\eta \sim \eta$。如果是 $\eta=2$，范围是 -2, -1, 0, 1, 2（共5种可能）。我们就用 3 个 bit ($2^3=8$) 来存它。如果是 $\eta=4$，就用 4 个 bit。
结果：公钥被压到了 1.3KB，签名压到了 2.4KB。如果不压，可能要翻倍。

5.4 Constant time implementation (防侧信道实现)

这是安全工程最核心的部分。
1. 逐行精读与直觉

原文："Our reference implementation does not branch depending on secret data and does not access memory locations that depend on secret data."

核心原则：扑克脸 (Poker Face)
大忌：if (secret_bit == 1) { do_A(); } else { do_B(); }
为什么？ 黑客拿着秒表在旁边掐时间。do_A 和 do_B 耗时不同，黑客一听就知道你的 secret_bit 是几。
Constant-time (常数时间)：无论私钥长什么样，代码跑的时间必须一模一样。

原文："Instead we use Montgomery reductions... and special reduction routines... never use the '%' operator..."

直觉（避免陷阱）：
C 语言里的取模 % 是个坑。对于负数，它的行为不仅怪异，而且 CPU 执行除法指令的时间是不固定的（取决于数值大小）。
Montgomery Reduction：这是一种“不用除法的取模术”。它只用乘法和位移（Shift）就能算出模运算的结果。这两个操作在 CPU 上是绝对等时的。

原文："...rejection sampling... reveals which of the conditions was the reason for the rejection... This is safe..."

例外情况：
在签名时，我们可以泄露“拒绝采样失败了”这个信息。
为什么？ 因为拒绝本身是基于公开信息（$z$ 的范数）判断的，而且我们设计的数学分布保证了拒绝概率和私钥无关。所以这里允许非恒定时间，换取效率。

5.5 & 5.6 Optimization (参考实现与 AVX2 加速)

这一节展示了如何利用 CPU 的特性把速度推到极致。
1. Montgomery & Lazy Reduction (懒惰是美德)

原文："We make heavy use of lazy reduction... In the NTT we do not reduce the results of additions..."

直觉：
做加法 $a+b$ 后，结果可能会超过 $q$。标准做法是马上减去 $q$（归约）。
Lazy Reduction：我不减！我让它先大着。只要它别大到溢出寄存器（64-bit），我就攒着。等到做了好几次运算，必须要输出的时候，再一次性减掉。
收益：少做了很多次减法，速度起飞。

2. AVX2 Vectorization (并行化)

原文："...we can do four vector multiplications and Montgomery reductions in parallel."

直觉（四车道高速）：
普通代码一次算 1 个乘法。
AVX2 指令集允许一次算 4 个甚至 8 个乘法（SIMD）。
Dilithium 特意设计成 $n=256$，完美契合 AVX2 的寄存器宽度。
Shuffle：为了配合并行，数据在寄存器里需要“洗牌”（Permute/Shuffle），让需要相乘的数据正好对齐。

常见误解 (Common Misconceptions)

误解：“C 代码写出来就是安全的。”

纠正：大错特错！ 编译器（GCC/Clang）为了优化速度，可能会把你写的“常数时间代码”优化成“有分支的代码”（比如把位运算优化成跳转）。写密码学代码必须检查汇编，或者使用 volatile 等手段阻止编译器自作聪明。

误解：“NTT 只是为了算得快，跟数据格式无关。”

纠正：在 Dilithium 中，矩阵 A 是直接在 NTT 域定义的。这意味着如果你不理解 NTT 的数据布局（乱序），你甚至无法正确生成公钥。NTT 渗透到了协议的定义里。

误解：“随机数生成器 (RNG) 只要调用系统函数就行。”

纠正：Dilithium 强制使用 SHAKE (XOF) 来扩展种子。这不仅仅是为了随机性，更是为了确定性（保证在不同机器上由同一颗种子能跑出一样的结果，方便调试和验证）。

整节总结 (Section Summary)

数据流：采用了Bit-packing（位打包）极致压缩公钥和签名，采用了NTT Domain（频域）直接存储矩阵以提升速度。
安全性实现：严格遵循Constant-time（常数时间）编程规范，杜绝分支和查表，使用 Montgomery 算法替代除法取模，防止侧信道攻击。
性能优化：

Lazy Reduction：能不取模就不取模，攒着一起做。
AVX2：利用 CPU 的并行指令，一次处理多个系数，实现了比参考代码快 4-5 倍的性能。

展望创新 (Innovation Outlook)

作为研究生，如果你想在工程实现上发论文，这里是金矿：

非 Intel 架构优化：

论文只以此 Intel AVX2 为例。在 ARM Neon（手机）、RISC-V Vector（物联网）上如何高效实现 Dilithium？这些平台的指令集特性不同，需要重新设计流水线。

硬件协同设计 (Co-design)：

设计一种专门跑 Dilithium 的 FPGA 架构。现在的瓶颈在于 SHAKE 哈希和 NTT。如果你能设计一个“流式”的哈希-NTT 转换器，能极大降低延迟。

抗故障注入 (Fault Injection)：

虽然防了侧信道（Timing），但如果攻击者用激光照射芯片（Fault），跳过了验签步骤怎么办？研究如何在代码中加入轻量级的冗余检查是目前的热点。

严格对齐原文精读“6 Comparisons”

如果说前五章是在自家车间里打磨零件、组装赛车，那么这一章就是“把车开到赛道上”。作者要把 Dilithium 和其他的后量子签名方案拉出来溜溜，比比谁跑得快，谁更省油（密钥小），谁更安全。
这一章对于研究生来说极具战略价值。如果你在答辩时被问到：“为什么不用 SPHINCS+？为什么不用 Falcon？” 答案全在这里。
我们将这一章分为三大板块来解读：非格密码对手、格密码内部斗争，以及数据对比。
6. Comparisons (群雄逐鹿)

6.1 开局：三大门派

原文："There are three major approaches for post-quantum signatures: hash-based signatures, multivariate signatures, and lattice-based signatures."

教授直觉（江湖格局）：
后量子签名界有三大门派：

哈希派 (Hash-based)：极其保守，只依赖哈希函数。
多变量派 (Multivariate)：数学结构复杂，以小签名著称。
格派 (Lattice-based)：也就是 Dilithium 所在的门派，以平衡性著称。

原文："...stateful hash-based signatures like XMSS... NIST therefore explicitly asks for stateless signature proposals."

直觉（有状态 vs 无状态）：
Stateful (有状态)：像 XMSS。你每签一次名，必须在硬盘上记一笔“我签过了”。如果你忘了记（比如恢复备份），私钥就会泄露。这对服务器运维是噩梦。
Stateless (无状态)：像 Dilithium。想签就签，不需要记账。NIST 只要这种，因为好用。

6.2 Non-Lattice-Based Signatures (外部分析)

1. Hash-based (SPHINCS)

原文："...stateless hash-based signatures are rather inefficient in terms of signature size and signing speed. For example, the SPHINCS signature scheme has signatures of about 40 KB..."

教授直觉（重型坦克）：
SPHINCS 是最安全的“备胎”。只要哈希函数（SHA-256）不被破，它就不被破。
缺点：太重了！签名有 40KB（Dilithium 只有 2.4KB）。速度也慢（几千万个时钟周期）。
结论：除非你对安全性有极度偏执，或者数学大厦崩塌了，否则不首选它。

2. Multivariate (Rainbow / MQDSS)

原文："...small signatures, however, come at the expense of rather large public keys... require a hidden structure... which was a weakness..."

教授直觉（玻璃大炮）：
优点：签名极小（几十字节），比现在的 ECC 还小！
缺点 1：公钥巨大（几百 KB）。
缺点 2 (致命)：安全性基于“隐藏结构”。这在历史上翻车无数次了（Rainbow 后来在 NIST 决赛中确实被打破了）。数学基础不牢靠。

6.3 Lattice-Based Signatures (内战：谁是格密码之王？)

这是本章的重头戏。Dilithium 要踩着前辈上位。
1. NTRU-based (BLISS / Falcon)

原文："The most efficient... are those based on the hardness of the NTRU problem... crucially require sampling from the discrete Gaussian distribution..."

对手分析：
BLISS / Falcon：这俩是以前的王者。它们用了一种叫 NTRU 的特殊格，效率极高。
致命弱点 (The Gaussian Trap)：
它们必须使用离散高斯采样。
教授直觉：在电脑上画高斯曲线非常难。为了画得准，需要复杂的查表或浮点运算。
后果：很难防侧信道攻击（Timing/Power Analysis）。就像为了走得快，必须在钢丝上跑步，稍微一抖（实现不完美）就掉下去了。
Dilithium 的暴击：
"Dilithium... avoids all uses of discrete Gaussian sampling"。
我用均匀采样（Rejection Sampling）。虽然理论效率稍微低一点点，但工程实现绝对安全，是在平地上跑步。

2. Standard-LWE (TESLA)

原文："...digital signatures based on the hardness of standard lattice problems... extremely large public keys..."

对手分析：
TESLA：不用多项式，只用大矩阵。
缺点：公钥大得离谱（12MB vs Dilithium 的 1.3KB）。完全不实用。

3. Dilithium 的定位

原文："...sit in the sweet spot that offers reasonably small signatures and public keys... simple constant-time implementations."

总结：
我比 SPHINCS 快和小。
我比 Rainbow 安全。
我比 BLISS 好实现且安全（无高斯）。
我是“甜点区 (Sweet Spot)”的选择。

6.4 Data Comparison (数据说话 - Table 3)

让我们看表格，这是最后的“跑分”环节。

Table 3

| 方案 | 抗侧信道? (ct?) | 签名速度 (Cycles) | 公钥大小 (Bytes) | 签名大小 (Bytes) |
| | | | | |
| Dilithium (推荐) | Yes | 508K | 1472 | 2701 |
| NTRU-GPV | No | ?? | 1792 | ~1200 |
| BLISS | No | ?? | 1792 | ~1700 |
| TESLA-I | Yes | 143,402K (慢300倍) | 12MB (大8000倍) | 2444 |
| SPHINCS | Yes | 51,636K (慢100倍) | 1056 | 41,000 (大15倍) |
| Rainbow | Yes | 68K (快) | 145,500 (大100倍) | 48 (极小) |

教授解读：
Dilithium vs BLISS：虽然 BLISS 签名小一点 (1.7KB vs 2.7KB)，但它不是 Constant-time (ct? = No)。在安全领域，不安全的快没有意义。
Dilithium vs SPHINCS：速度快了两个数量级，签名小了一个数量级。完胜。
Dilithium vs Rainbow：Rainbow 签名虽小，但公钥太大，且后来被破了。Dilithium 综合最强。

常见误解 (Common Misconceptions)

误解：“签名越小越好。”

纠正：还要看公钥大小。在 TLS 握手（HTTPS）中，浏览器需要下载服务器的公钥 + 签名。所以要看两者之和。Dilithium 的和大约是 4KB，非常均衡。Rainbow 虽然签名小，但公钥几十 KB，传起来更慢。

误解：“Falcon（NTRU类）因为有高斯采样所以不安全。”

纠正：不是算法不安全，是实现很难安全。Falcon 后来也成为了 NIST 标准，因为它确实签名最小。但 NIST 在报告中也特别指出了 Falcon 实现的高难度，推荐在有专用硬件支持（FPU）的场景使用。而 Dilithium 是通用推荐。

误解：“Dilithium 是最快的。”

纠正：Rainbow 验签比 Dilithium 快。但在安全性、尺寸和速度的综合考量下，Dilithium 是没有明显短板的“六边形战士”。

整节总结 (Section Summary)

外部竞争：

Hash-based (SPHINCS)：太慢太重，仅作备胎。
Multivariate (Rainbow)：公钥太大，且数学结构脆弱。

内部竞争 (格密码)：

NTRU/BLISS：依赖高斯采样，工程实现极其危险（侧信道）。
Dilithium：使用均匀采样 + 拒绝采样，彻底解决了侧信道隐患，同时通过 Hint 机制保持了较小的尺寸。

最终结论：Dilithium 是目前最均衡、最容易安全实现的后量子签名方案。

展望创新 (Innovation Outlook)

Falcon 的无高斯化：

Falcon 签名很小但难实现。有没有可能把 Dilithium 的“拒绝采样”思想用到 Falcon (NTRU) 上，搞一个“无高斯 Falcon”？（这很难，因为 NTRU 结构特殊）。

针对特定场景的参数调整：

表格里展示的是通用参数。如果你的物联网设备只在乎公钥大小，不在乎签名大小，能不能调整 Dilithium 的 $d$ 和 $\gamma$ 参数来适配？

混合方案 (Hybrid)：

在过渡期，我们可能需要“传统签名 + 后量子签名”一起用。如何设计一个证书格式，把 ECDSA 和 Dilithium 打包在一起，且不增加太多开销？

【全篇结语】

Ch1-2：你懂了它为什么要抛弃高斯采样，选择了模格。
Ch3：你掌握了核心的 Fiat-Shamir 构造、拒绝采样循环和精妙的 Hint 机制。
Ch4：你理解了它是如何基于 MLWE 和 MSIS 证明安全性的。
Ch5：你看到了 AVX2 和 NTT 是如何让它起飞的。
Ch6：你知道了它凭什么打败其他对手成为标准。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

南宫玉英 · 前天 10:31

很好很强大我过来先占个楼待编辑

歇凛尾 · 昨天 15:34

感谢，下载保存了

账号		自动登录	找回密码
密码			立即注册

CRYSTALS-Dilithium：A Lattice-Based Digital Signature Scheme

相关帖子

回复

浏览过的版块

签约作者

CRYSTALS-Dilithium：A Lattice-Based Digital Signature Scheme

相关帖子

相关推荐

GradEscape: A Gradient-Based Evader Against AI

Lattice Cryptography 格密码概述

前端工程化 - 良好的feature-based-目录结构与具体示例

CRYSTALS - Kyber：A CCA-Secure Module-Lattice-Based KEM

Module-Lattice-Based Key-Encapsulation Mechanism Standard

回复

浏览过的版块

签约作者