ML-DSA (Dilithium)

ML-DSA
Module-Lattice-Based
Digital Signature Algorithm
设计者
Vadim Lyubashevsky, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Peter Schwabe, Gregor Seiler, Damien Stehlé
首次发布
2018 (Dilithium)
2024 (FIPS 204)
类别
后量子 · 数字签名
数学基础
Module-LWE / Module-SIS
标准
FIPS 204
安全状态
安全

ML-DSA（Module-Lattice-Based Digital Signature Algorithm），原名 Dilithium，是由 NIST 于 2024 年发布的后量子数字签名标准（FIPS 204）。它基于模格上的 Module-LWE 和 Module-SIS 数学难题，旨在替代 RSA-PSS、ECDSA、EdDSA 等经典数字签名方案，抵抗量子计算机的攻击。

一句话理解 ML-DSA：你手上有一个秘密向量 s，你随机选一个 y 来「遮住」它，然后公布 z = y + c·s。只要 y 足够随机，z 看起来就像是随机数——不会泄露 s。但别人无法伪造 z，因为他们不知道 s，而要猜中 s 就得解决一个连量子计算机都搞不定的数学难题。
背景与标准化

数字签名是互联网安全的基石，用于 TLS 证书验证、代码签名、软件更新验证、电子文档签名等场景。然而 Shor 算法可以在量子计算机上高效破解 RSA 和 ECDSA 的数学基础。Dilithium 在 NIST 后量子密码标准化过程中被选为首选签名算法，于 2024 年 8 月作为 FIPS 204 正式发布。

ML-DSA 与 ML-KEM（Kyber）同属 CRYSTALS（Cryptographic Suite for Algebraic Lattices）项目，共享相同的数学基础（模格），设计风格一致。

数学预备知识

要理解 ML-DSA 的设计，需要了解几个关键数学概念。这里给出直觉性的解释，严格的数学定义请参阅 模格密码学数学基础 专题页。

1. 多项式环 Rq

ML-DSA 的所有运算都在一个特殊的多项式环上进行。简单来说，这个环的元素是「系数对 q 取模的 256 次多项式」：

R_q = Z_q[X] / (X^256 + 1)

你可以把它想象成一个 256 维的向量空间，每个元素有 256 个系数，每个系数是一个 0 到 q−1 之间的整数。两个元素相乘的方式由 X256 + 1 = 0 这个规则决定（即 X256 = −1，超过 256 次的项会「折回来」变成负的，类似模运算）。

在 ML-DSA-65 中，q = 1,952,581（一个 21 位的素数）。

2. 模格（Module Lattice）

「格」可以想象成 n 维空间中的网格点阵——就像二维平面上整数坐标点 (0,0), (1,0), (0,1), (1,1), ... 组成的规则格子，只是推广到了更高维度。

「模格」是在多项式环 Rq 上定义的格。在 ML-DSA 中，公钥定义了一组「基准向量」（矩阵  的行），私钥是一组「短」系数向量 s1，使得公钥 t = ·s1 + s2。知道短向量 s1 就相当于知道这组格点之间的一个「秘密捷径」。

3. 为什么这些问题难？

Module-SIS（短整数解问题）：给定矩阵 Â，找出一个「短」向量 z 使得 ·z ≈ 0。这就像在一个高维网格中，要找到一个离原点很近的格点——当维度很高时，搜索空间呈指数增长，暴力搜索完全不可行。

Module-LWE（学习误差问题）：给定 (Â, t = ·s + e)，其中 s 和 e 都是短向量，要恢复出 s。这就像解一个线性方程组，但方程组被「噪声」干扰了——答案有无限种可能，你无法判断哪个才是正确的。

关键直觉：这两个问题之所以难，本质上是因为高维空间中的「最近点搜索」是一个公认的困难问题（类似 NP-hard）。目前已知的所有算法（包括量子算法）都只能比暴力搜索稍好一点，仍然是指数时间的。这正是 ML-DSA 安全性的根基。
算法详解

ML-DSA 由三个算法组成：密钥生成（KeyGen）、签名（Sign）和验证（Verify）。下面逐个讲解。

密钥生成 KeyGen

密钥生成的目标是产生一对公钥/私钥，使得：公钥公开一个「难题」，私钥是这个难题的「答案」。

