FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG

Each language version is independently generated for its own context, not a direct translation.

这是一篇关于后量子密码学（Post-Quantum Cryptography）的重要技术论文。为了让你轻松理解，我们将把复杂的数学概念转化为生活中的故事和比喻。

🌟 核心故事：如何安全地“集体签字”？

想象一下，一家大银行（或者国家）有一把超级金钥匙，用来签署所有的巨额交易。为了安全，他们不想让这把钥匙放在一个人手里（怕被偷或内部作恶），也不想放在一个保险柜里（怕被黑客攻破）。

于是，他们决定把钥匙切碎，分给 100 个人（比如 100 个高管）。规则是：只要其中任意 32 个人（T=32）聚在一起，就能把碎片拼起来，完成签字。少于 32 个人，哪怕有 31 个，也拼不出任何东西，甚至不知道钥匙长什么样。

这就是阈值签名（Threshold Signature）。

🚨 以前的难题：量子计算机来了怎么办？

现在的数字签名（像 ECDSA）很安全，但未来的量子计算机能轻易破解它们。美国国家标准与技术研究院（NIST）刚刚发布了一个新标准 FIPS 204（基于 ML-DSA），这是专门用来对抗量子计算机的“新锁”。

问题在于：
以前的“集体签字”技术（针对旧锁）很成熟，但针对这个“新锁”（ML-DSA）的集体签字方案一直很难做。

要么太慢：需要很多人反复沟通，像开会一样，效率极低。
要么太笨重：签出来的文件巨大无比（比如从 3KB 变成 17KB），现有的系统根本读不懂。
要么门槛太高：以前有些方案要求“诚实的人必须比坏人多”，或者要求“除了凑齐人数外，还得额外多几个好人”，这在实际操作中很难满足。

💡 这篇论文的突破：Shamir 随机数分发（Shamir Nonce DKG）

作者 Leo Kao 提出了一种全新的方法，就像给“集体签字”装上了一个智能的“随机数生成器”。

1. 核心比喻：切蛋糕与拼图

旧方法：大家各自切蛋糕（生成随机数），然后试图拼起来。如果拼的时候有人捣乱，或者切得大小不一，整个蛋糕就废了（签字失败）。
新方法（Shamir Nonce DKG）：
- 想象大家手里都拿着一张神秘的图纸（多项式）。
- 每个人不直接告诉别人自己的“蛋糕切法”，而是根据图纸，各自切出一小块碎片（Nonce Share）。
- 神奇的是，只要凑齐 32 个人，这些碎片就能自动拼成一个完美的、随机的“大蛋糕”（最终的随机数）。
- 关键点：即使坏人控制了 31 个人，他们看着手里那 31 块碎片，也完全猜不出第 32 块碎片是什么，甚至猜不出整个大蛋糕长什么样。这就像一次一密（One-Time Pad），提供了极高的数学安全性，不需要依赖“计算机算不出来”的假设，而是基于“信息论”的绝对安全。

2. 为什么它这么厉害？

标准尺寸：它生成的签名，和单个人签名的格式一模一样（都是 3.3KB）。这意味着现有的银行系统、区块链节点、政府系统，不需要修改任何代码就能直接接受这种集体签名。就像你换了一把新锁，但钥匙孔的大小没变，原来的锁匠也能用。
任意人数：以前有些方案只能支持很少的人（比如最多 6 个），这个方案支持任意数量（从 3 人到 45 人甚至更多）。
不需要“好人多”：在特定的部署模式下，只要凑齐规定的人数（比如 32 人）就能签字，不需要额外多几个“好人”来凑数。

🛠️ 三种“作战模式”（部署方案）

为了适应不同的场景，作者设计了三种模式：

