密码学之 Ecdsa 签名、CMP20、MPC 钱包 (五) 更新2025.11.11

<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
    • 6.1 Paillier-Blum modulus
    • 6.2 Ring-Pedersen Parameters
    • 6.3 No Small Factor Modulus
  • 四、 Sigma-Protocols
  • ZK-Module
• 算法协议
  • 五、Key-Gen
  • 六、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{实例}\mathrm{ZKP-\Pi^{enc}}$：

• 设置：辅助 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{实例} \mathrm{ZKP-\Pi^{log}}$：

• 设置：辅助 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{实例}\mathrm{ZKP-\Pi^{aff-g}}$：

• 设置：辅助 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

给定范围内的带 Paillier 承诺的 Paillier 仿射操作关系，怎么去证明？ 定义关系 $\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} $$ 解释：该关系与前一个关系唯一的区别是 $\varepsilon$ 等于 $X$ 对应的 $Paillier$ 明文，而非离散对数。

$\textbf{实例}\mathrm{ZKP-\Pi^{aff-p}}$：

• 设置：辅助 Paillier 模数是 $\hat{N}$，以及 Ring-Pedersen 参数 $s, t \in \mathbb{Z}_{\hat{N}}^*$。
• 输入：公共输入 $(x,y,\rho,\rho_x,\rhoy)$ ，其中 $x\in\pm2^{\ell},y\in\pm2^{\ell^{\prime}},(1+N{1})^{x}\rho{x}^{N{1}}=X,(1+N{1})^{y}\rho{y}^{N{1}}=Y,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}^,\r_x,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}\end{equation} $$ 并计算 $$ \begin{equation}\begin{cases}A=C^\alpha\cdot((1+N_0)^\beta\cdot r^{N_0}){\mathrm{mod}}N_0^2\B_x=(1+N_1)^\alpha r_x^{N_1},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_x=r_x\cdot\rho_x^e{\mathrm{mod}}N_1\w_y=r_y\cdot\rho_y^e{\mathrm{mod}}N_1&\end{cases}\end{equation} $$ 发送 $(z_1,z_2,z_3,z_4,w,w_x,w_y)$ 给验证者。
• 等式验证： $$ \begin{equation}\begin{cases}C^{z_1}(1+N_0)^{z_2}w^{N_0}=A\cdot D^e{\mathrm{mod}}N_0^2\(1+N_1)^{z_1}w_x^{N_1}=B_x\cdot X^e{\mathrm{mod}}N_1^2\(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}}$。

6. Auxiliary Relations

6.1 Paillier-Blum modulus

这是一种特殊的 Paillier 模数，它满足以下条件： $$ \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} $$ 解释：双素数 $p,q$ 满足 $p,q\equiv3\,{\mathrm{mod}}\,4$，且 $N=pq$，同时 $\gcd(N,\phi(N))=1$，这种 $N$ 模数称为 Paillier-Blum 模数。这种关系如何证明？ $\textbf{实例}\mathrm{ZK-\Pi^{mod}}$：

• 输入：公共输入是 $N$。证明者的秘密是 $(p,q)$
• 证明者随机生成 $w\leftarrow \mathbb{Z}_N$，并且雅可比符号是 $-1$ ，并发送给验证者。
• 验证者发送 ${y_i\leftarrow\mathbb{Z}N}{i\in[m]}$
• 对每一个 $i\in[m]$ ，计算 $y'_i=(-1)^{a_i}w^{b_i}y_i$，令 $x_i=\sqrt[4]{y_i^{\prime}}$，其中$a_i,b_i\in {0,1}$，计算 $z_i=y_i^{N^{-1}{\mathrm{mod}}\phi(N)}{\mathrm{mod}}N$，发送 ${(x_i,a_i,b_i),zi}{i\in[m]}$ 给验证者。
• 验证：
  • $N$ 是一个奇合数
  • 对每一个 $i\in[m]$，都有 $z_i^{N}=y_i\,\mathrm{mod}\,N$
  • 对每一个 $i\in [m]$，都有 $x_i^4=(-1)^{a_i}w^{b_i}\,{\mathrm{mod}}\,N,a_i,b_i\in{0,1}$

6.2 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$，如何证明？ $\text{实例}\mathrm{ZK-\Pi^{prm}}$：

• 输入：公共输入是 $N,s,t$。证明者的秘密是 $\lambda$，满足 $s=t^{\lambda}\text{ mod } N$。
• 证明者随机生成 ${ai\leftarrow \mathbb{Z}{\phi(N)}}_{i\in[m]}$，计算 $A_i=t^{a_i}\text{ mod }N$ 并发送给验证者。
• 验证者随机生成一个挑战 ${ei\leftarrow {0,1}}{i\in[m]}$，并发送给证明者。
• 证明者计算 $z_i=a_i+e_i\lambda\text{ mod }\phi(N)$，并发送给验证者。
• 验证：如果对所有的 $i\in[m]$，都有 $t^{z_i}=A_i\cdot s^{e_i}$ 成立，那么接受该证明，否则拒绝。

