密码学之 Ecdsa 签名、CMP20、MPC 钱包 (五) 初稿

<div align='center'><font size='5'>密码学之 Ecdsa 签名、CMP20、MPC 钱包 (五) 初稿</font></div>

目录

• 综述
• 基本技术
  • 一、关于 MPC 钱包协议设计的文章
  • 二、Paillier 加密、ECDSA 签名
  • 三、NP-relations(NP关系)
  • 1. Schnorr
  • 2. Paillier Encryption in Range
  • 3. Group Element vs Paillier Encryption in Range
  • 4. Paillier Affine Operation with Group Commitment in Range
  • 5. Paillier Affine Operation with Paillier Commitment in Range
  • 6. Auxiliary Relations
  • 7. Sigma-Protocols
• 算法协议
  • 四、keygen
  • 五、key-refresh
  • 六、pre-signing
  • 七、signing
• 安全性分析
• 总结
  • 与其他方案的对比
  • 技术贡献与应用
  • 扩展与后续研究

综述

今天分享另一篇关于 ECDSA 的阈值组签名技术，详细内容源于这篇论文 UC Non-Interactive, Proactive, Threshold ECDSA，简称 CMP20，这篇论文研究方向属于多方安全计算领域，多方计算协议可以保证多个参与方在计算过程中不会泄露任何信息，从而保证计算的安全性。

该论文于 2020 年发表在 ACM SIGSAC 会议（计算机与通信安全会议）上，属于密码学领域的顶级会议。CMP20 是对早期阈值签名方案（如 GG18、GG20）的重要改进，首次在 UC 框架下实现了非交互式、主动安全且支持动态腐化（Adaptive Corruption）的阈值 ECDSA 签名。

该文章包含了非常全的关于 MPC 钱包协议中所涉及的密码学技术，以及非常全的各种零知识证明场景以及实现实例，这些技术在 GG18、GG20 等协议中都会用到。该协议只需要 4 轮通信，接下来依次进行讲解。

基本技术

一、关于 MPC 钱包协议设计的文章

• VSS、DKG、Threshold-Signature
• 密码学之Schnorr签名、多签、MPC钱包(一)
• 密码学之Schnorr签名、Frost20、MPC钱包(二)
• 密码学之承诺（Commitment Scheme）
• 密码学之 Ecdsa 签名、GG18、MPC 钱包(三)
• 密码学之 Ecdsa 签名、GG20、MPC 钱包 (四) 完整版

二、Paillier 加密、ECDSA 签名

请看这篇文章密码学之 Ecdsa 签名、GG18、MPC 钱包(三)的 1.4 和 1.1 部分。

三、NP-relations(NP关系)

这部分也是比较重要的概念，理解了这部分，就能理解后面的几种零知识证明（ZKP）。但凡涉及到零知识证明的地方，NP 类从未缺席。NP 问题是给定一个解，能在多项式时间内验证这个解是否正确，比如旅行商问题，若给出一条路径，可快速计算总路程是否符合要求。

1. Schnorr

定义关系： $$ \begin{align} \bm{R}_{sch}={(\text{PUB}_0,X;x)|X=g^x} \end{align} $$ 解释：该关系是最常见也是最简单的一个关系，即证明者拥有秘密 $x$，并且证明者公开 $X$，证明者需要证明使得 $X=g^x$ 成立的 $x$。使用最基本的 $schnorr$ 协议即可证明，这里不再详述。

2. Paillier Encryption in Range

这部分是 Paillier 加密范围的零知识证明，怎么设计零知识证明？ 定义关系： $$ \begin{equation} \bm{R}_{\mathrm{enc}}=\left{\left(N_0, \mathcal{I}, C ; x, \rho\right) \mid x \in \mathcal{I} \wedge C=\left(1+N_0\right)^x \rho^{N0} \in \mathbb{Z}{N_0^2}^*\right} \end{equation} $$ 解释：该关系表示，在不暴露秘密 $x$ 的条件下，对于公钥 $N_0$，证明密文 $C$ 对应的明文 $x$ 必须属于某个范围 $\mathcal{I}$。在 GG18 和 GG20 两篇文章中同样用到的相似的技术去证明 MtA 的份额必须在某一具体的范围中。

$\textbf{实例：}$

