Multiparty Threshold ECDSA (CMP, CGGMP)

1. 简介
- 1.1. 标准 ECDSA
2. GG18 回顾
- 2.1. 仅需 4 rounds（不考虑恶意参与者）
3. CMP/CGGMP
4. 参考

1. 简介

本文介绍论文 UC Non-Interactive, Proactive, Threshold ECDSA（按作者名字缩写一般简称 CMP20 或 CMP 协议），和论文 UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts（按作者名字缩写一般简称 CGGMP21 或 CGGMP 协议）中提出的多方 ECDSA 门限签名协议。

从论文的名称中容易知道，这两个协议的主要区别在于 CGGMP 协议支持识别恶意参与者，而 CMP 协议不支持。

1.1. 标准 ECDSA

设 $m$ 是待签名的消息的哈希值， $m = Hash(msg)$ ， $x$ 是私钥（公钥记为 $g^{x}$ ，这种记法和 CMP/CGGMP 论文中记法一致，其它论文一般记椭圆曲线公钥为 $x G$ ，这里没有采用这种记法）， $k$ 是由签名者随机生成的一次一用的随机数。

签名数据可记为 $(r, σ)$ ，其中 $r$ 是点 $R = g^{k^{- 1}}$ 的 $x$ 轴坐标， $σ ≜ k (m + r x)$ 。

2. GG18 回顾

CMP/CGGMP 协议和 GG18 协议有很深的渊源，CGGMP 论文的五个作者就是 CMP 论文的三个作者加上 GG18 论文的两个作者。节 3.2.1 会介绍 CMP/CGGMP 协议和 GG18 协议的主要区别。

下面简单总结一下 GG18 签名协议。需要说明的是，下面的记号风格和 CMP/CGGMP 论文一致，和 GG18 论文不同（如下面的记号 $χ_{i}, σ_{i}$ 的含义分别对应于 GG18 论文中的 $σ_{i}, s_{i}$ 的含义）。

求签名 $r$ （即 $R$ 的 $x$ 坐标）的思路。 $\begin{aligned} R & = g^{k^{- 1}} \\ = g^{γ γ^{- 1} k^{- 1}} \\ = g^{(\sum γ_{i}) γ^{- 1} k^{- 1}} \\ = {(g^{(\sum γ_{i})})}^{(γ k)^{- 1}} \\ = {(\prod g^{γ_{i}})}^{(γ k)^{- 1}} \end{aligned}$ 每个参与者都随机产生 $k_{i}$ 和 $γ_{i}$ ，它们分别是 $k$ 和 $γ$ 的 Additive Share，即 $k = \sum k_{i}, γ = \sum γ_{i}$ 。问题的关键在于每个参与者不泄露 $k_{i}$ 和 $γ_{i}$ 情况下，如何求得 $γ k$ ，思路是把乘积 $γ k$ 转换为 $γ k$ 的 Additive Share 的形式，每个参与者都可以得到其中的一个 Additive Share，记为 $δ_{i}$ ，即有 $\sum δ_{i} = γ k$ ，这样，每个参与者把自己的 $δ_{i}$ 公开给其它参与者，这样所有参与者都可以计算出 $γ k$ 了。

求签名 $σ$ 的思路（记 $χ ≜ k x$ ， $σ_{i} ≜ k_{i} m + χ_{i} r$ ）是把 $σ$ 拆分为 Additive Share，每个参与者计算一个 Additive Share，记为 $σ_{i}$ 。具体如下： $\begin{aligned} σ & = k (m + x r) \\ = k m + χ r \\ = (\sum k_{i}) m + (\sum χ_{i}) r \\ = \sum σ_{i} \end{aligned}$ 其中的难点是每个参与者不泄露 $k_{i}, x_{i}$ 情况下，如何求得 $k x$ ，方法和前面介绍的类似，把乘积 $k x$ 转换为 $k x$ 的 Additive Share 的形式，每个参与者都可以得到其中的一个 Additive Share $χ_{i}$ ，这样每个参与者可以计算一个 $σ_{i}$ ，每个参与者把自己的 $σ_{i}$ 公开给其它参与者，这样所有参与者都可以计算出 $σ$ 了。