KeyGen(): 输入：安全参数（决定矩阵维度 k×l 和模数 q） 1. 生成种子 ρ（rho），用它确定性生成矩阵 Â ∈ R_q^(k×l) Â 可以用哈希函数扩展出来，不需要存储整个矩阵 2. 从「小系数分布」中随机采样两个向量： s₁ ∈ S_η^l （l 个多项式，每个系数 ∈ {-η, ..., +η}） s₂ ∈ S_η^k （k 个多项式，每个系数 ∈ {-η, ..., +η}） 这里 η 是一个很小的数（如 η=2），所以 s₁, s₂ 的系数只取 -2, -1, 0, +1, +2 这几个值——这就是「短」的含义。 3. 计算公钥： t = Â · s₁ + s₂ （矩阵-向量乘法，再加一个小扰动） 4. 输出： 公钥 pk = (Â, t) ——"知道 s₁ 就能解开这个方程" 私钥 sk = (s₁, s₂, Â) ——秘密的「短向量」

要理解为什么这是安全的，可以这样想：公钥告诉你 t = ·s1 + s2，但 s1 和 s2 都非常「短」（系数只有 ±2 以内）。从 t 和  反推 s1 就是 Module-LWE 问题——目前没有任何已知的高效算法（包括量子算法）能解决它。

类比例子：想象你有一个巨大的线性方程组 Ax = b，但 b 被加了一个小噪声 e 变成 b' = Ax + e。你知道 A 和 b'，想要求 x。在低维情况下这也许能做，但当 x 有几千个分量、每个分量又有 256 个系数时，搜索空间是天文数字，你根本不知道哪个 x 是对的。
签名 Sign

签名是 ML-DSA 最精巧的部分。它使用了一种叫做 「Fiat-Shamir with Aborts」（带中止的 Fiat-Shamir）的技术。核心思想分三步：

Sign(sk, M): // sk = (s₁, s₂, Â), M = 消息 第 ① 步：生成随机「遮罩」y 从一个大范围中随机采样 y ∈ R_q^l y 的系数可以取比较大的值（不像 s₁ 那么短） y 的作用：把 s₁ 「藏」起来 第 ② 步：计算「承诺」和「挑战」 计算 w = Â · y （矩阵-向量乘法，不涉及私钥） 取 w 的高位比特：w₁ = HighBits(w) 用哈希函数生成挑战： c̃ = H(tr ‖ M ‖ w₁) // tr = H(pk)，M = 消息 把 c̃ 转化为一个小多项式 c（系数只有 -1, 0, +1） 这一步本质上是在说："我承诺了一个值 w₁，它由哈希绑定到消息 M" 第 ③ 步：计算「响应」 z = y + c · s₁ （关键步骤！） 现在检查 z 是否「太大」： 如果 ‖z‖∞ > γ₁ - β: // z 的最大系数超出了安全范围 → 丢弃这个 y，回到第 ① 步重新来 否则： 输出签名 σ = (z, h, c̃) 其中 h 是一些辅助信息（用于验证时重构 w₁）
为什么需要拒绝采样？
这是最关键的问题。z = y + c·s1，其中 y 是随机的大数，c·s1 是一个小的「偏移量」。如果 y 足够大，那么 z 的分布几乎完全由 y 决定，和 s1（私钥）无关——就像往一杯水里滴了一滴墨水，你无法从混合物判断那滴墨水是什么形状。

但如果 z 太大（某些系数超出了预设的安全边界），z 的分布就会「偏斜」，可能泄露关于 s1 的信息。这时就拒绝这个 z，重新来过。拒绝的概率大约在 1/7 到 1/3 之间（取决于参数集），所以平均尝试几次就能成功。

类比：想象你用投硬币来隐藏一个秘密数字。你先掷 100 次硬币得到 y，然后加上你的秘密 c·s₁ 得到 z。如果 z 的每一位都是大致 50/50 的 0 或 1，别人就看不出你的秘密。但如果某一位偏得太厉害（比如几乎全是 1），那就有问题了——这时候你就重新掷。
验证 Verify

验证过程比较直接——用公钥信息重新算一遍，看结果是否一致：

