假设 TSS 为 3-3
gg18 vs cmp20：
keygen
gg18
- 采用了 Feldman VSS 协议生成多项式 $p_i(x)$
- 计算私钥分片 $x_i=\sum_jp_j(id)$，公钥分片为 $X_i=g^{x_i} $
cmp20
- 直接生成私钥分片 $x_i$，公钥分片为 $X_i = g^{x_i}$
sign
- cmp20 可以先通过 presign 算出随机点 $R$，到了 signing 阶段直接对消息 $m$ 签名即可
- cmp20 的 round 数量更少，因为在校验对方的签名分片上采用了不同的策略
keygen
round_1
- 输入：$(ssid, i)$
- 生成私钥分片 $x_i \in F_q$ 和公钥分片：$X_i = g^{x_i}$，其中 $x_i \in F_q$ 是私钥分片
- zk-schnorr 承诺： $(A_i, \tau) = M(com, \prod^{sch})$，其中 $A_i = g^{\tau}$ 是 proof，$\tau$ 是随机数
- 生成随机数 $srid_i = \left\{0, 1\right\}^k, u_i = \left\{0, 1\right\}^k$
- 生成承诺 $V_i = Hash(ssid, i, srid_i, X_i, A_i, u_i)$
- 广播 $V_i$
round_2
- 收到 $P_j$ 的 $V_j$ 后，广播 $(ssid, i, srid_i, X_i, A_i, u_i)$
round_3
- 收到 $P_j$ 的 $(ssid, j, srid_j, X_j, A_j, u_j)$ 后，验证 $H(ssid, j, srid_j, X_j, A_j, u_j) = V_j$
- 将 $srid$ 设为所有其它 $P_j$ 的 $srid_j$ 的 xor：$srid = \bigoplus_jsrid_j$
zk-schnorr 证明： $\psi_i=M(prove, \prod^{sch}, (ssid, i, srid), X_i; x_i, \tau)$，证明知道私钥分片 $x_i$
其中，$(ssid, i, srid)$ 用来生成挑战 $c$，$\psi_i=\tau + c \cdot x_i$
- 向 $P_j$ 发送 $(ssid, i, \psi_i)$
final
- 收到 $P_j$ 的 $(ssid, j, \psi_j)$
- zk-schnorr 验证：$M(vrfy, \prod^{sch}, (ssid, j, srid), X_j, \psi_j) = 1$
- 计算公钥：$X = \prod_jX_j$
refresh
round_1
- 输入：$(ssid, srid, X, i)$
- 生成 Paillier 公钥 $N_i$ 和私钥 $(p_i, q_i)$，其中 $N_i=p_i \cdot q_i$
- 生成 ring-Pedersen 公钥 $(N_i, s_i, t_i)$ 和私钥 $\lambda$，其中 $s_i=t_i^{\lambda}$ mod $N_i$
- zk-schnorr 承诺： $(A_{i}^j, \tau_i^j) = M(com, \prod^{sch})$，其中 $A_i^j = g^{\tau_i^j}$ 是 proof，$\tau_i^j$ 是随机数，得到 $A'_i=(A_i^1, ..., A_i^n)$
- 生成新的秘密 $(x_i^1, ..., x_i^n)$ 和共享信息 $X'_i = (X_i^1=g^{x_i^1}, ..., X_n^1=g^{x_i^n})$，满足 $\sum_jx_i^j=0$
- 生成随机数 $\rho_i, u_i$
- 生成承诺 $V'_i = Hash(ssid, i, A'_i, X'_i, N_i, s_i, t_i, \rho_i, u_i)$
- 广播 $V'_i$
round_2
- 收到 $P_j$ 的 $V'_j$ 后，将所有的 $V'_j$ 哈希后得到 $V'$
- 广播 $(ssid, i, A'_i, X'_i, N_i, s_i, t_i, \rho_i, u_i, V')$
round_3
- 收到 $P_j$ 的 $(ssid, j, A'_j, X'_j, N_j, s_j, t_j, \rho_j, u_j, V')$
对于每个 $P_j$
- 计算新的公钥分片 $X^*_j = X_j \cdot \prod_kX^j_k$，并验证 $X_j^*$ 是否在椭圆曲线上
- 验证 $Hash(ssid, j, A'_j, X'_j, N_j, s_j, t_j, \rho_j, u_j)=V'_j$
- 验证 $V'$
- 计算 $\rho$ 为所有 $P_k$ 的 $\rho_k$ 的 xor：$\rho' = \bigoplus \rho_k$
生成 $N_i$ 是 Paillier-Blum Modulus 的 zk-proof
- 计算 $\psi_i=M(prove, \prod^{mod}, (sid, i, \rho), N_i; p_i, q_i)$
- 计算 $\psi'_i = M(prove, \prod^{mod}, (sid, i, \psi_i,\rho), N_i; (p_i, q_i))$
生成 $(N_i, s_i, t_i)$ 是 ring-Pedersen param 的 zk-proof，即 $s_i$ 属于 $t_i$ 生成的群中的元素，群的阶为 $N_i$
- 计算 $\psi''_i = M(prove, \prod^{prm}, (sid, i, \rho), (N_i, s_i, t_i); \lambda)$
对于所有的 $P_j$
- 使用 Pailier 公钥 $N_j$ 加密 $x_i^j$，得到密文 $C_i^j = enc_j(x_i^k; r_j)$，其中 $r_j$ 是随机数
使用 zk-schnorr 证明知道新的秘密
- 计算 $\psi_i^{j}=M(prove, \prod^{sch}, (ssid, i, srid, \rho), X_i^j; x_i^j, \tau_i^j)$
- 广播 $(\psi_i, \psi'_i, \psi''_i, \psi_i^j)$
final
收到 $P_j$ 的 $(\psi_j, \psi'_j, \psi''_j, \psi_j^k)$，验证这些 zk-proof
- 验证 $M(vrfy, \prod^{mod}, (sid, j, \rho), N_j, \psi_j) = 1$
- 验证 $M(vrfy, \prod^{mod}, (sid, j, \psi_j, \rho), N_j, \psi_j') = 1$
- 验证 $M(vrfy, \prod^{prm}, (sid, j), (N_j, s_j, t_j, \rho), \psi_j'') = 1$
- 对于每个 $P_k$ 验证 $M(vrfy, \prod^{sch}, (ssid, j, srid, \rho), X_j^k, \psi_j^k) = 1$
- Pailier 解密得到 $x_j^i = dec_i(C_j^i)$
- 计算新的私钥分片 $x_i^* = x_i + \sum_jx_j^i$ mod $q$，并验证 $g^{x_j^i} = X_j^i$
例子
refresh 时
- a 产生的增量： 1， -2， 1 = 0
- b 产生的增量：-1， 2， -1 = 0
- c 产生的增量： 0， 2， -2 = 0
- refresh 前根私钥分片：1, 2, 3
- refresh 前根私钥： 6 = 1 + 2 + 3
refresh 后根私钥分片：
- 1 + 1 - 1 + 0 = 1
- 2 - 2 + 2 + 2 = 4
- 3 + 1 - 1 - 2 = 1
- refresh 后根私钥为： 6 = 1 + 4 + 1
如果想让某方的根私钥分片在 refresh 前后保持不变，只需要让其它方为它产生的增量总和为 0，为了避免交互，各方可以简单将增量定为 0
presign
round_1
- 随机选择 $k_i, \gamma_i \leftarrow F_q$ 和 $\rho_i, \nu_i \leftarrow Z_{N_i}^*$，并生成 Pallier 密文 $G_i = enc_i(\gamma_i; \nu_i), \space K_i=enc_i(k_i; \rho_i)$
- 对于每个 $P_j$ 生成 $k_i \in I_{\in}, \space K_i=enc_i(k_i; \rho_i) $ 的 zk-proof：$\psi_{j,i}^0 = M(prove, \prod_j^{enc}, (sid, i), (I_{\in}, K_i); (k_i, \rho_i))$
- 广播 $(sid, i, K_i, G_i, \psi_{j, i}^0)$
round_2
- 收到 $P_j$ 的 $(sid, j, K_j, G_j, \psi_{i, j}^0)$，验证 $M(vrfy, \prod_i^{enc}, (sid, j), (I_{\in}, K_j), \psi_{i,j}) = 1$
- 对所有的 $K_j, G_j$ 进行哈希得到 $H_i$
- 计算 $\Gamma_i = g^{\gamma_i}$
对于每个 $P_j$
- 随机选择秘密 $\beta_{i,j}, \hat{\beta_{i,j}} \leftarrow J$ 和 $r_{i,j}, s_{i,j}, \hat{r_{i,j}}, \hat{s_{i,j}} \leftarrow Z_{N_j}$
- 计算 $F_{j,i}=enc_i(\beta_{i,j}, r_{i,j})$ 和同态加密运算 $D_{i,j} = (\gamma_i \bigodot K_j) \bigoplus enc_j(-\beta_{i,j}, s_{i,j})$
- 计算 $\hat{F_{j,i}}=enc_i(\hat{\beta_{i,j}}, \hat{r_{i,j}})$ 和同态加密运算 $\hat{D_{i,j}} = (x_i \bigodot K_j) \bigoplus enc_j(-\hat{\beta_{i,j}}, \hat{s_{i,j})}$
生成 $\gamma_i \in I_{\in}, \space \beta_{i,j} \in J_{\in}, \space G_i = enc_i(\gamma_i; \nu_i), \space F_{j,i}=enc_i(\beta_{i,j}, r_{i,j})$ 和 $D_{i,j} = (\gamma_i \bigodot K_j) \bigoplus enc_j(-\beta_{i,j}, s_{i,j})$ 的 proof：
$\psi_{j,i} = M(prove, \prod_j^{aff-p}, (sid, i), (I_{\in}, J_{\in}, D_{j,i}, K_j, F_{j,i}, G_i); (\gamma_i, \beta_{i,j}, s_{i,j}, r_{i,j}, \nu_i))$
生成 $x_i \in I_{\in}, \space \hat{\beta_{i,j}} \in J_{\in}, \space X_i=g^{x_i}, \space \hat{F_{j,i}}=enc_i(\hat{\beta_{i,j}}, \hat{r_{i,j}})$ 和 $\hat{D_{i,j}} = (x_i \bigodot K_j) \bigoplus enc_j(-\hat{\beta_{i,j}}, \hat{s_{i,j})}$ 的 zk-proof：
$\hat{\psi_{j,i}} = M(prove, \prod_j^{aff-g}, (sid, i), (I_{\in}, J_{\in}, \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}}))$
生成 $\gamma_i \in I_{\in}, \space \Gamma_i = g^{\gamma_i}, \space G_i = enc_i(\gamma_i; \nu_i) $ 的 zk-proof：
$\psi'_{j,i} = M(prove, \prod_j^{log}, (sid, i), (I_{\in}, G_i, \Gamma_i, g); (\gamma_i, \nu_i) ))$
- 向 $P_j$ 发送 $(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}, H_i)$
round_3
收到 $P_j$ 的 $(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}, H_i)$
- 验证 $M(vrfy, \prod_i^{aff-p}, (sid, j), (I_{\in}, J_{\in}, D_{i,j}, K_i, F_{j,i}, G_j), \psi_{i,j})=1$
- 验证 $M(vrfy, \prod_i^{aff-g}, (sid, j), (I_{\in}, J_{\in}, \hat{D_{i,j}}, K_i, \hat{F_{j,i}}, X_j), \hat{\psi_{i,j}})=1$
- 验证 $M(vrfy, \prod_i^{log}, (sid, j), (I_{\in}, G_{j}, \Gamma_{j}, g), \psi'_{i,j})=1$
- 计算 $\Gamma = \prod_j\Gamma_j$ 和 $∆_i = \Gamma^{k_i}$
对于每个 $P_j$
- 解密得到 $\alpha_{i,j} = dec_i(D_{i,j})$ 和 $\hat{\alpha_{i,j}} = dec_i(\hat{D_{i,j}})$
- 计算 $\delta_i = k_i\gamma_i + \sum_{j \ne i}(\alpha_{i,j} + \beta_{i,j})$ mod $q$
- 计算 $\chi_i = k_ix_i = \sum_{j \ne i}(\hat{\alpha_{i,j}} + \hat{\beta_{i,j}})$ mod $q$
生成的 $k_i \in I_{\in}, \space ∆_i = \Gamma^{k_i}, \space K_i=enc_i(k_i; \rho_i)$ 的 zk-proof：
$\psi''_{j,i} = M(prove, \prod^{log}_j, (sid, i), (I_{\in}, K_i, ∆_i, \Gamma); (k_i, \rho_i))$
- 向 $P_j$ 发送 $(sid, i, \delta_i, ∆_i, \psi''_{j,i})$
final
- 收到 $P_j$ 的 $(sid, j, \delta_j, ∆_j, \psi''_{i,j})$ 后，验证 $M(vrfy, \prod_i^{log}, (sid, j), (I_{\in}, K_j, ∆_j, \Gamma), \psi''_{i,j}) = 1$
- 计算 $\delta = \sum_j\delta_j$
- 验证 $g^{\delta} = \prod_j∆_j$
计算随机点 $R = \Gamma^{\delta^{-1}}$，推导如下
$$ \begin{align} R &= g^{k^{-1}} \\ &=g^{(k\gamma)^{-1} \cdot \gamma} \\ &=g^{((k_1 + k_2 + k_3)(\gamma_1 + \gamma_2 + \gamma_3))^{-1} \cdot (\gamma_1 + \gamma_2 + \gamma_3)} \\ &= g^{\begin{pmatrix} k_1\gamma_1 + k_1\gamma_2 + k_1\gamma_3 + \\ k_2\gamma_1 + k_2\gamma_2 + k_2\gamma_3 + \\ k_3\gamma_1 + k_3\gamma_2 + k_3\gamma_3\end{pmatrix}^{-1} \cdot (\gamma_1 + \gamma_2 + \gamma_3)}\\ &= g^{\begin{pmatrix} k_1\gamma_1 + (\alpha_{1,2}+\beta_{2,1}) + (\alpha_{1,3}+\beta_{3,1}) + \\ (\alpha_{2,1}+\beta_{1,2}) + k_2\gamma_2 + (\alpha_{2,3}+\beta_{3,2}) + \\ (\alpha_{3,1}+\beta_{3,2}) + (\alpha_{3,2}+\beta_{2,3}) + k_3\gamma_3\end{pmatrix}^{-1} \cdot (\gamma_1 + \gamma_2 + \gamma_3)}\\ &=(g^{\gamma_1 + \gamma_2 + \gamma_3})^{\begin{pmatrix} k_1\gamma_1 + \alpha_{1,2}+\beta_{2,1} + \alpha_{1,3}+\beta_{3,1}) + \\ \alpha_{2,1}+\beta_{1,2} + k_2\gamma_2 + \alpha_{2,3}+\beta_{3,2} + \\ \alpha_{3,1}+\beta_{3,2} + \alpha_{3,2}+\beta_{2,3} + k_3\gamma_3\end{pmatrix}^{-1}}\\ &= (\Gamma_1 + \Gamma_2 + \Gamma_3) ^{\begin{pmatrix} k_1\gamma_1 + \alpha_{1,2}+\beta_{2,1} + \alpha_{1,3}+\beta_{3,1}) + \\ \alpha_{2,1}+\beta_{1,2} + k_2\gamma_2 + \alpha_{2,3}+\beta_{3,2} + \\ \alpha_{3,1}+\beta_{3,2} + \alpha_{3,2}+\beta_{2,3} + k_3\gamma_3\end{pmatrix}^{-1}} \\ &= \Gamma^{(\delta_1 + \delta_2 + \delta_3)^{-1}} \\ &= \Gamma^{\delta^{-1}} \end{align} $$
signing
round_1
- 输入：$(sid, l, i,m)$
- 设 $r$ 为 $R$ 的横坐标，计算签名分片 $\sigma_i = k_im + r\chi_i$
- 向 $P_j$ 发送 $(sid, i, \sigma_i)$
- 删除 $(sid, l, R, k_i, \chi_i)$
final
- 收到 $P_j$ 的 $(sid, j, \sigma_j)$
计算签名 $\sigma = \sum_j\sigma_j$，推导如下
$$ \begin{align} s &= k(m+rx) \\ &=mk + rkx \\ &=m(k_1 + k_2 + k_3) + r(k_1 + k_2 + k_3)(x_1 + x_2 + x_3) \\ &= m(k_1 + k_2 + k_3) + r\begin{pmatrix} k_1x_1 + k_1x_2 + k_1x_3 + \\ k_2x_1 + k_2x_2 + k_2x_3 + \\ k_3x_1 + k_3x_2 + k_3x_3\end{pmatrix}^{-1} \\ &= m(k_1 + k_2 + k_3) + r\begin{pmatrix} k_1x_1 + (\hat{\alpha_{1,2}}+\hat{\beta_{2,1}}) + (\hat{\alpha_{1,3}}+\hat{\beta_{3,1}}) + \\ (\hat{\alpha_{2,1}}+\hat{\beta_{1,2}}) + k_2x_2 + (\hat{\alpha_{2,3}}+\hat{\beta_{3,2}}) + \\ (\hat{\alpha_{3,1}}+\hat{\beta_{3,2}}) + (\hat{\alpha_{3,2}}+\hat{\beta_{2,3}}) + k_3x_3\end{pmatrix}^{-1} \\ &= m(k_1 + k_2 + k_3) + r\begin{pmatrix} k_1x_1 + \hat{\alpha_{1,2}}+\hat{\beta_{2,1}} + \hat{\alpha_{1,3}}+\hat{\beta_{3,1}}) + \\ \hat{\alpha_{2,1}}+\hat{\beta_{1,2}} + k_2x_2 + \hat{\alpha_{2,3}}+\hat{\beta_{3,2}} + \\ \hat{\alpha_{3,1}}+\hat{\beta_{3,2}} + \hat{\alpha_{3,2}}+\hat{\beta_{2,3}} + k_3x_3\end{pmatrix}^{-1} \\ &= m(k_1 + k_2 + k_3) + r(\chi_1 + \chi_2 + \chi_3)\\ &= (mk_1 + r\sigma_1) + (mk_2 + r\sigma_2) + (mk_3 + r\sigma_3) \end{align} $$
没有评论