阈值 ECDSA 签名：从 GG18 到 CGGMP20 的协议演进

概述

阈值签名（Threshold Signature）是门限密码学的重要应用，允许多个参与方共同持有签名私钥，只有达到阈值的参与方可合签，而单个参与者无法获得完整私钥。Schnorr 签名因其在群元素上的线性性质，天然支持门限化。然而，ECDSA 签名过程包含非线性的模逆运算，使其门限化成为密码学协议设计中最困难的挑战之一。

1991 年，Rabin 首次提出秘密共享概念，Shamir 在此基础上提出了拉格朗日插值方案。1996 年，Mizuki 和 Okamoto 首次研究阈值 Schnorr 签名。2005 年，Gennaro、Judson 和 Yung 提出了第一个基于多方计算的 ECDSA 门限方案，但需要 O(t²) 轮通信。2016 年，Gennaro、Goldfeder 和 Narayanan 提出了 GG18 方案，将通信轮数优化至 9 轮。2020 年，Canetti 等人提出的 CGGMP20 方案支持任意阈值且无需可信_setup_。

为什么 ECDSA 门限化比 Schnorr 困难

Schnorr 签名的线性优势

Schnorr 签名的核心公式为：

$$\sigma = k \cdot H(R \| m) + d \pmod{n}$$

其中 $R = kG$ 是随机点，$d$ 是私钥，$k$ 是一次性随机数。门限化时，每个参与方 $i$ 持有份额 $d_i$，计算部分签名：

$$\sigma_i = k_i \cdot H(R \| m) + d_i \pmod{n}$$

聚合时直接求和即可：

$$\sigma = \sum_i \sigma_i = \left(\sum_i k_i\right) \cdot H(R \| m) + \sum_i d_i \pmod{n}$$

关键在于：Schnorr 签名对私钥是线性的，份额可以直接相加。

ECDSA 的非线性瓶颈

ECDSA 签名公式包含模逆运算：

$$s = k^{-1}(H(m) + d \cdot r) \pmod{n}$$

其中 $r$ 是 $kG$ 的 x 坐标。问题在于：模逆运算破坏线性。每个参与方的份额 $d_i$ 无法直接聚合，因为：

$$k^{-1}(H(m) + \sum_i d_i \cdot r) \neq \sum_i k^{-1}(H(m) + d_i \cdot r)$$

要解决这个非线性问题，需要引入安全多方计算（MPC） 技术来安全地计算模逆运算。

GG18 方案：Gennaro-Goldfeder-Narayanan 九轮协议

设计思想

GG18（2016年）是第一个实用的 ECDSA 门限签名方案，由 Rosario Gennaro、Stanislaw Jarecki 和 Yuval Ishai 提出。该方案的核心思想是：将 ECDSA 的模逆运算分解为多个 MPC 子协议，通过安全比较和倒数计算来实现。

协议概述

GG18 协议涉及 $n$ 个参与方，阈值 $t$，使用 Shamir 秘密共享。协议分为三个阶段：

阶段一：密钥生成（Setup）

• 每个参与方 $i$ 生成 Shamir 多项式 $f_i(x)$，秘密为随机值 $a_i$
• 各方交换份额，构建共享随机数 $r$ 的加法共享
• 通过安全乘法协议计算 $[r] = [r_1] \cdot [r_2]$

签名过程需要以下 MPC 原语：

关键协议细节

SecureRecip 协议：计算 $[k^{-1}]$

• 各方使用 Beaver 三元组预计算 $[a] \cdot [b] = [c]$
• 通过公开解方程得到 $[k^{-1}]$

ECDSA 中的模运算在有限域 $\mathbb{Z}_p^*$ 上进行，其中 $p$ 为大素数。各方共享 $k$，需要通过 MPC 协议计算 $k^{-1} \pmod{p}$。

性能特征

CGGMP20 方案：可验证任意阈值签名

改进动机

GG18 存在两个主要局限：

• 需要可信 setup：密钥生成阶段需要可信第三方或多方协同完成
• 通信复杂度：O(n²) 的通信量限制了参与方规模

核心创新：Verifiable Secret Sharing

CGGMP20 使用可验证秘密共享（VSS） 替代 GG18 的 Trusted Setup：