Verify(pk, M, σ): // pk = (Â, t), σ = (z, h, c̃) 1. 从签名中恢复 c（从 c̃ 直接得到） 2. 用公钥重新计算高位比特： w₁' = HighBits( · z − c · t) 注意： · z − c · t =  · (y + c·s₁) − c · (·s₁ + s₂) = ·y + c·Â·s₁ − c·Â·s₁ − c·s₂ = ·y − c·s₂ 因为 s₂ 很短（系数 ≤ η），c·s₂ 也很小， 所以 ·y − c·s₂ 的高位比特 = ·y 的高位比特 = w₁ 3. 重新计算哈希挑战： c̃' = H(tr ‖ M ‖ w₁') 4. 验证： ✓ c̃' == c̃ （挑战一致 → 签名人确实知道 s₁） ✓ ‖z‖∞ ≤ γ₁−β （z 在安全范围内 → 没有被篡改） ✓ h 的辅助信息一致 如果全部通过 → 签名有效

验证的数学原理很简单：因为 z = y + c·s1，所以 ·z − c·t = ·y − c·s2。由于 s2 很短，它对高位比特的影响为零（就像 12345 加上 ±2，万位和千位不变），所以 HighBits(·z − c·t) = HighBits(·y) = w1，和签名时计算的一样。

参数集与具体数值

ML-DSA 有三个参数集，数字命名规则是「安全级别-维度参数」：

参数集NIST 级别klηq公钥签名私钥
ML-DSA-44Level 24421,952,5811,312 B2,420 B2,560 B
ML-DSA-65Level 36541,952,5811,952 B3,309 B4,032 B
ML-DSA-87Level 58721,952,5812,592 B4,627 B4,896 B

其中 k 是矩阵 Â 的行数，l 是列数（也是 s1 和 y 的维度），η 是私钥系数的范围。安全级别越高，矩阵越大，公钥和签名也越大，但安全强度越高。

拒绝采样的概率
参数集接受概率（约）平均重试次数
ML-DSA-44~67%~1.5 次
ML-DSA-65~33%~3 次
ML-DSA-87~14%~7 次

拒绝采样虽然是「随缘」的，但接受概率是固定的、可预测的。最坏情况下也只是多试几次，不影响安全性。而且整个过程是恒定时间的——被拒绝的尝试不会产生任何输出，攻击者无法通过计时来推断信息。

