Multiparty Threshold ECDSA (DKLS19)

1. 简介
- 1.1. 标准 ECDSA
2. DKLS19 主要思路
- 2.1. DKLS19 协议
3. MtA with Oblivious Transfer
- 3.1. Gil99 (OT-based MtA)
- 3.2. 特点：Light Computation, Heavy Bandwidth
4. 参考

1. 简介

2019 年，Jack Doerner, Yashvanth Kondi, Eysa Lee, and Abhi Shelat 在论文 Threshold ECDSA from ECDSA Assumptions: The Multiparty Case 中提出的多方 ECDSA 门限签名方案，简称 DKLS19 协议，本文将讨论它。

注 1：还有一个名为 DKLS18 的协议，它是 2018 年同样这 4 个作者在论文 Secure Two-party Threshold ECDSA from ECDSA Assumptions 中提出的协议，它是一个两方的 ECDSA 门限签名方案。
注 2：还有一个名为 DKLS23 的协议，它是 2023 年同样这 4 个作者在论文 Threshold ECDSA in Three Rounds 中提出的协议。

1.1. 标准 ECDSA

设 \(m\) 是待签名的消息， \(H(m)\) 是待签名消息的哈希， \(sk\) 是私钥， \(k\) 是由签名者随机生成的一次一用的随机数。

签名数据可记为 \((\text{sig}, r_x)\) ，其中 \(r_x\) 是点 \(R = k \cdot G\) 的 \(x\) 轴坐标， \(\text{sig}\) 由下式确定 \[\text{sig} \triangleq \frac{H(m) + sk \cdot r_x}{k}\]

2. DKLS19 主要思路

假设参与者集合为 \(\mathbf{P}\) ，其中 \(\vert \mathbf{P} \vert = t\) ，也就是说一共有 \(t\) 个参与者进行 ECDSA 门限签名。

DKLS19 主要思路：

Multiplication and Inversion. \(t\) 个参与者执行一个 “inverse-sampling” 协议（ \(\mathcal{F}_{\text{Inv}}^{n,t}\) ），在协议结束后，每个参与者可得到 \(k\) 的 additive sharing（即每个参与者可得到 \(k_i\) ，会满足 \(\sum_{i \in \mathbf{P}} k_i = k\) ），得到 \(1/k\) 的 additive sharing（即每个参与者可得到 \(v_i\) ，会满足 \(\sum_{i \in \mathbf{P}} v_i = 1/k\) ），以及得到 \(R=k \cdot G\) 。然后每个参与者由 \(sk\) 的 additive sharing 和 \(1/k\) 的 additive sharing 进行一个类似于 GMW 乘法的协议可得到 \(sk * (1/k)\) 的 additive sharing（即每个参与者自己手头有 \(sk_i\) 和 \(v_i\) ，经过协议可以得到 \(w_i\) ，会满足 \(\sum_{i \in \mathbf{P}} w_i = sk/k\) ）。
Consistency Check. 为了确保参与者忠实地执行上一步的协议，我们要进行一些一致性的检查。如果有参与者违法协议，则可以被发现。
Signing. 如果 Consistency Check 阶段没有发现问题，则我们可以说 \(\mathbf{P}\) 中每个参与者得到的 \(v_i,w_i,R\) 确实会满足： \[\sum_{i \in \mathbf{P}} v_i = 1/k, \qquad \sum_{i \in \mathbf{P}} w_i = sk/k, \qquad R = k\cdot G\] 每个参与者进行本地计算 \[\text{sig}_i \triangleq v_i \cdot H(m) + w_i \cdot r_x\] 然后把它广播给其它参与者，这样每个参与者按下面式子可以得到最终的签名 \[\text{sig} \triangleq \sum_{i \in \mathbf{P}} \text{sig}_i\]

我们容易验证这种方式得到的 \(\text{sig}\) 和标准 ECDSA 的 \(\text{sig}\) 是一样的，验证如下： \[\begin{aligned} \sum_{i \in \mathbf{P}} \text{sig}_i & = \sum_{i \in \mathbf{P}} \left(v_i \cdot H(m) + w_i \cdot r_x \right) \\ & = \left(\sum_{i \in \mathbf{P}} v_i \right) \cdot H(m) + \left(\sum_{i \in \mathbf{P}} w_i \right) \cdot r_x \\ &= \frac{1}{k} \cdot H(m) + \frac{sk}{k} \cdot r_x \end{aligned}\]

