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

<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^{N_0} \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+N_0)^\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,N_1)$： $$ \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,N_1,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}^*,r_y\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,N_1)$： $$ \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=(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,\rho_y)$ ，其中 $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,r_y\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),z_i}{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$。
• 证明者随机生成 ${a_i\leftarrow \mathbb{Z}{\phi(N)}}{i\in[m]}$，计算 $A_i=t^{a_i}\text{ mod }N$ 并发送给验证者。
• 验证者随机生成一个挑战 ${e_i\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{N_0}\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^{x_i}$，同时需要广播其幂指数的知识证明。于是，$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}$ 并计算 $V_i=\mathcal{H}(ssid,i,srid_{i},X_{i},A_{i},u_{i})$。 广播 $(ssid,i,V_i)$。

$\textbf{Round 2.}$

• 当收到来自参与者 $\mathcal{P}j$ 发来的 $(ssid,j,V_j)$ 时，广播发送 $(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})$ 时，验证 $V_j=\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$ 属于由 $t_i$ 生成的乘法群 $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}^*{N_i},\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},\psi_j^{\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}$ 执行：

• 随机生成 $\rho_k\leftarrow \mathbb{Z}^*_{N_k}$, 并计算 $C_i^k=enc_k(x_i^k;\rho_k)$

• 对每一个 $\mathcal{P_j}$ 计算 $$ \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{P_j}$ 计算 $$ \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,u_i,\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,u_j,\pi{i,j},\left(\psi{i,j,k},C_j^k\right)_k)$ 时，验证：

• $\prod_kX_j^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$

1. 对所有的 $\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

首先对预签名阶段进行高层次概述。需要指出的是，在辅助信息阶段结束时，每个参与方 $\mathcal{P_i}$ 都已拥有 Paillier 加密方案$(enc_i,dec_i)$及其公钥$N_i$，同时掌握 Ring-Pedersen 参数 $s_i,t_i\in \mathbb{Z}{N_i}$。此外，ECDSA 签名的形式为 $(r=g^{k^{-1}}|{x-axis},\sigma=k(m+rx))$，其中 $\mathcal{P_i}$ 持有 $x$ 的加性份额 $x_i$。
为便于对比，我们先回顾一下 GG18 协议的核心要点。协议各方共同计算出随机点 $g^{k^{−1}}$，并分别生成 $k$ 的局部加性份额 $k_i$ 和 $k·x$ 的份额 $\chi_i$ 。需要特别说明的是，$g^{k^{-1}}$ 是通过 $(g^{\gamma})^{\delta^{-1}}$ 计算得出的，其中共同计算的随机值 $\delta=k\gamma$ ，而 $\gamma$ 则是为了隐藏 $k$ 而生成的掩码。具体流程如下：

1. 每个参与方 $\mathcal{P}_i$ 生成本地份额 $k_i$ 和 $\gamma_i$ ，使用 $\mathcal{P}_i$ 的密钥分别计算 Paillier 加密 $K_i=\mathrm{enc}_i(k_i)$ 和 $G_i=\mathrm{enc}_i(\gamma_i)$，并广播 $(K_i,G_i)$。

2. 对于每个 $j\neq i$，参与方 $\mathcal{P}i$ 会随机生成 $\beta{i,j},\hat{\beta}{i,j}\leftarrow\mathcal{J}\varepsilon$，利用 Paillier 密码学的同态特性，分别计算 $D_{j,i}=\mathrm{enc}j(\gamma_i\cdot k_j-\beta{i,j})$ 和 $\hat{D}{j,i}=\mathrm{enc}j(x_i\cdot k_j-\hat{\beta}{i,j})$。随后，$\mathcal{P}i$ 进行加密得到 $F{j,i}=\mathrm{enc}i(\beta{i,j})$ 和 $\hat{F}{j,i}=\mathrm{enc}i(\hat{\beta}{i,j})$，令 $\Gamma_i=g^{\gamma_i}$ ，最终将 $(D_{j,i},\hat{D}{j,i},F{j,i},\hat{F}_{j,i})$ 发送给所有参与方。

