【施工中】开坑后一定更有动力写！

前置知识

Shamir’s Secret Sharin

1979 年 Adi Shamir How to share a secret

在门限 (t,n)(t,n) 中分享秘密，即 nn 个人持有部分秘密，任意 tt 个人能还原出完整秘密。

原理：秘密是多项式 f(x)=a0+a1x+⋯+at−1xt−1f(x)=a_0+a_1x+\dots+a_{t-1}x^{t-1} 中的 a0a_0，每次还原时利用多项式插值。

注意：初始时依赖可信赖第三方（Dealer）生成多项式并分发 (i,f(i))(i,f(i))。

Verifiable Secret Sharing

Feldman VSS

1987 年 Feldman A Practical Scheme for Non-interactive Verifiable Secret Sharing

保证了 Dealer 在分发 (x,f(x))(x,f(x)) 时无法恶意替换。

原理：Dealer 分完后声明 c0=ga0,c1=ga1,…,ct−1=gat−1c_0=g^{a0},c_1=g^{a_1},\dots,c_{t-1}=g^{a_{t-1}}；每个成员收到 (x,f(x))(x,f(x)) 后验证 gf(x)=∏icixig^{f(x)}=\prod_i c_i^{x^i}

Pedersen VSS

1991 年 Pedersen Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing

新增 g(x)=b0+b1x+⋯+bt−1xt−1g(x)=b0+b_1x+\dots+b_{t-1}x^{t-1} 这个陪跑多项式，分发时发送 (x,f(x),g(x))(x,f(x),g(x))。

Dealer 公布 ci=saitbic_i=s^{a_i}t^{b_i}，被称为 commitment。每个成员验证 sf(x)tg(x)=∏icixis^{f(x)}t^{g(x)}=\prod_i c_i^{x^i}。

Pedersen VSS 是 Information-Theoretic Secure（信息论安全的），即安全性不依赖于任何计算复杂性假设。

Publicly Verifiable Secret Sharing

1996 年 Stadler Publicly Verifiable Secret Sharing 中提出。

Distributed Key Generation（DKG）

1991 年 Pedersen A Threshold Cryptosystem without a Trusted Party 中提出的，可称为 Pedersen’s DKG（ Joint Feldman DKG）。基于 Feldman VSS。

2006 年，Rosario Gennaro Secure Distributed Key Generation for Discrete-Log Based Cryptosystems 中提出的，可称为 Gennaro DKG。基于 Pedersen VSS。

Schnorr

Fiat-Shamir Transform

交互式改非交互式，核心是 Verifier 给出的数值都用哈希产生。

Multiplicative-to-Additive

Multiplicative-to-Additive 指的是乘法到加法的转换协议。假设 Alice 和 Bob 各自有个秘密值 a∈Zq,b∈Zqa \in \mathbb{Z}_q,b \in \mathbb{Z}_q，MtA 能在不泄露各自秘密的情况下，让他们各自得到 α∈Zq,β∈Zq\alpha \in \mathbb{Z}_q,\beta \in \mathbb{Z}_q 使得 ab=α+βmod  qab=\alpha+\beta \mod q。

MtA 通常使用 Paillier 工具，其具有同态加的特性，详见 《密码学导论》。

ECDSA 多方签名原理

目标

设 G\mathbb{G} 是有限域下阶为 qq 的椭圆曲线，gg 是其生成元。私钥是 xx，公钥是 y=gx∈Gy=g^x \in \mathbb{G}。

  • 签名：将待签字符串表示成字符串 m∈Zqm \in \mathbb{Z}_q，取随机数 k∈Zqk \in \mathbb{Z}_q，计算 R=gk−1∈GR=g^{k^{-1}} \in \mathbb{G}，设 rr 是 RR 点在椭圆上的 x 坐标，计算 s=k(m+xr)mod  qs=k(m+xr) \mod q，称 (R,s)(R,s) 是一组对 mm 的签名。
  • 验签：判定 gm/sgr/s=Rmod  qg^{m/s}g^{r/s}=R \mod q 是否成立。