如何让各个参与者得到 \(v_i\) 和 \(w_i\) 是求解 \(\text{sig}\) 的难点。

2.1. DKLS19 协议

原论文中对 DKLS19 协议的描述如图 1 所示。

Figure 1: DKLS19

在 DKLS19 协议的 Multiplication and Inversion 阶段中，在两个重要的子协议 \(\mathcal{F}_{\text{Inv}}^{n,t}\) 和 \(\mathcal{F}_{\text{2PMul}}^{l}\) ，本文不打算详细介绍它们，感兴趣的读者可阅读原论文。本文后面会介绍一个更基础的协议 MtA，它是子协议 \(\mathcal{F}_{\text{Inv}}^{n,t}\) 和 \(\mathcal{F}_{\text{2PMul}}^{l}\) 的基础。

3. MtA with Oblivious Transfer

Alice 手头有个秘密 \(a\) ，Bob 手头有个秘密 \(b\) ，如何设计一个协议让 Alice 得到另一个值 \(x\) ，Bob 得到另一个值 \(y\) ，且满足 \(x+y= ab\) 。这个协议可以称为 Multiplicative-to-Additive（简称 MtA），它是 ECDSA 门限签名的一个关键子协议，在著名的 ECDSA 门限签名协议 GG18 协议中，是使用 Paillier 同态加密来实现 MtA 的。

在 DKLS19 中，并没有使用 Paillier 同态加密来实现 MtA，而是使用 Oblivious Transfer（OT）来实现 MtA，其思想来源于 1999 年 Niv Gilboa 发表的论文 Two Party RSA Key Generation（Gil99）。

3.1. Gil99 (OT-based MtA)

假设 \(a\) 和 \(b\) 分别是 Alice 和 Bob 手头的秘密值，它们的比特位长度是 \(\rho\) ，记 \(a\) 可以表示为二进制数 \(a_{\rho-1},\cdots,a_1,a_0\) ，也就是说 \(a\) 可以表示为 \(a=\sum_{i=0}^{\rho-1}a_i \cdot 2^i\) 。

Gilboa 设计了下面协议可以让 Alice 得到 \(x\) ，Bob 得到 \(y\) ，且满足关系 \(x+y= ab\) ：

Bob 随机选择 \(\rho\) 个数 \(s_0,s_1,\cdots,s_{\rho-1}\) ，Bob 定义 \(2\rho\) 个数 \(t_i^0 \triangleq s_i, t_i^1 \triangleq 2^ib + s_i\) ，其中 \(0 \le i \le \rho-1\) ；
Alice 和 Bob 执行 \(\rho\) 个 1-out-of-2 OT 协议。在第 \(i\) 个 1-out-of-2 OT 协议中，Bob 发送两个数 \(t_i^0,t_i^1\) ，而 Alice 根据 \(a_i\) 的值，从中选择 \(t_i^{a_i}\) ；
Alice 设置 \(x \triangleq \sum_{i=0}^{\rho-1} t_i^{a_i}\) ，Bob 设置 \(y \triangleq - \sum_{i=0}^{\rho - 1} s_i\) 。

上面描述的协议可以表示为图 2 所示。

Figure 2: Gil99 (OT-based MtA)

下面来证明一下，为什么 \(x+y = ab\) 会成立。

\[\begin{aligned} x + y &= \sum_{i=0}^{\rho-1} t_i^{a_i} - \sum_{i=0}^{\rho - 1} s_i \\ & \equiv \sum_{i=0}^{\rho-1} (a_i \cdot 2^ib + s_i) - \sum_{i=0}^{\rho - 1} s_i \\ & \equiv b \sum_{i=0}^{\rho-1} (a_i \cdot 2^i) \\ & \equiv ba \end{aligned}\]

在上面证明过程中利用了恒等式 \(t_i^{a_i} = a_i \cdot 2^ib + s_i\) ，由于 \(a_i\) 是 \(a\) 的一个二进制位，我们分别设 \(a_i=0\) 和 \(a_i=1\) 两种情况，每种情况下容易验证这个恒等式成立。

3.2. 特点：Light Computation, Heavy Bandwidth

基于 Oblivious Transfer 的 MtA 协议有个特点：Light Computation, Heavy Bandwidth。

之所以说 Light Computation，是由于基于 Oblivious Transfer 实现的 MtA 协议的计算量要小于其它方案（如基于 Paillier 同态加密）实现的 MtA；之所以说 Heavy Bandwidth，是由于会进行多个 Oblivious Transfer 过程，需要交换的数据比较多。