总结： 每个参与者如何求解 $δ_{i}$ 和 $χ_{i}$ 是 GG18 签名协议中最关键的地方。

2.1. 仅需 4 rounds（不考虑恶意参与者）

如果不考虑恶意参与者，则 GG18 的签名协议只需要 4 个 rounds（前 3 个 rounds 和待签名数据 $m$ 无关，到第 4 个 round 时，才需要待签名数据 $m$ ）。

通过前 3 个 rounds 可以求出 $δ_{i}$ 和 $χ_{i}$ （如果想更细节地理解 $δ_{i}$ 和 $χ_{i}$ 的求解，建议参考：https://aandds.com/blog/multiparty-threshold-ecdsa.html ），如图 1（摘自 CGGMP 4.1 Presigning）所示。

Figure 1: 不考虑恶意参与者，GG18 只需要 3 rounds 可以求解 $δ_{i}$ 和 $χ_{i}$

第 4 个 round 时，每个参与者收到了其它参与者公开了 $δ_{i}$ ，从而可以求出 $r$ ，又由于在第 3 round 时已经计算出了 $χ_{i}$ ，所以第 4 round 时利用 $σ_{i} ≜ k_{i} m + χ_{i} r$ 就可以求出 $σ_{i}$ ，每个参与者公开 $σ_{i}$ ，所有参与者都可以求出最终签名数据 $σ = \sum σ_{i}$ 。

为了能够抵抗恶意参与者，GG18 的签名协议总共需要 9 rounds。 抵抗恶意参与者导致 GG18 额外增加了 5 个 rounds。

3. CMP/CGGMP

3.1. Key Generation

CMP/CGGMP 论文中介绍的 DKG 算法，是一种 n/n 方案，并不是更通用的 t/n 方案。论文中是这样交待的：

In this work we mainly focus on n-out-of-n multi-party signing, and do not explicitly consider the more general t-out-of-n threshold signing for t < n. Such a protocol can be derived almost immediately from our protocol herein for the online variant using Shamir secret-sharing, with relevant changes to the protocol’s components, similarly to Gennaro and Goldfeder.

Keygen 过程中参与者除了生成私钥分片外，还要生成下面参数：

Paillier 密钥对（私钥自己保留，公钥发送给其他参与者）；签名过程中 MtA 子协议中需要它。
Ring-Pederson 参数 $(N, s, t)$ ；MtA 子协议的 Range Proof 中需要这些参数。它们就是 GG18 论文中提到的参数 $(\tilde{N}, h_{1}, h_{2})$ 。
ElGamal 密钥对（私钥自己保留，公钥发送给其他参与者）；ElGamal 密钥对只有当签名采用“6 rounds Pre-Signing 加 1 round Signing”的方案（这种方案识别恶意参与者的效率更高，仅在 CGGMP 论文中介绍了这个方案，在 CMP 论文中没有）时才需要它，如果签名采用“3 rounds Pre-Signing 加 1 round Signing”的方案（CGGMP 论文和 CMP 论文都有这个方案）则不需要它。

3.2. Signing

在介绍 CMP/CGGMP 签名协议之前，先介绍一下 GMW compiler。

GMW compiler 是一种将 Semi-Honest MPC 协议转换为 Malicious MPC 协议的通用方法。GMW Compiler 的基本思路是：先设计一个 Semi-Honest MPC 协议，然后对每一步引入零知识证明以确保参与者忠实地执行协议，这样就把 Semi-Honest MPC 协议改造成了 Malicious MPC 协议。

3.2.1. CMP/CGGMP 思路

CMP/CGGMP 协议采用了 GMW compiler 的思路。前面介绍的 GG18 4 rounds 协议是一个 Semi-Honest MPC 协议，通过在每步计算中引入零知识证明以确保参与者忠实地执行协议，从而得到一个 Malicious MPC 协议，这就是 CMP/CGGMP 协议的主要思路。