上述签名方式与标准流程略有区别（RR 处从 gkg^{k} 改为为 gk−1g^{k^{-1}}，ss 处从 k−1k-1 改为 kk），猜测为了求 ss 时更好维护。

现在假设私钥是被 nn 个参与者各自维护（即 x=∑xix=\sum x_i），他们想基于门限 tt 对 mm 进行签名但不泄露私钥。

原理

密钥生成时每位参与者各自准备 xix_i，认为全局私钥为 x=∑xix=\sum x_i。

每次签名时每位参与者各自取随机数 kik_i，认为全局随机数 k=∑kik=\sum k_i。

求 r=gk−1r=g^{k^{-1}} 时引入辅助随机数 γ=∑γi\gamma=\sum \gamma_i，同样由每个参与者各自生成：

gk−1=gγk−1γ−1=(g∑γi)(kγ)−1=(∏gγi)(kγ)−1\begin{aligned} g^{k^{-1}}&=g^{\gamma k^{-1} \gamma^{-1}} \\ &=\left(g^{\sum \gamma_i} \right)^{(k\gamma)^{-1}} \\ &=\left(\prod g^{\gamma_i} \right)^{(k\gamma)^{-1}} \end{aligned}

注意到各自公开 gγig^{\gamma_i} 不影响 γi\gamma_i 的安全性，只需优雅计算出 kγk \gamma 即可。为了求出 kγk\gamma，每一组参与者 (i,j)(i,j) 需要用 MtA 协议将 kiγjk_i\gamma_j 拆解为 kiγj=αi,j+βi,jk_i\gamma_j=\alpha_{i,j}+\beta_{i,j}，即双方各自持有 αi,j\alpha_{i,j} 和 βi,j\beta_{i,j}。最后每个参与者求出 δi\delta_i：

kγ=(∑ki)(∑γi)=∑i≠jkiγj+∑ikiγi=∑i≠j(αi,j+βi,j)+∑ikiγi=∑i(δi=kiγi+∑j≠iαi,j+∑j≠iβj,i)\begin{aligned} k\gamma&=\left(\sum k_i\right)\left(\sum \gamma_i \right) \\ &=\sum\limits_{i \ne j}k_i \gamma_j+\sum \limits_i k_i \gamma_i \\ &=\sum\limits_{i \ne j}(\alpha_{i,j}+\beta_{i,j})+\sum \limits_i k_i\gamma_i \\ &=\sum \limits_i \left(\delta_i=k_i\gamma_i+\sum_{j \ne i} \alpha_{i,j} +\sum_{j \ne i} \beta_{j, i}\right) \end{aligned}

计算 ss 时，每一组参与者 (i,j)(i,j) 同样用 MtA 将 kixjk_ix_j 拆解为 kixj=μi,j+νi,jk_ix_j=\mu_{i,j}+\nu_{i,j}，最后每个参与者求出 σi\sigma_i 和 sis_i：

s=k(m+xr)=(∑imki)+(∑iki)(∑ixi)r=∑i(si=mki+rσi)σi=kixi+∑j≠iμi,j+∑j≠iνi,js=k(m+xr)=\left(\sum \limits_i mk_i\right)+\left(\sum \limits_i k_i\right)\left(\sum \limits_i x_i\right)r=\sum \limits_i (s_i=mk_i+r\sigma_i) \\ \sigma_i=k_ix_i+\sum \limits_{j \ne i}\mu_{i,j}+\sum \limits_{j \ne i}\nu_{i,j}

GG18 & GG20

原论文：Fast Multiparty Threshold ECDSA with Fast Trustless Setup，鸣谢 sig01 的 讲解。

协议流程

门限

Range Proof

