Key Generation

原理

输入： party 下标 $i$，party 数量 $n$，门限 $t$，曲线 $E$，其生成元为 $G$，阶为 $q$

  • round_1

    • 随机选择 $s_{i,0},...s_{i,t-1} \leftarrow Z_q$，令 $\vec{S_i}=(s_{i,k} \cdot G)_{k \in [t]}$，$f_i(x)=\sum_{k \in [t]}s_{i,k} \cdot x^k$，$F_i(x)=f(x) \cdot G$
    • 计算 $\sigma_{i,j}=f_i(j+1)$，$j \in [n]$
    • 随机选择 $rid_i \leftarrow \left\{i,1\right\}^k$
    • zk-schnorr 承诺： $(A_i,\tau_i) \leftarrow M(com, \prod^{sch})$，其中 $A_i=g^{\tau_i}$ 是 proof，$\tau_i$ 是随机数
    • HD-wallet：随机选择 chain code $c_i \leftarrow \left\{0,1\right\}^{128}$（32-bytes）
    • 随机选择 $u_i \leftarrow \left\{0,1\right\}^k$ 并计算承诺 $V_i=H(sid || n || i || t || rid_i || \vec{S_i} || A_i || u_i || c_i)$
    • 广播 $V_i$

  • round_2

    • 收到其它 party 的 $V_j$
    • 广播 $(rid_i, \vec{S_i}, A_i, u_i, c_i)$
    • P2P 向 $P_j$ 发送 $\sigma_{i,j}$

  • round_3

    • 收到其它 party 的 $(rid_j, \vec{S_j}, A_j, u_j, c_j)$ 和 $\sigma_{j,i}$

      • 检查 $\vec{S_j}$ 的度是否为 $t$
      • 检查 $V_j==H(sid || n || j || t || rid_j || \vec{S_j} || A_j || u_j || c_j)$
      • 定义 $F_j(x)=\sum_{k\in[t]}x^k\cdot S_{j,k}$
      • 检查 $\sigma_{j,i}\cdot G=F_j(i+1)$
    • 计算 $rid = \bigoplus_{j\in[n]}rid_j$
    • HD-wallet：计算 chain code $c = \bigoplus_{j\in[n]}c_j$
    • 令 $F(x)=\sum_{k \in [t]}x^k \cdot (\sum_{j \in [n]}S_{j,k}) =\sum_{j \in [n]}F_j(x)$
    • 对于 $j \in [n]$，计算所有公钥分片 $X_j=F(j+1)$
    • 计算私钥分片 $x_i=\sum_{j \in [n]}\sigma_{j,i}$
    • 计算挑战 $e_i=H(sid||i||rid||X_i||A_i)$
    • zk-schnorr 证明知道私钥分片 $\sigma_i$：$\psi_i=M(prov, \prod^{sch}, e_i, \sigma_i, \tau_i)$
    • 广播 $\psi_i$

  • final

    • 收到其它 party 的 $\psi_j$
    • 计算 $e_j=H(sid||j||rid||X_j||A_j)$，并验证 $M(verify, \prod^{sch}, A_j,e_j,X_j)=1$
    • 计算共享公钥 $Y=\sum_{j\in[n]}S_{j,0}$
    • 计算身份映射关系 $I : I(i)=i+1$
    • 输出 $(Y, x_i, \vec{X}, I, c)$

例子

  1. 对于 3 / 3，各方构造随机多项式

    $$ \begin{align} &p_1(x) = 1 + 2x + 3x^2 \\ &p_2(x) = 2 + 3x + x^2 \\ &p_3(x) = 3 + x + 2x^2\\ \end{align} $$

  2. 各方算出 $p_i(j)$

    $$ \begin{align} &p_1(1)=6, \space p_1(2)=17, \space p_1(3)=34 \\ &p_2(1)=6, \space p_2(2)=12, \space p_3(3)=20 \\ &p_3(1)=6, \space p_3(2)=13, \space p_3(3)=24 \\ \end{align} $$

  3. 各方算出私钥分片

    $$ \begin{align} &x_1=6 + 6 + 6=18\\ &x_2 = 17 + 12 + 13 = 42\\ &x_3=34 + 20 + 24 = 78\\ \end{align} $$

  4. 共享根私钥为各多项式常数项之和：$x=1+2+3=6$

    共享根私钥和根私钥分片之前满足拉格朗日插值：

    $$ \begin{align} 6&=\frac{x-2}{1-2}\frac{x-3}{1-3} \cdot 18 + \frac{x-1}{2-1}\frac{x-3}{2-3} \cdot 42 + \frac{x-1}{3-1}\frac{x-2}{3-2} \cdot 78 \\ &=\frac{0-2}{1-2}\frac{0-3}{1-3} \cdot 18 + \frac{0-1}{2-1}\frac{0-3}{2-3} \cdot 42 + \frac{0-1}{3-1}\frac{0-2}{3-2} \cdot 78 \\ &=3 \times 18 - 3 \times 42 + 1 \times 78 \end{align} $$

Key Refresh

  • refresh 前

    • 根私钥分片：18, 42, 78
    • 共享根私钥：6

  • refresh

    • a 产生新的常数项为 0 的随机多项式 $f_1(x)=2x+x^2$
    • b 产生新的常数项为 0 的随机多项式 $f_2(x)=x+3x^2$
    • c 产生新的常数项为 0 的随机多项式 $f_3(x)=x+2x^2$

  • refresh 后

    • 根私钥分片：

      • $18 + f_1(1)+f_2(1)+f_3(1)=28$
      • $42 + f_1(2)+f_2(2)+f_3(2)=74$
      • $78 + f_1(3)+f_2(3)+f_3(3)=144$
    • 共享根私钥：

    $$ \begin{align} 6&=\frac{x-2}{1-2}\frac{x-3}{1-3} \cdot 28 + \frac{x-1}{2-1}\frac{x-3}{2-3} \cdot 74 + \frac{x-1}{3-1}\frac{x-2}{3-2} \cdot 144 \\ &=\frac{0-2}{1-2}\frac{0-3}{1-3} \cdot 28 + \frac{0-1}{2-1}\frac{0-3}{2-3} \cdot 74 + \frac{0-1}{3-1}\frac{0-2}{3-2} \cdot 144 \\ &=3 \times 28 - 3 \times 74 + 1 \times 144 \end{align} $$