3.2.2. CGGMP 签名（3 rounds Pre-Signing）和（1 round Signing）

CGGMP 签名协议如图 2 和图 3 所示（摘自 CGGMP 4.3 Signing），总共是 4 rounds。其中前 3 rounds 不需要待签名消息，可以提前进行；最后 1 round 才需要待签名消息。 这 4 rounds 和节 2.1 中介绍的 GG18 协议的 4 rounds 可以一一对应，不过是每个 rounds 中额外增加了很多零知识证明以确保参与者忠实地执行协议。

Figure 2: CGGMP Pre-Signing（3 rounds）

Figure 3: CGGMP Signing（1 round）

注 1：CMP 论文中的签名协议也是 4 rounds，和上面介绍的 CGGMP 4 rounds 签名协议的主要过程基本相同。
注 2：CGGMP 论文中还介绍一种 7 rounds（前 6 rounds 不需要待签名消息，可以提前进行）的签名协议，它识别恶意参与者的效率更高，这里不介绍。

3.2.3. 一些零知识证明

3.2.3.1. $\prod^{enc}$

Paillier Encryption in Range: $R_{enc} = {(N_{0}, I, C; x, ρ) ∣ x \in I \land C = (1 + N_{0})^{x} ρ^{N_{0}} \in Z_{N_{0}^{2}}^{*}}$

上面关系记号中， $(N_{0}, I, C; x, ρ)$ 中分号前面的数据是公开数据（即 $N_{0}, I, C$ 是公开数据），而分号后面的数据是私密数据（即 $x, ρ$ 是私密数据）。记号 $\land$ 是“与”的意思，也就是说上面关系记号表示要同时满足下面两个约束：

$x$ 在范围 $I$ 中，即 $x \in I$
$x$ 的 Paillier 密文是 $C$ ，即 $C = (1 + N_{0})^{x} ρ^{N_{0}} \in Z_{N_{0}^{2}}^{*}$

为关系 $R_{enc}$ 生成的零知识证明可记为 $\prod^{enc}$ ，这个零知识证明的具体过程如图 4 所示（参考 CGGMP 论文的 6.1 Paillier Encryption in Range ZK）。

Figure 4: Paillier Encryption in Range ZK – $\prod^{enc}$

3.2.3.2. $\prod^{aff-g}$

Paillier Affine Operation with Group Commitment in Range: $\begin{aligned} R_{aff-g} = {({PUB}_{2}, I, J, C, C_{0}, Y, X; ε, δ, r, ρ) ∣ & ε \in I \\ \land δ \in J \\ \land C = C_{0}^{ε} (1 + N_{0})^{δ} r^{N_{0}} \in Z_{N_{0}^{2}}^{*} \\ \land Y = (1 + N_{1})^{δ} ρ^{N_{1}} \in Z_{N_{1}^{2}}^{*} \\ \land X = g^{ε}} \end{aligned}$
其中 ${PUB}_{2} = (G, g, N_{0}, N_{1})$ 是公开参数。

这个关系需要满足上面式子中提到的 5 个约束，我们重点关注一下第 3 个约束，即 $C = C_{0}^{ε} \underset{Ciphertext of δ}{\underset{⏟}{(1 + N_{0})^{δ} r^{N_{0}}}} \in Z_{N_{0}^{2}}^{*}$ 。为什么要有这么一个奇奇怪怪的约束呢？回答这个问题前，先需要了解 Paillier 的加同态加密的两个特性：

假设 $k$ 的 Paillier 密文是 $C_{0}$ ，则在密文 $C_{0}$ 上进行指数运算得到 $C_{0}^{ε}$ ，这个结果是 $k ε$ 的 Paillier 密文；
假设 $x_{1}, x_{2}$ 的 Paillier 密文是 $X_{0}, X_{1}$ ，则在密文 $X_{0}, X_{1}$ 上进行乘法运算 $X_{0} X_{1}$ ，这个结果是 $x_{1} + x_{2}$ 的 Paillier 密文。