3. 每个节点 $\mathcal{P}i$ 执行以下运算：首先解密 $\alpha{i,j}=\mathsf{dec}i(D{i,j})$ 和 $\hat{\alpha}{i,j}=\mathsf{dec}i(\hat{D}{i,j})$，并进行模 $q$ 运算。接着计算 $\delta{i}=\gamma_{i}\cdot k_{i}+\sum_{j\neq i}\alpha_{i,j}+\beta_{i,j}\mathrm{mod}q$，以及 $\chi_{i}=x_{i}\cdot k_{i}+\sum_{j\neq i}\hat{\alpha}{i,j}+\hat{\beta}{i,j}{\mathrm{mod}}q$。最后 $\mathcal{P}i$ 令 $\Gamma=\prod{j}\Gamma_{j}$，$\Delta_i=\Gamma^{k_i}$，将 $\delta_i$ 和 $\Delta_i$ 发送给所有参与方。

当获取所有 $\delta_j$ 值后，参与者 $\mathcal{P}_i$ 计算 $\delta=\sum_j{\delta_j}\mathrm{mod}q$，并验证 $g^\delta=\prod_j\Delta_j$ 等于。若未发现矛盾，$\mathcal{P}_i$ 将设置 $R=\Gamma^{\delta^{-1}}$ 并存储 $(R,k_i,\chi_i)$。为增强恶意安全防护，上述流程需补充以下 ZK 证明：

• $K_i$ 的明文必须属于 $\mathcal{I}_\varepsilon$
• 密文 ${D}{j,i}$ 是通过对 $K_j$ 进行仿射运算得到的，其中乘法系数等于 $G_i$ 的隐藏值且该值位于 $\mathcal{I}\varepsilon$ 范围内，加法系数等于 $F_{j,i}$ 的隐藏值且该值位于 $\mathcal{J}_\varepsilon$ 范围内。
• 密文 $\hat{D}{j,i}$ 是通过对 $K_j$ 进行仿射操作得到的，其中乘法系数等于 $X_i$ 的指数，且位于范围 $\mathcal{I}\varepsilon$ 内，加法系数等于 $\hat{F}{j,i}$ 的隐藏值，且位于范围 $\mathcal{J}\varepsilon$ 内。
• $\Delta_i$ 的指数等于 $G_i$ 的明文值。

协议如下

回想一下，$\mathcal{P}_i$ 的秘密状态包含 $x_i,p_i,q_i$，使得 $x_i=g^{x_i}$ 且 $N_i=p_iq_i$。

$\textbf{Round 1.}$ 当从 $\mathcal{P}_i$ 接收输入 $(\text{pre-sign, sid, }\ell,i)$ 时，解析 $sid=(\ldots,\mathbb{G},q,g,\bm{P},srid,\bm{X},\bm{N},\bm{s},\bm{t})$，执行以下操作：

• 随机生成 $k_i,\gamma_i\leftarrow\mathbb{F}q,\rho_i,\nu_i\leftarrow\mathbb{Z}{N_i}^*$ 并设置 $G_{i}=\mathrm{enc}{i}(\gamma{i};\nu_{i}),K_{i}=\mathrm{enc}{i}(k{i};\rho_{i})$。
• 对每一个 $j\neq i$，计算 $\psi_{j,i}^{0}=\mathcal{M}(\mathrm{prove},\Pi_{j}^{\mathrm{enc}},(sid,i),(\mathcal{I}{\varepsilon},K{i});(k_{i},\rho_{i}))$。 广播 $(sid,i,K_i,G_i)$ 并发送 $(sid,i,\psi_{j,i}^{0})$ 给每一个 $\mathcal{P}_j$。

$\textbf{Round 2.}$