6.3 No Small Factor Modulus

$$ \begin{equation}\bm{R}_{\mathrm{fac}}=\begin{Bmatrix}(\ell,N;p,q)\mid N=pq\wedge q>2^\ell\end{Bmatrix}\end{equation} $$ 解释：该关系表示一个合数 $N$ 没有小因子，其质因数 $p,q$ 满足 $q>2^\ell$，如何证明？ $\textbf{实例}\mathrm{ZK-\Pi^{fac}}$：

• 设置：$\hat{N}$ 是一个辅助安全的双素数乘积的合数，Ring-Pedersen parameters 为 $s,t\in\mathbb{Z^*_{\hat{N}}}$
• 输入：公共输入 $N_0$。证明者的秘密是 $(p,q)$，满足 $p,q<\pm{\sqrt{N_0}\cdot 2^{\ell}}$。
• 证明者随机生成 $$ \begin{equation}\alpha,\beta\leftarrow\pm2^{\ell+\epsilon}\cdot\sqrt{N_0},\quad\begin{cases}\mu,\nu\leftarrow\pm2^\ell\cdot\hat{N}\\rho\leftarrow\pm2^\ell\cdot N_0\cdot\hat{N}\r\leftarrow\pm2^{\ell+\epsilon}\cdot N_0\cdot\hat{N}\x,y\leftarrow\pm2^{\ell+\epsilon}\cdot\hat{N}&\end{cases}\end{equation} $$ 并计算 $$ \begin{equation}\begin{cases}P=s^pt^\mu,Q=s^qt^\nu&{\mathrm{mod}}\hat{N}\A=s^\alpha t^x&{\mathrm{mod}}\hat{N}\B=s^\beta t^y&{\mathrm{mod}}\hat{N}\T=Q^\alpha t^r&{\mathrm{mod}}\hat{N}&\end{cases}\end{equation} $$ 发送 $(P,Q,A,B,T,\rho)$ 给验证者。
• 验证者：随机生成一个挑战 $e\leftarrow \pm{q}$，并发送给证明者。
• 证明者：生成证明，计算 $$ \begin{equation}\begin{cases}z_1&=\alpha+ep\z_2&=\beta+eq\w_1&=x+e\mu\w_2&=y+e\nu\v&=r+e\rho-e\nu p &\end{cases}\end{equation} $$ 发送 $(z_1,z_2,w_1,w_2,v)$ 给验证者。
• 等式验证： $$ \begin{equation}\begin{cases}s^{z_1}t^{w_1}=A\cdot P^e{\mathrm{mod}}\hat{N}\s^{z_2}t^{w_2}=B\cdot Q^e{\mathrm{mod}}\hat{N}\Q^{z_1}t^v=T\cdot (s^{N_0}t^{\rho})^e{\mathrm{mod}}\hat{N}&\end{cases}\end{equation} $$
• 范围验证：若 $z_1,z_2\in\pm\sqrt{N0}\cdot2^{\ell+\varepsilon}$ 成立，则可以保证 $p,q>2^{\ell}$ ，这里假设 $2^{2\ell+\varepsilon}\approx\sqrt{N{0}}$。

四、 Sigma-Protocols

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{аuх},x;w,\tau)$，$\mathcal{M}(\mathrm{vrfy},\Pi,\mathrm{aux},x,\psi)$。这三部分非常重要，后面的阈值组签名方案的大部分协议就是基于这三部分实现的。

• com 表述公共输入，$1^{\kappa}$ 表示安全参数。
• $\Pi=(\mathrm{P_1},\mathrm{P_1},\cdots)$ 表示一系列算法。
• $\mathrm{aux}$ 表示辅助输入，$x$ 表示公开输入。
• $w$ 表示证明者的秘密或证据，$\tau$ 表示随机化秘密值。
• $\psi$ 表示生成的证明
• $\mathcal{H}:{0,1}^*\rightarrow{0,1}^h$ 表示哈希函数。

算法协议

五、Key-Gen

密钥生成的核心是：对于每一个参与方 $\mathcal{P_i}\in\bm{P}$，随机生成 $x_i\leftarrow\mathbb{F}_q$，计算并广播公钥分享 $X_i=g^{xi}$，同时需要广播其幂指数的知识证明。于是，$X=\prod{j}X_{j}$。