也就是说第 3 个约束表达的意思是： 如果 $k$ 的 Paillier 密文是 $C_{0}$ ，则 $C = C_{0}^{ε} (1 + N_{0})^{δ} r^{N_{0}}$ 一定是 $k ε + δ$ 的 Paillier 密文，这可用于 MtA 协议。

为关系 $R_{aff-g}$ 生成的零知识证明可记为 $\prod^{aff-g}$ ，这个零知识证明的具体过程如图 5 所示（参考 CGGMP 论文的 6.2 Paillier Operation with Group Commitment in Range ZK）。

cmp_cggmp_zk_paillier_affine_op_with_group_commit_in_range.gif

Figure 5: Paillier Operation with Group Commitment in Range ZK - $\prod^{aff-g}$

3.2.3.3. $\prod^{log*}$

Dlog vs Paillier Encryption in Range: $\begin{aligned} R_{log*} = {({PUB}_{1}, I, C, X, g; x, ρ) ∣ & x \in I \\ \land C = (1 + N_{0})^{x} ρ^{N} \in Z_{N^{2}}^{*} \\ \land X = g^{x}} \end{aligned}$
其中 ${PUB}_{1} = (G, N)$ 是公开参数。

关系 $R_{log*}$ 比前面介绍的 $R_{enc}$ 来说，只多了一个约束，即 $X = g^{x}$ 。

为关系 $R_{log*}$ 生成的零知识证明可记为 $\prod^{log*}$ ，这个零知识证明的具体过程如图 6 所示（参考 CGGMP 论文的 C.2 Group Element vs Paillier Encryption in Range ZK）。

Figure 6: Knowledge of Exponent vs Paillier Encryption – $\prod^{log*}$

3.3. 关于 Broadcast 消息

协议中很多地方都提到了参与者把某消息 Broadcast 给其它参与者，这其中隐含的含义是：存在一个“可靠的广播通道”，往这个广播通道发送消息时，所有参与者都能收到消息，而且是收到相同的消息。

但在真正环境中，没有这样的“可靠的广播通道”，往往只有 Point-to-Point 网络。恶意参与者通过 Point-to-Point 网络发送 Broadcast 消息时，可能往不同的参与者发送不同的消息。这种攻击在 CMP/CGGMP 论文中并没有考虑。不过，在 CMP/CGGMP 论文 3.1 节中的“Remark 3.2”中，对 Broadcast 消息进行了说明：

We observe that the protocol instructs the parties to (verifiably) broadcast some of their messages (as opposed to messages which are “sent to all”, where equality verification is not required). For non-unanimous halting [see Secure Computation Without Agreement], this can be achieved in a point-to-point network using echo-broadcasting with one extra round of communication.

也就是， CMP/CGGMP 论文建议读者采用 Secure Computation Without Agreement 中的提到的 Echo-Broadcast Protocol（如图 7）在 Point-to-Point 网络中实现可靠地广播。

Figure 7: Echo-Broadcast Protocol 可实现在 Point-to-Point 网络中可靠地广播消息

下面以 $P_{1}$ 想发送广播消息给 $P_{2}, P_{3}$ 为例，介绍下图 7 的思路：当参与者 $P_{2}, P_{3}$ 收到 $P_{1}$ 发来的广播消息时，参与者 $P_{2}, P_{3}$ 不直接接受这个广播消息，而是把这个消息转发给其它参与者。这样，如果 $P_{2}$ 收到的来自 $P_{1}$ 的广播消息和通过 $P_{3}$ 转发的 $P_{1}$ 广播消息相同，那么 $P_{2}$ 就接受 $P_{1}$ 的广播消息。类似地， $P_{3}$ 也一样。

3.4. 开源实现

下面是 CMP/CGGMP 协议的一些开源实现：