1. 当从 $\mathcal{P}i$ 接收到 $(sid,j,K_j,G_j,\psi{i,j}^0)$ 时，验证： $$ \begin{equation*} \mathcal{M}(\mathrm{vrfy},\Pi_{i}^{\mathrm{enc}},(sid,j),(\mathcal{I}{\varepsilon},K{j}),\psi_{i,j}^0)=1 \end{equation*} $$
2. 当对所有的 $\mathcal{P_j}$，上述验证全都通过时，设置 $\Gamma_i=g^{\gamma_i}$ 执行：
   对每一个$j\neq i$，随机生成 $r_{i,j},s_{i,j},\hat{r}{i,j},\hat{s}{i,j}\leftarrow\mathbb{Z}{N_j},\beta{i,j},\hat{\beta}{i,j}\leftarrow\mathcal{J}$ 并计算： $$ \begin{aligned} &-D{j,i}=(\gamma_{i}\odot K_{j})\oplus\mathrm{enc}{j}(-\beta{i,j},s_{i,j})\mathrm{and}F_{j,i}=\mathrm{enc}{i}(\beta{i,j},r_{i,j}).\&-\hat{D}{j,i}=(x{i}\odot K_{j})\oplus\mathrm{enc}{j}(-\hat{\beta}{i,j},\hat{s}{i,j})\mathrm{and}\hat{F}{j,i}=\mathrm{enc}{i}(\hat{\beta}{i,j},\hat{r}{i,j}).\&-\psi{j,i}=\mathcal{M}(\mathrm{prove},\Pi_{j}^{\mathrm{aff-p}},(sid,i),(\mathcal{I}{\varepsilon},\mathcal{J}{\varepsilon},D_{j,i},K_{j},F_{j,i},G_{i});(\gamma_{i},\beta_{i,j},s_{i,j},r_{i,j},\nu_{i})).\&-\hat{\psi}{j,i}=\mathcal{M}(\mathrm{prove},\Pi{j}^{\mathrm{aff-g}},(sid,i),(\mathcal{I}{\varepsilon},\mathcal{J}{\varepsilon},\hat{D}{j,i},K{j},\hat{F}{j,i},X{i});(x_{i},\hat{\beta}{i,j},\hat{s}{i,j},\hat{r}{i,j})).\&-\psi{j,i}^{\prime}=\mathcal{M}(\mathrm{prove},\Pi_{j}^{\mathrm{aff-g}},(sid,i),(\mathcal{I}{\varepsilon},G{i},\Gamma_{i},g);(\gamma_{i},\nu_{i})). \end{aligned} $$ 发送 $(sid,i,\Gamma_{i},D_{j,i},F_{j,i},\hat{D}{j,i},\hat{F}{j,i},\psi_{j,i},\hat{\psi}{j,i},\psi{j,i}^{\prime})$ 给每一个 $\mathcal{P}_j$。

$\textbf{Round 3.}$