$\textbf{Round 1.}$ 对于参与方 $\mathcal{P_i}$ 来说，其输入为 $(\mathrm{keygen},ssid,i)$ 其中 $ssid=(\cdots,\mathbb{G},q,g,\bm{P})$，执行如下操作：

• 随机生成 $x_i\leftarrow\mathbb{F}_q$ 并计算 $X_i=g^{x_i}$。
• 随机生成 $srid_i\leftarrow{0,1}^{\kappa}$ 并计算 $(A_i,\tau)\leftarrow\mathcal{M}(\mathrm{com},\Pi^{\mathrm{sch}})$。
• 随机生成 $u_i\leftarrow{0,1}^{\kappa}$ 并计算 $Vi=\mathcal{H}(ssid,i,srid{i},X{i},A{i},u_{i})$。 广播 $(ssid,i,V_i)$。

$\textbf{Round 2.}$

• 当收到来自参与者 $\mathcal{P}_j$ 发来的 $(ssid,j,Vj)$ 时，广播发送 $(ssid,i,srid{i},X{i},A{i},u_{i})$ ，事实上这一步是打开承诺的意思。

$\textbf{Round 3.}$

• 1. 当收到来自$\mathcal{P}j$ 发来的 $(ssid,j,srid{j},X{j},A{j},u_{j})$ 时，验证 $Vj=\mathcal{H}(ssid,i,srid{i},X{i},A{i},u_{i})$，如果成立，则接受，否则公开投诉该参与者作恶，并中止协议。
• 2. 当收到所有参与者的上述数据时
     • 令 $srid=\oplus_j srid_j$
     • 计算并生成证明 $\psi{i}=\mathcal{M}(\mathrm{prove},\Pi^{\mathrm{sch}},(ssid,i,srid),X{i};x{i},\tau)$。
       并将 $(ssid,i,\psi{i})$ 广播出去。

$\textbf{Output.}$

• 1. 当收到来自 $\mathcal{P}j$ 发来的 $(ssid,j,\psi{j})$ 时，解析 $\psi_j=(\hat{A}_j,\cdots)$
     • 验证 $\hat{A}_j=A_j$
     • 验证 $\mathcal{M}(\mathrm{vrfy},\Pi^{\mathrm{sch}},(ssid,j,srid),X{j},\psi{j})=1$
• 2. 对所有的 $\mathcal{P_j}$ 以上验证都成立，则输出公钥 $X=\prod_jX_j$。

$\textbf{Errors.}$ 当收到其他参与者的投诉时，以及出现验证失败时，则协议中止或者发起投诉。

$\textbf{Stored State.}$ 存储 $srid,\bm{X}=(X_1,\cdots,X_n)$ 和 $x_i$。

六、Key-Refresh

在高层次上，辅助信息和密钥刷新阶段的流程如下：各方 $\mathcal{P_i}$ 分别随机生成一个由安全素数相乘得到的 Paillier 模数 $N_i$，以及 Ring-Pedersen 参数 $(s_i,t_i)。在恶意安全防护方面，下述流程通过 ZKP 技术使得安全性得到增强。

• $N_i$ 是一个 Paillier-Blum 模以及没有小因子。
• $N_i$ 是两个大小不超过 $\sqrt{N}\cdot 2^{\ell+\varepsilon}$ 的素数的乘积。
• 使用零知识证明 $s_i$ 属于由 $ti$ 生成的乘法群 $Z^*{N_i}$。
• $C^k_i$ 对应的明文（模 $q$）与 $X^k_i$ 的离散对数是相等的。

协议如下：

$\textbf{Round 1.}$ 输入 $(\mathrm{aux-info},sid,i)$，执行如下操作：

• 随机生成两个长度都是 $4\kappa$-bit 的安全素数 $(p_i,q_i)$，并计算 $N_i=p_iq_i$。
• 随机生成 $x_i^1,\ldots,x_i^n\leftarrow\mathbb{F}q$，满足 $\sum{j}x{i}^{j}=0$。计算 $X{i}^{j}=g^{x{i}^{j}},\bm{Y{i}}=(X{i}^{j}){j},\bm{x{i}}=(x{i}^{j})_{j}.$
• 随机生成 $r\leftarrow\mathbb{Z}^*_{Ni},\lambda\leftarrow\mathbb{Z}{\phi(N_i)}$，令$t_i=r^2\text{ mod }N_i,s_i=t_i^{\lambda}\text{ mod }N_i$
• 随机生成 $u_i\leftarrow{0,1}^\kappa$ 并计算 $V_i=\mathcal{H}(sid,i,\bm{Y_i},u_i)$
• 计算 $\psi{i}=\mathcal{M}(\mathrm{prove},\Pi^{\mathrm{mod}},(sid,i),N{i};(p{i},q{i}))$
• 计算 $\psi{i}^{\prime}=\mathcal{M}(\mathrm{prove},\Pi^{\mathrm{mod}},(sid,i,\psi{i}),N{i};(p{i},q_{i}))$
• 计算 $\psi{i}^{\prime\prime}=\mathcal{M}(\mathrm{prove},\Pi^{\mathrm{prm}},(sid,i),(N{i},s{i},t{i});\lambda)$