完整签名流程图解
签名者（拥有私钥 s₁, s₂） 验证者（只看得到公钥 Â, t） ════════════════════════ ══════════════════════════ 1. 随机选 y 2. w = ·y 3. w₁ = HighBits(w) 4. c̃ = H(tr‖M‖w₁) 5. z = y + c·s₁ 6. 检查 z 是否太大 → 如果太大就回到步骤 1 7. 发送签名 σ = (z, h, c̃) ──────────→ 8. w₁' = HighBits(·z − c·t) 9. c̃' = H(tr‖M‖w₁') 10. 检查 c̃' == c̃ 且 ‖z‖ 不太大 11. ✓ 通过！签名有效 为什么能验证通过？ ·z − c·t = ·(y+c·s₁) − c·(·s₁+s₂) = ·y − c·s₂ 因为 s₂ 很短，c·s₂ 不影响高位 → w₁' = w₁ → c̃' = c̃ ✓ 为什么攻击者无法伪造？ 要伪造签名，攻击者需要找到 z 使得 ·z − c·t 的高位匹配 但不知道 s₁ → 这等价于解决 Module-SIS 问题 → 计算上不可行
与经典签名方案对比
方案数学基础公钥签名签名速度抗量子
RSA-2048大整数分解256 B256 B慢（~1 ms）Shor 算法可破解
ECDSA P-256椭圆曲线离散对数64 B64 B快（~0.1 ms）Shor 算法可破解
Ed25519椭圆曲线离散对数32 B64 B极快（~0.05 ms）Shor 算法可破解
ML-DSA-65模格问题1,952 B3,309 B极快（~0.1 ms）安全
SLH-DSA-128s哈希函数安全性32 B7,856 B慢（~10 ms）安全

ML-DSA 的签名速度实际上比 RSA 快很多，与 EdDSA 相当。代价是签名和公钥更大——但这是后量子安全的必要代价。在所有后量子签名方案中，ML-DSA 提供了安全性和性能的最佳平衡。

安全性分析
安全基础

ML-DSA 的安全性严格归约到两个数学问题：

  • Module-SIS（模格短整数解问题）：如果攻击者能伪造签名，就能解决 Module-SIS → 但 Module-SIS 被认为是困难问题 → 所以无法伪造。详见 模格密码学数学基础。
  • Module-LWE（模格学习误差问题）：拒绝采样确保签名不泄露私钥信息，因为 z 的分布接近均匀分布 → 即便收集大量签名，也无法恢复 s1。
NIST 安全级别
级别含义对应参数集
Level 1破解难度 ≥ 破解 AES-128（2128 次运算）—
Level 2破解难度 ≥ 破解 SHA-256（2192 次运算，考虑量子加速）ML-DSA-44
Level 3破解难度 ≥ 破解 AES-192（2192 次运算）ML-DSA-65
Level 5破解难度 ≥ 破解 AES-256（2256 次运算）ML-DSA-87
侧信道防护

ML-DSA 的参考实现采用了恒定时间（constant-time）编程技术：

  • 拒绝采样的判定不使用条件分支，而是通过算术掩码实现
  • 多项式乘法使用恒定时间算法（NTT 变换）
  • 不依赖内存访问模式来决定控制流

这意味着即使攻击者能够精确测量签名操作的执行时间或功耗，也无法获得任何关于私钥的信息。

已知攻击与安全裕度

截至 2026 年，针对 ML-DSA 的最佳已知攻击仍是格基归约攻击（Lattice Reduction），使用 BKZ 算法及其变体。对于 ML-DSA-65，已知的最佳攻击需要约 2180 次运算，远超 NIST Level 3 要求的 2192 安全裕度。目前没有任何利用格问题特殊结构的攻击能显著优于通用格归约。

实际部署
  • TLS 证书：Chrome、Firefox 已开始实验支持 ML-DSA 证书链
  • 代码签名：用于验证软件更新的真实性和完整性
  • 文档签名：替代 RSA/ECDSA 用于电子签名
  • 区块链：部分区块链项目正在评估 ML-DSA 用于交易签名
  • S/MIME & OpenPGP：RFC 9580 规定在 OpenPGP 中支持 ML-DSA

过渡期内推荐使用 混合签名（Composite Signatures），即同时包含经典签名（如 Ed25519）和 ML-DSA 签名，确保向后兼容。只有两种签名算法同时被攻破时签名才会失效。

与 ML-KEM (Kyber) 的关系

ML-DSA 和 ML-KEM 同属 CRYSTALS 家族，设计哲学相似：

ML-DSA（签名）ML-KEM（密钥封装）
用途数字签名（身份验证、不可否认性）密钥交换（保密性）
数学基础Module-LWE + Module-SISModule-LWE
核心技术拒绝采样（Fiat-Shamir with Aborts）Fujisaki-Okamoto 变换
私钥形式短向量 s₁, s₂短向量 s
公钥形式t = ·s₁ + s₂t = ·s + e
环Rq = Zq[X]/(X256+1)Rq = Zq[X]/(X256+1)
标准FIPS 204FIPS 203

两者使用相同的多项式环和模数，共享许多底层实现（如 NTT 变换），使得在实际系统中可以高效地同时部署两者。

深入阅读
参考文献
  1. NIST (2024). "Module-Lattice-Based Digital Signature Standard". FIPS 204.
  2. Bai, S., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D. (2018). "CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme". IACR TCHES 2018, Issue 1.
  3. Lyubashevsky, V. (2012). "Lattice Signatures Without Trapdoors". EUROCRYPT 2012, LNCS 7237, pp. 738-755.
  4. Bai, S., Galbraith, S. (2014). "An Improved Compression Technique for Signatures Based on Learning with Errors". CT-RSA 2014, LNCS 8366, pp. 28-47.
  5. Ducas, L., Prest, T. (2016). "Faster Hash-and-Sign Signatures Using a Variant of the BKZ Algorithm". IACR ePrint 2016/199.
  6. Albrecht, M.R., et al. (2023). "NIST PQC — Digital Signature Schemes Selection Report". NIST Internal Report.
加密算法导航
AES · DES/3DES · Blowfish · SM4 · ChaCha20 · RC4 · RSA · ECC · DH · SM2 · ML-KEM · ML-DSA · SLH-DSA
分类：密码学 · 后量子密码 · 数字签名 · 格密码 · NIST标准