GG18 在签名过程中需要对 MtA 子协议进行 Range Proof：利用 Paillier 加密算法来实现 MtA 协议，Bob 计算得到的 α=ab−βmod  N\alpha=ab-\beta \mod N 是基于 Paillier 的公钥取模的，而我们希望这个结果能在模 qq 域下保持正确。

GG18 核心逻辑是 控制数值范围防止对 NN 取模。Alice 把计算公式改为加：Enc(a)⊗b+Enc(β′)Enc(a) \otimes b+Enc(\beta')，注意本地使用 β=−β′mod  q\beta=-\beta' \mod q，这样能在模 qq 域下保持 MtA 结果的准确性。如果 (a,b,β′)(a,b,\beta') 在数值上能保证 ab+β′<Nab+\beta'<N，那么 Paillier 流程相当于没有执行 mod  N\mod N 行为，Bob 解开后的 α\alpha 一定是模 qq 域下正确的。

GG18 为了确保 ab+β′<Nab+\beta'<N 成立，要求 N>q8N>q^8（密钥生成阶段检查），a<q3a<q^3（Alice 生成时保证且声明），b<q3,β′<q7b<q^3,\beta'<q^7（Bob 生成时保证且声明）。这样就有 ab+β′<q3⋅q3+q7<q8<Nab+\beta'<q^3 \cdot q^3+q^7<q^8<N。

在区块链实践中， qq 是 Secp256k1 的 order，256 比特位长度；NN 是 2048 比特位长度。

GG20

安全性问题

CMP20

Range Proof 细节

enc：(N0,K)(N_0,K)，证明 ∃k∈±2l\exist k \in \pm 2^l 使得 K=Paillier(k;ρ,N0)K=Paillier(k;\rho,N_0) 。

aff-p：(N0,N1,D,C,Y,X)(N_0,N_1,D,C,Y,X)，证明 ∃x∈±2l,y∈±2l′\exists x \in \pm 2^l,y \in \pm 2^{l'} 使得

X=Paillier(x;ρx,N1),Y=Paillier(y;ρy,N1),D=Cx⋅Paillier(y;ρ,N0)mod  N02X=Paillier(x;\rho_x,N_1),Y=Paillier(y;\rho_y,N_1),D=C^x \cdot Paillier(y;\rho,N_0) \mod N_0^2

aff-g：(Gq,g,N0,N1,C,D,Y,X)(\mathbb{G}_q, g, N_0, N_1, C, D, Y, X)，证明 ∃x∈±2l,y∈±2l′\exists x \in \pm 2^l,y \in \pm 2^{l'} 使得：

gx=X∈G,Y=Paillier(y;ρ1,N1),D=Cx⋅Paillier(y;ρ0,N0)mod  N02g^x=X \in \mathbb{G},Y=Paillier(y;\rho_1,N_1),D=C^x \cdot Paillier(y;\rho_0,N_0) \mod N_0^2

log：(Gq,g,N0,C,X)(\mathbb{G}_q, g, N_0, C, X)，证明 ∃x∈±2l\exist x \in \pm 2^l 使得 C=Paillier(x;ρ,N0),X=gxC=Paillier(x;\rho,N_0),X=g^x 。

协议流程

CGCMP

这篇论文的形成有一段佳话：Rosario Gennaro 和 Steven Goldfeder 在 CCS 2020 提出了 GG20，而 Ran Canetti、Nikolaos Makriyannis、Udi Peled 同样在 CCS2020 提出了 CMP20；双方在 2021 年合作提出了 CGCMP，里面提供了具有 trade-off 的两个签名方法；双方在 2024 年更新了 CGCMP，统一了签名方法。

标题 备注
Fast Multiparty Threshold ECDSA with Fast Trustless Setup GG18，两个作者
One Round Threshold ECDSA with Identifiable Abort GG20，两个作者
UC Non-Interactive, Proactive, Threshold ECDSA CMP20，三个作者
UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts CGCMP，五个作者
UC Non-Interactive, Proactive, Distributed ECDSA with Identifiable Aborts CGCMP 更新，五个作者