模式 P1（有“ trusted 管家”）：
- 场景：公司有一个高度安全的硬件保险箱（TEE/HSM）。
- 做法：大家把碎片发给这个保险箱，由它来拼凑和检查。
- 优点：速度最快（约 6 毫秒），像闪电一样快。
- 缺点：你得信任这个保险箱没坏。
模式 P2（完全去中心化）：
- 场景：没有可信的第三方，大家互不信任（比如区块链节点）。
- 做法：大家通过复杂的“暗语”（多方计算 MPC）互相沟通，谁也不知道别人的秘密。
- 优点：最安全，不需要信任任何硬件。
- 缺点：稍微慢一点（约 20-200 毫秒），因为沟通轮次多。
模式 P3+（半异步模式，最人性化）：
- 场景：需要人类参与审批（比如 CEO 签字）。CEO 可能很忙，不能一直在线。
- 做法：CEO 可以提前把碎片准备好（离线预计算）。当需要签字时，只要他在 5 分钟内回复一下就行，不需要和其他人同时在线开会。
- 优点：体验最好，像发微信一样方便，且速度快。

📊 性能表现：快得像什么？

速度：在普通电脑上，3 个人凑齐签字只需要 6 毫秒（P1 模式），或者 22 毫秒（P3+ 模式）。这比眨眼还快（眨眼约 100-400 毫秒）。
成功率：以前大家担心这种复杂的数学计算会经常失败，但作者发现，因为使用了特殊的数学分布（Irwin-Hall 分布），成功率反而比单个人签字还要高一点（21% - 45% 的成功率，意味着平均试 3 次就能成功）。
扩展性：即使人数增加到 32 人，速度依然保持在 100 毫秒以内，完全实用。

🛡️ 安全性：为什么量子计算机也怕它？

抗量子：基于 FIPS 204 标准，专门设计用来抵抗量子计算机的攻击。
隐私保护：即使坏人控制了大部分参与者，他们也无法从签字过程中反推出私钥。
数学证明：作者不仅给出了代码，还给出了严格的数学证明（UC 安全证明），证明这个方案在理论上是无懈可击的。

🎯 总结：这对我们意味着什么？

这篇论文就像是为未来的数字世界打造了一套通用的、安全的、高效的“集体签字”系统。

对于企业：你可以放心地把私钥分给多个部门管理，防止内部腐败或外部黑客。
对于区块链：可以让去中心化组织（DAO）更安全地管理资产，且不需要修改现有的节点软件。
对于政府：可以建立抗量子攻击的数字证书体系，保护国家关键基础设施。

一句话总结：
作者发明了一种既快又安全、且完全兼容现有系统的“多人合作签字”新方法，让未来的数字世界在面对量子计算机威胁时，依然能像现在一样安全、高效地运转。

Each language version is independently generated for its own context, not a direct translation.

1. 研究背景与问题 (Problem)

随着量子计算机的临近，NIST 发布了 FIPS 204 标准，确立了基于格的 ML-DSA (Module-Lattice-Based Digital Signature Algorithm) 作为后量子数字签名标准。然而，现有的阈值签名方案在应用于 ML-DSA 时面临巨大挑战，存在显著的“阈值缺口”（Threshold Gap）：

FIPS 204 兼容性难题：ML-DSA 采用“带中止的 Fiat-Shamir"范式，签名有效性依赖于响应向量 $z = y + c \cdot s_1$ 满足范数约束 $\|z\|_\infty < \gamma_1 - \beta$ 。在阈值设置中，若直接对秘密密钥份额进行线性重组，拉格朗日系数（Lagrange coefficients）通常非常大（随阈值 $T$ 指数增长），导致部分响应 $z_i$ 的范数过大，无法满足拒绝采样（Rejection Sampling）的约束，从而使得签名几乎必然失败。
现有方案的局限性：
- 短系数 LSSS 方案（如 del Pino-Niot）：受限于拉格朗日系数必须小于模数 $q$ 的约束，仅能支持极小的阈值（ $T \le 6$ 或 $T \le 8$ ），无法满足实际应用中 $T \in [9, 32]$ 的需求。
- 噪声淹没（Noise Flooding）方案：虽然支持任意阈值，但会引入巨大的统计噪声，导致签名尺寸膨胀至约 17KB（标准 ML-DSA 为 3.3KB），破坏了 FIPS 204 的格式兼容性。
- 专用构造：如 Ringtail，虽然效率高，但生成的签名格式无法被标准 FIPS 204 验证器识别，无法直接部署。
核心痛点：目前缺乏一种既能支持任意阈值、又能生成标准尺寸（3.3KB）签名、且无需计算假设即可保证随机数份额隐私的 ML-DSA 阈值方案。