• 每个参与方独立生成自己的 Shamir 多项式
• 通过 Feldman VSS 或 Pedersen VSS 验证份额一致性
• 无需可信第三方，任何参与方可验证其他参与方的份额

协议结构

CGGMP20 协议分为三个阶段：

阶段一：密钥生成（无可信 setup）

对于每个参与方 i：
  1. 选择随机多项式 f_i(x) = a_0 + a_1*x + ... + a_{t-1}*x^{t-1}
  2. 计算承诺 c_i,j = g^{a_j} * h^{b_j}（Pedersen 承诺）
  3. 广播所有承诺
  4. 计算份额 s_i = f_i(i)，通过 VSS 验证

阶段二：签名计算

与 GG18 类似，但使用分布式密钥生成（DKG）替代中心化 setup。

阶段三：签名验证

验证者需要验证聚合签名满足 ECDSA 验证方程：

$$R = s^{-1} \cdot H(m) \cdot G + s^{-1} \cdot r \cdot Q$$

其中 $Q$ 是公钥。

与 GG18 的对比

Lindell 方案：2 轮通信优化

Yehuda Lindell 在 2018 年提出了一个不同的思路：使用 Paillier 同态加密来加速模逆运算。

核心思想

Lindell 的方案基于以下观察：

$$k^{-1} \pmod{p} = \text{可以通过 Paillier 加密的加法同态性计算}$$

通过 Paillier 加密，各方可以在不泄露 $k$ 的情况下协作计算 $k^{-1}$。

协议流程

• 共享随机数：各方生成共享的随机数 $k$
• 安全倒数计算：使用 Paillier 加密计算 $k^{-1}$
• 签名聚合：各方的部分签名可以直接相加

性能对比

国密 SM2 阈值签名适配

SM2 与 ECDSA 的关系

SM2 签名算法与 ECDSA 在数学结构上高度相似，都使用椭圆曲线和模逆运算。主要区别在于：

SM2 阈值化的挑战

SM2 签名额外需要计算 ZA 值：

$$ZA = SM3(ENTL_A \| ID_A \| a \| b \| x_G \| y_G \| x_A \| y_A)$$

这意味着每个参与方在签名前需要知道完整的身份信息和曲线参数。在门限设置下，这要求所有参与方共享相同的 ZA 计算上下文。

适配路径

• 使用 GG18 框架：将 SM3 替代 SHA-256，将椭圆曲线参数替换为 SM2 标准曲线
• 处理 ZA 预处理：在签名计算前，所有参与方预先计算并共享 ZA 值
• 安全性分析：SM2 的 ZA 计算引入了额外的确定性，不影响门限安全性的证明

工程实践与陷阱

实现陷阱

• 随机数重用：与单签一样，门限 ECDSA 中 $k$ 的重用会导致私钥泄露
• 份额泄露：任何超过阈值的参与方合谋可以恢复私钥
• 离线攻击：恶意参与方可以故意延迟签名过程

防御措施

• 预计算机制：签名前预计算 Beaver 三元组，减少签名延迟
• 防撤销机制：引入可撤销秘密共享，防止恶意参与方获取份额
• 超时协议：设置签名超时，超时后启动重建协议

相关实践

• SM2 密钥 Shamir 门限分割实战 — SM2 密钥的 Shamir 分割工程实现
• 秘密共享与门限密码学 — 门限密码学基础概念

参考来源

• Gennaro, R., Goldfeder, S., & Narayanan, A. (2016). "Threshold-Optimal DSA/ECDSA Signatures and an Application to Bitcoin Wallet Security." *Lecture Notes in Computer Science*, 9696, 156-174.
• Canetti, R., Gennaro, R., Goldfeder, S., Makriyannis, N., & Peled, U. (2020). "UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts." *Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (CCS)*, 1769-1787.
• Lindell, Y. (2017). "Fast Secure Two-Party ECDSA Signing." *Advances in Cryptology – CRYPTO 2017*, Lecture Notes in Computer Science, 10403, 155-185.
• GM/T 0003.2-2012《SM2 椭圆曲线公钥密码算法第 2 部分：数字签名算法》
• GM/T 0009-2023《SM2 密码算法使用规范》