Two-party ECDSA Signing
Table of Contents
1. Two-party ECDSA 简介
“Two-party ECDSA”问题是指：由两方组成的群体共同完成 ECDSA 签名，可以看作是 2/2 门限签名。本文以 \(P_1\) 和 \(P_2\) 表示参与共同签名的两方。
1.1. 标准的 ECDSA
假设待签名的消息为 \(m\) ，其哈希为 \(H(m)\) ，用户的私钥为 \(x\) ，我们回顾一下标准的（只涉及一方的）ECDSA 签名算法：
- 随机选择 \(k \leftarrow \mathbb{Z}_p\) ；
- 计算 \(R = k \cdot G\) ；
- 计算 \(r=r_x \bmod q\) ，其中 \(r_x\) 是 \(R\) 的 \(x\) 轴坐标；
- 计算 \(s=k^{-1} \cdot (H(m) + r \cdot x) \bmod q\) 。
得到的 \((r,s)\) 就是 ECDSA 签名数据。
2. MacKenzie-Reiter 方案
2001 年，MacKenzie 和 Reiter 在论文 Two-Party Generation of DSA Signatures（full version）中提出了一个 Two-party ECDSA Signing 方案。
MacKenzie 和 Reiter 提出的思路如下：参与方 \(P_1\) 随机生成 \(x_1, k_1\) （和标准的 ECDSA 一样，其中 \(x_1\) 是需要保存的，而 \(k_1\) 是一次一用的），类似地参与方 \(P_2\) 也随机生成 \(x_2, k_2\) ，这两方所组成的群体的 \(k\) 和 \(x\) 分别由 \(k=k_1 \cdot k_2\) 和 \(x=x_1 \cdot x_2\) 得到，由于 \(P_1\) 不能泄露 \(x_1, k_1\) ，同样 \(P_2\) 也不能泄露 \(x_2, k_2\) ，所以不能直接得到群体的 \(k,x\) 。MacKenzie 和 Reiter 给出了一个方案，可以在各方不泄露自己秘密（即 \(x_i, k_i\) ）的情况下构造出群体私钥对消息的签名数据。
2.1. 群体公钥
在介绍如何构造群体签名数据前，先介绍一下如何得到群体的公钥 \(Q = x \cdot G = x_1 \cdot x_2 \cdot G\) 。在各方不泄露各自秘密值 \(x_i\) 的情况下，可以按图 1 所示方法求得 \(Q\) ，这是一个标准的 Diffie–Hellman key exchange 过程。
Figure 1: 运用 Diffie-Hellman 协议得到群体公钥 \(Q\)
\(P_1\) 发送 \(Q_1=x_1 \cdot G\) 给 \(P_2\) （由 \(Q_1\) 无法倒推出 \(P_1\) 的秘密 \(x_1\) ），\(P_2\) 拿了 \(Q_1\) 再乘上 \(x_2\) 就得到了群体公钥；类似地 \(P_1\) 也可以得到群体公钥 \(Q\) 。
2.2. 群体签名数据 \(r\) 部分
由 ECDSA 知，群体签名数据 \(r\) 是 \(R = k_1 \cdot k_2 \cdot G\) 的 \(x\) 轴坐标，我们只需要求得群体 \(R\) 即可知道 \(r\) 。
和计算群体公钥 \(Q\) 类似，利用 Diffie-Hellman key exchange 方法 \(P_1,P_2\) 都可以得到群体的 \(R\) ，如图 2 所示。
Figure 2: 运用 Diffie-Hellman 协议得到群体 \(R\)
2.3. 群体签名数据 \(s\) 部分
群体签名数据的 \(s\) 部分的求解相对 \(r\) 的求解要麻烦一些，我们回顾下标准 ECDSA 的 \(s\) ： \[s=k^{-1} \cdot (H(m) + r \cdot x) \bmod q\] 换为两方共同完成签名后， \(s\) 的计算方式相应地调整为： \[s=(k_1 \cdot k_2)^{-1} \cdot (H(m) + r \cdot x_1 \cdot x_2) \bmod q\]
在确保 \(P_1\) 不泄露 \(x_1,k_1\) ，而 \(P_2\) 不泄露 \(x_2,k_2\) 的情况下，如何计算群体签名数据的 \(s\) 部分呢？利用 Paillier Cryptosystem 的“同态加密”性质可以做到。
2.3.1. Paillier 加同态
Paillier Cryptosystem 是一种公钥密码算法。除此外，Paillier 还具备“加同态”性质。
Paillier 具备下面两个性质：
- 仅已知公钥和两个加密后的消息 \(E(m_1)\) 和 \(E(m_2)\) ，不接触私钥（也就是说不解密）情况下，可以计算出两个明文 \(m_1\) 和 \(m_2\) 相加后再加密的结果，即 \(E(m_1 + m_2)\) ；我们把同态相加记为 \(\oplus\) ，也就是： \[E(m_1 + m_2) = E(m_1) \oplus E(m_2)\]
- 仅已知公钥和密文 \(E(m_1)\) 情况下，可以计算出 \(k \cdot m_1\) 的密文（这里 \(k\) 是常量），即 \(E(k \cdot m_1)\) ，我们把这个运算记为 \(\odot\) ，也就是： \[E(k \cdot m_1) = k \odot E(m_1)\]
这两个性质很有用，可以帮助我们计算群体签名数据中的 \(s\) 部分。
2.3.2. 计算 \(s\) 的具体协议
有了前面介绍的 Paillier，我们可以确保 \(P_1\) 不泄露 \(x_1,k_1\) ，而 \(P_2\) 不泄露 \(x_2,k_2\) 的情况下，计算群体签名数据的 \(s\) 了。
上式中，红色部分是只有 \(P_1\) 知道的，把它加密后，发送给 \(P_2\) ， \(P_2\) 利用 Paillier 的同态加密性质在密文上构造出加密后的 \(s\) ，然后发送给 \(P_1\) ， \(P_1\) 解密即可得到 \(s\) ，这个过程如图 3 所示。
Figure 3: 计算 \(s\) 的具体协议（简化版本）
2.4. MacKenzie-Reiter 方案的缺点
为了防止恶意参与者，Two-party ECDSA 协议需要确保“最终生成的群体签名是正确的”。 \(P_1\) 需要在不泄露 \(k_1\) 的情况下证明他向 \(P_2\) 提供的加密数据中确实包含了 \(k_1^{-1}\) ，这需要借助“零知识证明”来完成。 由于 \(P_2\) 手头掌握的和 \(k_1\) 相关的数据只有 \(R_1 = k_1 \cdot G\) （并不包含 \(k_1^{-1} \cdot G\) ），这个证明过程是很复杂的，涉及很多运算，代价比较大。
Yehuda Lindell 于 2017 年提出了另一种 Two-party ECDSA 方案，其零知识证明过程的代价比 MacKenzie-Reiter 方案要小。
3. Yehuda Lindell 方案
2017 年，Yehuda Lindell 在论文 Fast Secure Two-party ECDSA Signing 提出一个更快的 Two-party ECDSA 方案。除去零知识证明相关内容，和 MacKenzie-Reiter 方案的主要区别在于如何构造群体签名数据的 \(s\) 部分。
Yehuda Lindell 方案中构造群体公钥、群体签名数据 \(r\) 部分的方法和 MacKenzie-Reiter 方案是类似的，这里不介绍。
3.1. 群体签名数据 \(s\) 部分
Yehuda Lindell 方案中，构造群体签名数据 \(s\) 部分的流程如图 4 所示。
Figure 4: Yehuda Lindell 方案（构造群体签名数据的 \(s\) 部分）
这个流程中引入了随机数 \(\rho\) ，这是为了获得更好的安全性，由于在它出现的地方同时乘以了模数 \(q\) ，所以并不会影响到正确性。
3.2. \(x = x_1 + x_2\)
前面的介绍中， \(P_1\) 保存的秘密 \(x_1\) 和 \(P_2\) 保存的秘密 \(x_2\) 的乘积 \(x_1 \cdot x_2\) 就是他们作为群体对外的私钥，即 \(x=x_1 \cdot x_2\) 。我们可以把相乘改为相加吗，即 \(x=x_1+x_2\) ？答案是肯定的。不过协议要相应地调整，下文将具体介绍如何调整。
3.2.1. 群体公钥
和节 2.1 中介绍的方式有一点点区别。现在群体公钥的计算要调整为： \[Q = x \cdot G = (x_1 + x_2) \cdot G = x_1 \cdot G + x_2 \cdot G = Q_1 + Q_2\]
3.2.2. 群体签名数据 \(r\) 部分
由于 \(k=k_1 \cdot k_2\) 没有变化，所以群体签名数据 \(r\) 部分的构造没变化，参考节 2.2 。
3.2.3. 群体签名数据 \(s\) 部分
构造群体签名数据 \(s\) 部分的协议需要调整，如图 5 所示。
Figure 5: 采用 \(x=x_1 + x_2\) 方式时，构造 \(s\)
3.3. 开源实现
在 blockchain-crypto-mpc 中有 Yehuda Lindell 方案的开源实现，在这个实现中，为了更方便地支持“Share Refresh”（即在群体私钥不变的前提下实现 \(x_1,x_2\) 的更新），采用了 \(x = x_1 + x_2\) 的方式。
在 multi-party-ecdsa 中也有 Yehuda Lindell 方案的开源实现，这个实现中，采用了原始论文 \(x = x_1 \cdot x_2\) 的方式，参考：https://github.com/ZenGo-X/gotham-city/blob/master/white-paper/white-paper.pdf