• 设置：辅助 RSA 模数是 $\hat{N}$，以及 Ring-Pedersen 参数 $s, t \in \mathbb{Z}_{\hat{N}}^*$
• 输入：公共输入 $(N_0, K)$。证明者拥有秘密输入 $(k, \rho)$，满足 $k \in \pm 2^\ell$ 并且 $K = (1 + N_0)^k \cdot \rho^{N_0} \mod N_0^2$。
• 证明者：随机生成 $$ \begin{equation} \begin{cases} \alpha\leftarrow\pm2^{\ell+\varepsilon}\ \mu\leftarrow\pm2^\ell\cdot\hat{N}\ r\leftarrow\mathbb{Z}_{N_0}^*\ \gamma\leftarrow\pm2^{\ell+\varepsilon}\cdot\hat{N}&\end{cases}
  \end{equation} $$ 并计算 $$ \begin{equation} \begin{cases} S=s^kt^\mu{\mathrm{mod}}\hat{N}\ A=(1+N_0)^\alpha\cdot r^{N_0}{\mathrm{mod}}N_0^2\ C=s^\alpha t^\gamma{\mathrm{mod}}\hat{N}&\end{cases} \end{equation} $$ 并把 $(S,A,C)$ 发送给验证者。
• 验证者：随机生成一个挑战$e\leftarrow \pm{q}$，并发送给证明者。
• 证明者：生成证明，计算 $$ \begin{cases}z_1&=\alpha+ek\z_2&=r\cdot\rho^e{\mathrm{mod}}N_0\z_3&=\gamma+e\mu&\end{cases}. $$ 发送 $(z_1,z_2,z_3)$ 给验证者。
• 验证者：等式验证 $$\begin{cases}(1+N_0)^{z_1}\cdot z_2^{N_0}=A\cdot K^e{\mathrm{mod}}N_0^2\s^{z_1}t^{z_3}=C\cdot S^e{\mathrm{mod}}\hat{N}&\end{cases}$$
• 验证者：范围验证 $z_1\in \pm2^{\ell+\epsilon}$，若成立，则保证 $k\in\pm2^{\ell+\varepsilon}$。

3. Group Element vs Paillier Encryption in Range

群元素上的 Paillier 加密范围的关系，怎么去证明？ 定义关系： $$ \begin{equation} \bm{R}_{\log }=\left{\left(\mathrm{PUB}1, \mathcal{I}, C, X, g ; x, \rho\right) \mid x \in \mathcal{I} \wedge C=(1+N)^x \rho^N \in \mathbb{Z}{N^2}^* \wedge X=g^x\right} \end{equation} $$ 解释：该关系表示 $X$ 的离散对数与密文 $C$ 对应的明文是相等的，并且明文的范围是 $\mathcal{I}$。在不暴露 $x,\rho$ 的条件下，需要设计零知识证明证明上述关系成立。怎么做？

$\textbf{实例：}$

• 设置：辅助 RSA 模数是 $\hat{N}$，以及 Ring-Pedersen 参数 $s, t \in \mathbb{Z}_{\hat{N}}^*$
• 输入：公共输入 $(\mathbb{G},q,N_0,C,X,g)$。证明者拥有秘密输入 $(x, \rho)$，满足 $x \in \pm 2^\ell$ 并且 $C= (1 + N_0)^x \cdot \rho^{N_0} \mod N_0^2$ 并且 $X=g^x\in \mathbb{G}$。
  • 证明者：随机生成 $$ \begin{equation}\alpha\leftarrow\pm2^{\ell+\varepsilon}\mathrm{ 和 }\begin{cases}\mu\leftarrow\pm2^\ell\cdot\hat{N}\r\leftarrow\mathbb{Z}_N^*\\gamma\leftarrow\pm2^{\ell+\varepsilon}\cdot\hat{N}&\end{cases}\mathrm{,计算}\quad\begin{cases}S=s^xt^\mu{\mathrm{mod}}\hat{N}\A=(1+N0)^\alpha\cdot R{N_0}{\mathrm{mod}}N_0^2\Y=g^\alpha\in\mathbb{G}\D=s^\alpha t^\gamma{\mathrm{mod}}\hat{N}&\end{cases}\end{equation} $$ 发送 $(S,A,Y,D)$ 给验证者。
  • 验证者：随机生成一个挑战$e\leftarrow \pm{q}$，并发送给证明者。
  • 证明者：生成证明，计算 $$ \begin{equation}\begin{cases}z_1&=\alpha+ex\z_2&=r\cdot\rho^e{\mathrm{mod}}N_0\z_3&=\gamma+e\mu&\end{cases}.\end{equation} $$
• 等式验证： $$ \begin{equation}\begin{cases}(1+N_0)^{z_1}\cdot z_2^{N_0}=A\cdot C^e{\mathrm{mod}}N_0^2\g^{z_1}=Y\cdot X^e\in\mathbb{G}\s^{z_1}t^{z_3}=D\cdot S^e{\mathrm{mod}}\hat{N}&\end{cases}\end{equation} $$
• 范围验证：$z_1\in \pm{2^{\ell+\varepsilon}}$，若成立，则保证 $x\in\pm2^{\ell+\varepsilon}$。