Auxiliary Information

输入：party 下标 $i$，sid

  • round_1

    • 生成 4k-bit 安全素数 $p_i, q_i$
    • 生成 Paillier 公钥 $N_i=p_iq_i$ 和私钥 $\phi=(p_i-1)(q_i-1)$
    • 生成 ring-Pedersen 公钥 $(N_i, s_i, t_i)$ 和 私钥 $\lambda$：随机选择 $r \leftarrow Z_{N_i}^*$ 和 $\lambda \leftarrow Z_{\phi}$，计算 $t_i=r_i^2$ mod $N_i$ 和 $s_i=t_i^{\lambda}$ mod $N_i$

    • 生成 Ring-Pedersen Parameters 证明 $R_{prm}=\left\{(N,s,t;\lambda)|s=t^{\lambda }\space mod \space N\right\}$

      $\hat{\psi_i}=M(prove, \prod^{prm}, (sid ||i), (N_i, s_i, t_i); \lambda)$

    • 随机选择 $\rho_i, u_i \leftarrow \left\{0,1\right\}^k$，计算 $V_i=H(sid||n||i||N_i||s_i||t_i||\hat{phi}||\rho_i||u_i)$
    • 广播 $V_i$

  • round_2

    • 收到其它 party 的 $V_j$
    • 广播 $(N_i, s_i, t_i, \hat{\psi_i}, \rho_i, u_i)$

  • round_3

    • 收到其它 party 的 $(N_j, s_j, t_j, \hat{\psi_j}, \rho_j, u_j)$
    • 对于所有 $j \in [n]$，令 $R_j=(N_j,s_j,t_j)$，得到向量 $\vec{R}=(R_j)_{j \in [n]}$

    • 对于 $j \ne i$

      • 验证 $V_j=H(sid||n||j||N_j||s_j||t_j||\hat{phi}||\rho_j||u_j)$
      • 验证 $N_j$ 长度至少为 8k-1 比特
      • 验证 $M(verify, \prod^{prm}, (sid ||i), (N_i, s_i, t_i), \hat{\psi_i})=1$
      • 获得 Paillier 公钥 $N_j$
    • 计算 $\rho = \bigoplus_j \rho_j$

    • 生成 Paillier-Blum Modulus 证明 $R_{mod}=\left\{(N;p,q)| p,q=3 \space mod \space 4 \in PRIMES ∧ N=pq ∧ gcd(N,\phi(N))=1\right\}$

      $\psi_i=M(prove, \prod^{mod}, (sid||i||\rho), N_i, (p_i,q_i))$

    • 对于 $j\ne i$

      • 生成 No Small Factor Modulus 证明 $R_{fac}=\left\{(l,N;p,q)|N=pq ∧ p,q>2^l\right\}$

        $\phi_i^j=M(prove, \prod^{fac}, (sid||i||\rho), R_j, N_i, (p_i,q_i))$

      • P2P 向 $P_j$ 发送 $(\psi_i, \phi_i^j)$

  • final

    • 收到其它 party 的 $(\psi_j, \phi_j^i)$

    • 对于 $j \ne i$

      • 验证 $M(verify, \prod^{mod}, (sid||j||\rho), N_j, \psi_j)=1$
      • 验证 $M(verify, \prod^{fac}, (sid||j||\rho), R_i,N_j,\phi_j^i)=1$
    • 输出 $(p_i,q_i,\vec{R})$

Pre-Signing

输入：门限 $t$，sid，曲线 $E$ 的生成元 $G$，阶为 $q$

party 总数量为 $n$，$S(i): [t] \rightarrow [n]$ 为 party $P_i$ 在 key-generation 时的下标，私钥分片 $x'_{S(i)}$，公钥分片 $\vec{X'}=(X_j')_{j\in [n]}$，映射关系 $I: [n] \rightarrow F_q^*$ ，Paillier 私钥 $sk_{S(i)}$，公钥 $\vec{N'}=(N'_j)_{j \in [n]}$，auxiliar information $\vec{R'}=(s_j,t_j,\hat{N}_{j\in[n]})$

Step1. 令 $sk_i=sk_{S(i)}$，$\hat{R}=(R'_{S(j)})_{j \in [n]}$

  • 对于 $j \in [t]$，计算拉格朗日插值 $\lambda_j=\prod_{i\in [t] / \left\{j\right\}} \frac{I(S(i))}{I(S(i))-I(S(j))}$ mod $q$
  • 计算 $x_i=\lambda_i \cdot x'_{S(i)}$
  • 对于 $j \in [t]$，计算 $X_j=\lambda_j \cdot X'_{S(j)}$，令 $\vec{X}=\left\{X_j\right\}_{j\in [t]}$

Step2. HD-wallet：

  • 令 $X_0=X_0 + shift \cdot G$
  • 如果 $i=0$，令 $x_0= x_0 + shift$
  • 注意：共享公钥为 $Y + shift \cdot G$

Step3. 调用 non-threshold pre-signing 协议

Signing

  • HD-wallet：$\chi = \chi + k \cdot shift$
  • $r = R|_x$，$\sigma_i=km + r \chi$
  • 输出 $(r, \sigma_i)$

参考

cggmp21