1. 当接收到来自 $\mathcal{P}j$ 的 $(sid,j,\Gamma_j,D{i,j},F_{i,j},\hat{D}{i,j},\hat{F}{i,j},\psi_{i,j},\hat{\psi}{i,j},\psi{i,j}^{\prime})$，验证下面三个等式： $$ \begin{aligned} &\mathcal{M}(\text{vrfy}, \Pi_{i}^{\text{aff-p}}, (sid, j), (\mathcal{I}{\varepsilon}, \mathcal{J}{\varepsilon}, D_{i,j}, K_{i}, F_{j,i}, G_{j}), \psi_{i,j}) = 1. \ &\mathcal{M}(\text{vrfy}, \Pi_{i}^{\text{aff-g}}, (sid, j), (\mathcal{I}{\varepsilon}, \mathcal{J}{\varepsilon}, \hat{D}{j,k}, K{i}, \hat{F}{j,i}, X{j}), \hat{\psi}{i,j}) = 1. \ &\mathcal{M}(\text{vrfy}, \Pi{i}^{\text{log}}, (sid, j), (\mathcal{I}{\varepsilon}, G{j}, \Gamma_{j}, g), \psi_{i,j}') = 1. \end{aligned} $$
2. 当对所有的 $\mathcal{P_j}$，上述验证全都通过时，设置 $\Gamma=\prod_{j}\Gamma_{j},\Delta_{i}=\Gamma^{k_{i}}$，并执行以下操作：
   • 对每一个 $j\neq i$，设置 $\alpha_{i,j}=\mathrm{dec}i(D{i,j}),\hat{\alpha}{i,j}=\mathrm{dec}i(\hat{D}{i,j})$，并令： $$ \begin{cases} \delta_i=\gamma_ik_i+\sum{j\neq i}(\alpha_{i,j}+\beta_{i,j}){\mathrm{mod}}q\\chi_i=x_ik_i+\sum_{j\neq i}(\hat{\alpha}{i,j}+\hat{\beta}{i,j}){\mathrm{mod}}q& \end{cases} $$
   • 对每一个 $j\neq i$，计算 $\psi_{j,i}^{\prime\prime}=\mathcal{M}(\mathrm{prove},\Pi_{j}^{\mathrm{log}},(sid,i),(\mathcal{I}{\varepsilon},K{i},\Delta_{i},\Gamma);(k_{i},\rho_{i}))$。发送 $(sid,i,\delta_i,\Delta_i,\psi_{j,i}^{\prime\prime})$ 给每一个 $\mathcal{P}_j$。 清除内存中除存储状态外的所有项目。

$\textbf{Output.}$

1. 当接收到来自 $\mathcal{P}j$ 的 $(sid,j,\delta_j,\Delta_j,\psi{j,i}^{\prime\prime})$，验证： $$ \begin{equation*} \mathcal{M}(\mathrm{vrfy},\Pi_{i}^{\mathrm{log}},(sid,j),(\mathcal{I}{\varepsilon},K{j},\Delta_{j},\Gamma),\psi_{i,j}^{\prime\prime})=1. \end{equation*} $$
2. 当对所有的 $\mathcal{P_j}$，上述验证全都通过时，设置 $\delta=\sum_{j}\delta_{j}$，并执行：
   • 验证：$g^{\delta}=\prod_j\Delta_j$。
   • 设置 $R=\Gamma^{\delta^{-1}}$ 并输出 $(sid,i,R,k_i,\chi_i)$。清除所有项目，但保留已保存的状态。

$\textbf{Errors.}$ 若验证步骤失败或收到其他参与者 $\mathcal{P}_j\in \bm{P}$ 的投诉，应立即上报并终止流程。

$\textbf{Stored State.}$ 保存 $\bm{X,N,s,t}$ 以及 $x_i,p_i,q_i$。

八、Signing

当消息 $m$ 的哈希值已知后，对于曲线第 $i$ 个已公开点 $(\text{sign},\ell,i,m)$ 的输入，签名过程可简化为获取相关数据并计算正确的签名份额。具体步骤如下：首先获取 $(\ell,R,k,\chi)$；接着计算 $r=R|_{x-axis}$；然后将 $\sigma_i=km+r\chi$ 发送给所有节点；最后擦除元组 $(\ell,R,k,\chi)$。

协议如下：

$\textbf{Round 1.}$ 当输入参数为 $(\text{sign},\ell,i,m)$ 时，若存在 $(sid,\ell,R,k,\chi)$ 记录，则执行以下操作：

• 设置 $r=R|_{x-axis},\sigma_i=km+r\chi$
• 发送 $(sid,i,\sigma_i)$ 给所有的参与者。并将 $(sid,\ell,R,k,\chi)$ 从存储中删除。

$\textbf{Output.}$ 当接收到来自 $\mathcal{P}_j$ 的 $(sid,j,\sigma_j)$ 时，执行：

• 设置 $\sigma=\sum_j\sigma_j$
• 验证 $(r,\sigma)$ 是一个有效签名。输出 $(\text{signature},sid,m,R,\sigma)$。

$\textbf{Errors.}$ 若验证步骤失败或收到其他参与者 $\mathcal{P_j}\in \bm{P}$ 的投诉，应立即上报并终止流程。

安全性分析

采用随机预言机模型进行安全分析，并假设所有哈希值（例如 $Fiat-Shamir$ 启发式算法中的哈希值）均通过调用随机预言机获取。

采用卡内蒂等人和卡梅尼施等人提出的理论框架，将随机预言机模型整合到统一计算（UC）体系中。该理论框架的核心在于：随机预言机是对实际公共哈希函数的抽象化建模，这种哈希函数在全球范围内被系统及其环境所使用。具体而言，随机预言机被建模为一种理想化功能，无论是在真实系统还是理想系统中，该功能都具有全局可访问性。卡内蒂等人和卡梅尼施等人为该功能提供了多种替代性表述方式。改论文采用其中最简单（也是最具约束性）的表述形式——严格随机预言机。

总结

与其他方案的对比

技术贡献与应用

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

扩展与后续研究

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