4. Paillier Affine Operation with Group Commitment in Range

给定范围内的带群承诺的 Paillier 仿射操作关系，怎么去证明？
定义关系 $\bm{R}_{\text {aff-g }}$ 对所有的 $(\mathsf{PUB}_2,\mathcal{I},\mathcal{J},C,C_0,Y,X;\varepsilon,\delta,r,\rho)$ 满足如下关系，其中$\text{PUB}_2=(\mathbb{G},g,N_0,N1)$： $$ \begin{equation} (\varepsilon,\delta)\in\mathcal{I}\times\mathcal{J}\:\wedge\:C=C{0}^{\varepsilon}\cdot(1+N{0})^{\delta}r^{N{0}}\in\mathbb{Z}{N{0}^{2}}^{}\:\wedge\:Y=(1+N{1})^{\delta}\rho^{N{1}}\in\mathbb{Z}{N{1}^{2}}^{}\:\wedge\:X=g^{\varepsilon}\in\mathbb{G} \end{equation} $$ 解释：在不暴露 $(\varepsilon,\delta,r,\rho)$ 的条件下，证明密文 $C$ 是通过 $C_0$ 进行仿射变换得到的，其中乘法系数 $\varepsilon$ 必须属于某个范围 $\mathcal{I}$，加法系数 $\delta$ 必须属于某个范围$\mathcal{J}$，并且$X$的离散对数与$\varepsilon$相等，$Y$ 对应的明文与 $\delta$ 相等。

$\textbf{实例}$：

• 设置：辅助 Paillier 模数是 $\hat{N}$，以及 Ring-Pedersen 参数 $s, t \in \mathbb{Z}_{\hat{N}}^*$

