GG20
Gennaro, Goldfeder 20, One Round Threshold ECDSA with Identifiable Abort
Keygen
假设参与方配置为 {t-n} 每个参与方生成一个随机数 $u_i$ , 然后将 $u_i$ 拆分成 t 份，记为 $u_i'$ 通过类似 Shamir secret sharing 分享给其他 t 个参与者(分享者自己也获得一份) 。 计算每个参与者持有的share $y_i=\sum_{i=1}^t u_i'$, 这里之所以命名为$y_i$是为了和下文sign时使用拉格朗日插值多项式做铺垫。
Sign
ECDSA的签名 $s=k^{-1}(h+ d_Ar)=k^{-1}h + k^{-1}d_Ar $
MtA
multiplicative-to-additive: 假设 Alice 有私密数据 a, Bob有私密数据 b， 现在想要在不暴露 a，b 的情况下，计算它们的乘积 ab. 使用Paillier 同态加密.
- Alice 发送加密后的a:$E(a)$给Bob
- Bob 计算 $(E(a))^b+E(\beta) = E(ab+\beta) $, 然后将 $E(ab+\beta) $发送给Alice
- Alice解密 $E(ab+\beta) $ 得到 $ab+\beta $, 然后公开 $ab+\beta $
- Bob 公开 $-\beta $
- 将Alice和Bob公开的数据相加有 $(ab+\beta)+(-\beta)=ab $,至此，完成了MtA
GG20进行签名时，每一个参与方生成自己 $k_i$, 观察上面的签名公式，h是公开数据，只需要分别计算出来 $[k^{-1}, k^{-1}d_A, r ]$,就可以计算出来签名s。因为 $k=\prod_{i-1}^t k_i $, 所以 $[k^{-1}, r]$ 都可以直接使用 MtA 计算出来。但 $k^{-1}d_A $ 中的私钥并不满足累乘关系，即 $d_A \neq \prod_{i-1}^t x_i $,所以不能通过MtA直接计算。
根据拉格朗日插值法，给定n+1个点，可以找到一个次数不超过n的拉格朗日多项式L,并且只有一个。这也是GG20实现阈值签名的数学理论依据，对于 (t-n) 的阈值签名算法，我们只需要构造一个 t-1 阶的多项式，那么只需要提供 t个点就可以唯一确定这个多项式。GG20中将这个t-1阶多项式的常数项$a_0$设置为私钥。
拉格朗日插值多项式 $L(x)=\sum_{i=1}^t y_i\ell_i(x) $, 其中 $\ell_i(x) $为拉格朗日基本多项式： $$\ell_i(x)=\prod_{j=1,j\neq i}^t \frac{x-x_j}{x_i-x_j} $$ 我们将 keygen 阶段生成的 $y_i$ 当做拉格朗日插值法的点，$x_i$ 取 $[1,2,3,\cdots,t]$, 然后每一个参与方只需要计算 $y_i\ell_i(0) \cdot k^{-1} $, 然后将各自的计算结果公布出来，对公布的结果求和就可以求得 $k^{-1}d_A $.
至此，签名公式中的$[k^{-1}, k^{-1}d_A, r ]$都计算出来的，签名也就可以计算出来了。
举个例子
为了简单，我们举一个 {2-3} 的例子。有三个参与方，分别表示为$P_1,P_2,P_3$
- 它们随机生成了随机数 $u_1=10, u_2=20, u_3=30$, 则私钥 $d_A=u_1+u_2+u_3=60$
- 它们分别生成了随机的 t-1 即 2-1=1 阶多项式
$F_1(x)=10+11x \ F_2(x)=20+22x \ F_3(x)=30+33x $ - 进行类似SSS的分享有
$y_1=F_1(1)+F_2(1)+F_3(1)=21+42+63=126 \ y_2=F_1(2)+F_2(2)+F_3(2)=32+64+96=192 \ y_3=F_1(3)+F_2(3)+F_3(3)=43+86+129=258 $ - 假设是$P_2,P_3$参与签名，求拉格朗日基本多项式
$\ell_2(x)=\frac{x-3}{2-3}=3-x,\quad \ell_2(0)=3,\quad y_2\ell_2(0)=192\times 3=576 \ \ell_3(x)=\frac{x-2}{3-2}=x-2,\quad \ell_3(0)=-2,\quad y_3\ell_3(0)=258\times (-2)=-516 $ - $d_A=y_2\ell_2(0)+y_3\ell_3(0)=576-516=60 $
Todo
根据 sefeheron 的预警文档，Dmytro和Omer 发现攻击者通过选择合适的$k_i$值，通过多次签名交互，可以缩小每个参与方$y_i$的取值范围，当取值范围缩小到一定规模，就可以通过暴力计算得到私钥。论文中只用了16次就破解了。