广播$(sid,i,V_i,N_i,s_i,t_i,\psi_i,\psi_i^{\prime},\psi_i^{\prime\prime}).$

$\textbf{Round 2.}$

1. 当收到来自 $\mathcal{P}_j$ 发来的 $(sid,j,V_j,N_j,s_j,t_j,\psi_j,\psi_j^{\prime},\psij^{\prime\prime})$ 时，验证: $$ \begin{aligned}&N{j}\geq2^{8\kappa}\&\mathcal{M}(\mathrm{vrfy},\Pi^{\mathrm{mod}},(sid,j),N{j},\psi{j})=1\&\mathcal{M}(\mathrm{vrfy},\Pi^{\mathrm{mod}},(sid,j,\psi{j}),N{j},\psi{j}^{\prime})=1\&\mathcal{M}(\mathrm{vrfy},\Pi^{\mathrm{prm}},(sid,j),(N{j},s{j},t{j}),\psi_{j}^{\prime\prime})=1\end{aligned} $$
2. 当上述验证全都通过时，对每一个参与者 $\mathcal{P_k}$ 执行：
   • 随机生成 $\rhok\leftarrow \mathbb{Z}^*{N_k}$, 并计算 $C_i^k=enc_k(x_i^k;\rho_k)$
   • 对每一个 $\mathcal{Pj}$ 计算 $$ \begin{equation*} \psi{j,i,k}=\mathcal{M}(\mathrm{prove},\Pi{j}^{\mathrm{log}},(sid,i),(\mathcal{I}{\varepsilon},C{i}^{k},X{i}^{k},g);(x{i}^{k},\rho{k})) \end{equation*} $$ 表示对每一个作为验证者的 $\mathcal{P_j}$，都要生成一个零知识证明。
   • 对每一个 $\mathcal{Pj}$ 计算 $$ \begin{equation*} \pi{j,i}=\mathcal{M}(\mathrm{prove},\Pi{j}^{\mathrm{fac}},(sid,i),(\ell,N{i});(p{i},q{i})), \end{equation*} $$ 表示对每一个作为验证者的 $\mathcal{P_j}$，都要生成一个零知识证明。 发送 $(sid,i,\boldsymbol{Y}_i,ui,\pi{j,i},\left(\psi_{j,i,k},C_i^k\right)_k)$ 给每一个 $\mathcal{P_j}$ 。

• 下图有助于理解算法：

$\textbf{Output.}$

1. 当收到来自 $\mathcal{P}_j$ 发来的 $(sid,j,\boldsymbol{Y}_j,uj,\pi{i,j},\left(\psi_{i,j,k},C_j^k\right)_k)$ 时，验证：

   • $\prod_kXj^k=\mathrm{id}{\mathbb{G}}$
   • $\mathcal{H}(sid,j,\boldsymbol{Y}{j},u{j})=V{j}\mathrm{~and~}\mathcal{M}(\mathrm{vrfy},\Pi{j}^{\mathrm{fac}},(sid,i),(\ell,N{i}),\pi{i,j})=1$
   • 对每一个 $k$，验证 $\mathcal{M}(\mathrm{vrfy},\Pi{i}^{\mathrm{log}},(sid,j),(\mathcal{I}{\varepsilon},C{j}^{k},X{j}^{k},g),\psi_{i,j,k})=1$

2. 对所有的 $\mathcal{P_j}$，当上述验证全都通过时，执行：

   • 令 $x{i}^{*}=x{i}+\sum{j}\mathrm{dec}{i}(C_{j}^{i}){\mathrm{mod}}q$
   • 令 $X{k}^{*}=X{k}\cdot\prod{j}X{j}^{k}\text{ for every }k$ 输出 $(sid,i,\boldsymbol{X}^=(X_k^)_k,\boldsymbol{N}=(N_j)_j,\boldsymbol{s}=(s_j)_j,\boldsymbol{t}=(t_j)_j)$，向量形式。

$\textbf{Errors.}$ 当收到其他参与者的投诉时，以及出现验证失败时，则协议中止或者主动发起投诉。

$\textbf{Stored State.}$ 存储 $x_i^*,p_i,q_i$。

七、Pre-Signing

八、Signing

安全性分析

总结

与其他方案的对比

技术贡献与应用

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

扩展与后续研究

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