• 输入：公共输入 $(\mathbb{G},g,N_0,N1,C,D,Y,X)$，其中 $q=|\mathbb{G}|$、$g$ 是 $\mathbb{G}$ 的生成元。证明者秘密输入 $(x,y,\rho,\rho{y})$，满足 $x\in\pm2^{\ell},y\in\pm2^{\ell^{\prime}},g^{x}=X,(1+N{1})^{y}\rho{y}^{N{1}}=Y\mathrm{~mod~}N{1}^{2}$，并且 $D=C^{x}(1+N{0})^{y}\cdot\rho^{N{0}}{\mathrm{mod}}N_{0}^{2}$。

  • 证明者：随机生成 $\alpha\leftarrow\pm{2^{\ell+\varepsilon}},\beta\leftarrow\pm{2^{\ell'+\varepsilon}}$, 以及 $$ \begin{equation}\begin{cases}r\leftarrow\mathbb{Z}_{N_0}^,ry\leftarrow\mathbb{Z}{N_1}^\\gamma\leftarrow\pm2^{\ell+\varepsilon}\cdot\hat{N},m\leftarrow\pm2^\ell\cdot\hat{N}\\delta\leftarrow\pm2^{\ell+\varepsilon}\cdot\hat{N},\mu\leftarrow\pm2^\ell\cdot\hat{N}&\end{cases}\quad\text{计算}\quad\begin{cases}A=C^\alpha\cdot((1+N_0)^\beta\cdot r^{N_0})&\mathrm{mod}N_0^2\B_x=g^\alpha\in\mathbb{G}\B_y=(1+N_1)^\beta r_y^{N_1}&\mathrm{mod}N_1^2\E=s^\alpha t^\gamma,S=s^xt^m&\mathrm{mod}\hat{N}\F=s^\beta t^\delta,T=s^yt^\mu&\mathrm{mod}\hat{N}&\end{cases}\end{equation} $$ 发送 $(A,B_x,B_y,E,F,S,T)$ 给验证者。
  • 验证者：随机生成一个挑战 $e\leftarrow \pm{q}$，并发送给证明者。
  • 证明者：生成证明，计算 $$ \begin{equation}\begin{cases}z_1=\alpha+ex\z_2=\beta+ey\z_3=\gamma+em\z_4=\delta+e\mu\w=r\cdot\rho^e{\mathrm{mod}}N_0\w_y=r_y\cdot\rho_y^e{\mathrm{mod}}N_1&\end{cases}\end{equation} $$

• 等式验证： $$ \begin{equation} \begin{cases}C^{z_1}\left(1+N_0\right)^{z_2}w^{N_0}=A\cdot D^e{\mathrm{mod}}N_0^2\g^{z_1}=B_x\cdot X^e\in\mathbb{G}\(1+N_1)^{z_2}w_y^{N_1}=B_y\cdot Y^e{\mathrm{mod}}N_1^2\s^{z_1}t^{z_3}=E\cdot S^e{\mathrm{mod}}\hat{N}\s^{z_2}t^{z_4}=F\cdot T^e{\mathrm{mod}}\hat{N}&\end{cases} \end{equation} $$

• 范围验证：$z_1\in \pm{2^{\ell+\varepsilon}},z_2\in \pm{2^{\ell'+\varepsilon}}$，若成立，则保证 $x\in \pm{2^{\ell+\varepsilon}},y\in \pm{2^{\ell'+\varepsilon}}$。

5. Paillier Affine Operation with Paillier Commitment in Range

定义关系 $\bm{R}_{\text{aff-p}}$ 对所有的 $(\mathrm{PUB}_3,\mathcal{I},\mathcal{J},C,C_0,Y,X;\varepsilon,\delta,r,\rho,\mu)$ 满足以下关系，其中 $\text{PUB}_3=(N_0,N1)$： $$ \begin{equation}(\varepsilon,\delta)\in\mathcal{I}\times\mathcal{J}\wedge C=C{0}^{e}\cdot(1+N{0})^{\delta}r^{N{0}}\in\mathbb{Z}{N{0}^{2}}^{}\wedge Y=(1+N{1})^{\delta}\rho^{N{1}}\in\mathbb{Z}{N{1}^{2}}^{}\wedge X=(1+N{1})^{\varepsilon}\mu^{N{1}}\in\mathbb{Z}{N{1}^{2}}^{*}\end{equation} $$ 解释：

6. Auxiliary Relations

• $\textbf{Paillier-Blum modulus}$ $$ \begin{equation}\bm{R}_{\mathrm{mod}}={(N;p,q)\mid\mathrm{PRIMES}\ni p,q\equiv3{\mathrm{mod}}4\wedge N=pq\wedge\gcd(N,\phi(N))=1}\end{equation} $$

• $\textbf{Ring-Pedersen Parameters}$ $$ \begin{equation}\bm{R}_{\mathrm{prm}}=\begin{Bmatrix}(N,s,t;\lambda)\mid s=t^{\lambda}{\mathrm{mod}}N\end{Bmatrix}\end{equation} $$ 解释：该关系表示，在一个乘法群中，已知 $s,t\in \mathbb{Z}^*_N$，$t$ 是生成元，在不暴露 $\lambda$ 的条件下，证明 $s=t^{\lambda}\text{ mod } N$

• $\textbf{No Small Factor Modulus}$ $$ \begin{equation}\bm{R}_{\mathrm{fac}}=\begin{Bmatrix}(\ell,N;p,q)\mid N=pq\wedge p,q>2^\ell\end{Bmatrix}\end{equation} $$

7. Sigma-Protocols

• $\textbf{ZK-Module}$ $\mathrm{ZK-Module~}\mathcal{M}\mathrm{~for~}\Sigma\mathrm{-protocols}$ 包含三部分，分别是$\mathcal{M}(\operatorname{com},\Pi,1^\kappa)$，$\mathcal{M}(\mathrm{prove},\Pi,\mathrm{аих},x;w,\tau)$，$\mathcal{M}(\mathrm{vrfy},\Pi,\mathrm{aux},x,\psi)$。这三部分非常重要，最后的阈值组签名协议的大部分就是基于这三部分实现的。

算法协议

四、keygen

五、key-refresh

六、pre-signing

七、signing

安全性分析

总结

与其他方案的对比

技术贡献与应用

• 安全性突破：CMP20 通过结合 Paillier 同态加密和零知识证明，在密态下完成签名计算，同时支持动态腐化模型（恶意节点可在协议执行中动态选择攻击目标），这是此前方案（如 GG18 仅支持静态腐化）的关键升级。
• 效率优化：通过离线预计算和在线阶段的一轮交互设计，CMP20 将签名生成时间大幅缩短，适用于高频交易场景（如区块链共识、数字资产托管）。
• 实际应用：Cobo、Fireblocks 等机构级数字资产托管平台采用 CMP20 技术，实现多节点协作管理私钥，确保资产在部分节点被攻击时仍安全。

扩展与后续研究

• CMP20 的设计思想被后续研究进一步扩展，例如：
• CGGMP21：2021 年提出的改进方案，通过优化同态加密和零知识证明，进一步降低通信复杂度。 抗量子密码学融合：当前研究正探索将 CMP20 与基于格的签名结合，以应对未来量子计算的威胁。