2. 方法论 (Methodology)

作者提出了一种名为 Shamir Nonce DKG 的新颖架构，结合**成对抵消掩码（Pairwise-Canceling Masks）**技术，解决了上述问题。

核心技术创新：

Shamir 随机数分布式密钥生成 (Shamir Nonce DKG)：
- 结构匹配：传统的阈值签名通常对长期私钥 $s_1$ 使用 Shamir 秘密共享，但对随机数 $y$ 使用简单的加法共享。本文创新性地让参与方共同生成一个次数为 $(T-1)$ 的 Shamir 多项式来生成随机数 $y$ 。
- 无需拉格朗日系数缩放：每个参与方计算局部响应 $z_i = y_i + c \cdot s_{1,i}$ ，不乘以拉格朗日系数 $\lambda_i$ 。
- 聚合机制：组合器（Combiner）在聚合阶段应用拉格朗日系数： $z = \sum \lambda_i z_i = \sum \lambda_i y_i + c \sum \lambda_i s_{1,i} = y + c \cdot s_1$ 。
- 优势：由于 $y$ 和 $s_1$ 都是同次数的 Shamir 多项式，拉格朗日插值在加法上具有分配律。这使得单个参与方的 $z_i$ 保持短范数（满足 $\|z_i\|_\infty \le \lceil \gamma_1/|S| \rceil + \beta$ ），避免了系数放大导致的拒绝采样失败。
随机数份额隐私 (Nonce Share Privacy)：
- 利用 Shamir 多项式的性质，攻击者最多只能观察到 $T-1$ 个评估点。对于诚实参与方的多项式，剩余的一个自由度提供了近似“一次性密码本”的效果。
- 无条件隐私：证明了在 $|S| \le 17$ 时，诚实参与方的随机数份额具有超过私钥熵 5 倍的条件最小熵（Conditional Min-Entropy）。这不需要任何计算假设（如 LWE 困难性），仅基于统计性质。
- 打破“两诚实”假设：在基于协调员的配置（P1, P3+）中，仅需 $|S| \ge T$ 即可实现隐私，而传统方案通常要求 $|S| \ge T+1$ 。
成对抵消掩码 (Pairwise-Canceling Masks)：
- 用于隐藏承诺值 $W_i$ 和 $r_0$ -检查份额 $V_i$ （包含 $c \cdot s_2$ 的信息）。
- 利用预共享的种子和 PRF 生成掩码，使得 $\sum m_i = 0$ 。这防止了攻击者通过广播的中间值恢复 $c \cdot s_2$ ，进而恢复私钥 $s_2$ （因为 ML-DSA 的挑战 $c$ 几乎总是可逆的）。
Irwin-Hall 分布与安全性分析：
- 聚合后的随机数 $y$ 服从 Irwin-Hall 分布（多个均匀分布之和），而非均匀分布。
- 作者通过**直接移位不变性分析（Direct Shift-Invariance Analysis）**证明，这种分布带来的安全损失极小（每会话 $< 0.013$ 比特），远优于保守的 Raccoon 风格界限，消除了以往工作中的可扩展性差距。

3. 三种部署配置 (Deployment Profiles)

论文定义了三种具有不同信任假设的部署配置，均提供了完整的 UC（通用组合）安全证明：

Profile P1 (TEE 辅助)：
- 架构：使用可信执行环境（TEE/HSM）作为协调员。
- 流程：协调员在安全 enclave 内执行 $r_0$ -检查和提示生成。
- 优势：仅需 3 轮在线交互，延迟最低（3-of-5 配置下约 5.8ms）。
- 信任：依赖 TEE 完整性。
Profile P2 (完全分布式 MPC)：
- 架构：无硬件信任，完全基于多方计算（MPC）。
- 技术：使用 SPDZ 和 edaBits 协议在 MPC 内部计算 $r_0$ -检查，不重建 $c \cdot s_2$ 。
- 优势：支持**恶意敌手下的非诚实多数（Dishonest-Majority）**安全，支持任意阈值。
- 性能：5 轮在线交互（3-of-5 配置下约 21.5ms）。
Profile P3+ (半异步 2PC)：
- 架构：专为“人机交互”授权设计。两个计算方（CP）通过轻量级 2PC 执行检查，签名方半异步参与。
- 流程：签名方可离线预计算随机数，在收到挑战后的时间窗口内（如 5 分钟）响应。
- 优势：仅需 2 个逻辑轮次（1 轮签名方 + 1 轮服务器），极大降低了网络延迟敏感场景的延迟（3-of-5 配置下约 22.1ms）。

4. 主要结果 (Results)

性能表现：
- 延迟：在 Rust 实现中，从 2-of-3 到 32-of-45 的阈值配置，P1 和 P3+ 的延迟均保持在 100ms 以下（P1 约 4-60ms，P3+ 约 17-94ms）。P2 因 MPC 开销略高（21-194ms），但消除了硬件信任。
- 成功率：由于 Irwin-Hall 分布比均匀分布更集中在零附近，阈值签名的成功率（21%-45%）甚至略高于或等同于单签名 ML-DSA 的基准（20%-25%）。
- 扩展性：支持高达 32 个参与方，且签名尺寸严格保持 3.3 KB（ML-DSA-65），与标准 FIPS 204 验证器完全兼容。
安全性证明：
- 不可伪造性 (EUF-CMA)：归约到 Module-SIS 问题，安全损失极小（ $< 0.013 \times q_s$ 比特）。
- 隐私性：随机数份额隐私是统计性的（无条件），无需计算假设。
- UC 安全：所有三种配置均提供了针对静态恶意敌手的 UC 安全证明。
对比优势：
- 与现有工作（如 Bienstock et al., Celi et al.）相比，本方案是唯一同时满足任意阈值、FIPS 204 兼容、非诚实多数安全（P2）、常数轮次且无条件随机数隐私的方案。

5. 意义与影响 (Significance)

填补关键空白：解决了 FIPS 204 标准化后，阈值签名领域长期存在的“阈值缺口”问题，使得在 $T \in [9, 32]$ 范围内的实际应用场景（如企业密钥管理、分布式 CA、加密货币托管）能够安全、高效地迁移到后量子时代。
无需妥协的兼容性：生成的签名在格式和大小上与单签名 ML-DSA 完全一致，无需修改现有的验证基础设施，实现了“即插即用”的部署。
理论突破：提出的 Shamir Nonce DKG 技术为基于格的阈值签名提供了一种新的范式，即通过匹配随机数和私钥的多项式结构来避免拉格朗日系数放大问题，并实现了无计算假设的随机数隐私。
工程落地：提供了经过优化的 Rust 实现，证明了该方案在工业级硬件上的可行性，为后量子密码学的实际部署铺平了道路。

总结：该论文提出了一种高效、安全且完全兼容 FIPS 204 的 ML-DSA 阈值签名方案，通过创新的 Shamir 随机数生成机制，克服了格密码在阈值设置中的核心障碍，为后量子时代的分布式信任系统提供了关键的基础设施。