论文：FROST: Flexible Round-Optimized Schnorr Threshold Signatures

pre-signing

每个成员都参与，提前生成 $\pi$ 个数据，可以被 $\pi$ 次 signing 使用，用来生成签名中所需的 nonce。

  • round_1

    • $P_i$ 创建一个空列表 $L_i$，对于 $j \in [1,\pi]$

      • 随机选择 $d_{i,j} \leftarrow Z_q^*$ 和 $e_{i,j} \leftarrow Z_q^*$
      • 计算承诺 $D_{i,j}=g^{d_{i,j}}$ 和 $E_{i,j} =g^{e_{i,j}}$
      • 将 $(D_{i,j}, E_{i,j})$ 存到 $L_i$，保存 $((d_{i,j}, D_{i,j}), (e_{i,j},E_{i,j}))$，以供后续签名使用
    • 将 $(i,L_i)$ 存储到预定位置

signing

$SA$ 是签名聚合者，可以是参与签名的任意一方。$S$ 是参与签名的集合，$X$ 是公共公钥，$B=<(i,D_i,E_i)>_{i\in S}$ 是一个列表，包含了每个参与签名方在 pre-signing 生成的数据。$x_i$ 是 $P_i$ 的私钥，$H_1, H_2$ 是哈希函数，输出位于空间 $Z_q^*$ 内。$m$ 是要签名的消息。

  • round_0

    • $SA$ 选择下一个可用的 $L_i$，并构建 $B$
    • 向每个 $P_i$ 发送 $(m, B)$

  • round_1

    • $P_i$ 收到 $(m, B)$，验证消息 $m$，并检查 $B$ 中的每个 $D_j,E_j \in G^*$ 是否满足
    • 计算消息绑定值 $\rho_i=H_1(i,m,B)$

    • 为每个 $P_j$ 计算 $R_j=D_j \cdot (E_j)^{\rho_j}$，从而得到承诺 $R=\prod_{j\in S}R_j$

      $\rho_i$ 与消息绑定了，以避免攻击者操纵 $R$ 的结果，从而操纵 $c$，具体见论文 2.5 节

    • 计算挑战 $c=H_2(R,X,m)$

    • 计算 nonce 值 $k_i=d_i+(e_i\cdot \rho_i)$

      因为 $\rho_i$ 与消息绑定了，所以每个消息都会生成不同的 $k_i$，否则会泄露私钥

    • 计算签名分片 $s_i=k_i+\lambda_i \cdot x_i \cdot c$

      其中 $\lambda_i$ 是拉格朗日插值系数，$\lambda_i \cdot x_i$ 是私钥分片的加性份额

    • 将 $s_i$ 发送给 $SA$

  • final

    $SA$ 执行如下操作

    • 为每个 $P_i$ 计算 $\rho_i=H_1(i,m,B)$ 和 $R_i=D_{i,j} \cdot E_{i,j}^{\rho_i}$
    • 恢复 $R=\prod_{i\in S}R_i$
    • 恢复 $c=H_2(R,X,m)$

    • 校验响应的合法性，验证 $g^{s_i}=R_i \cdot X_i^{c \cdot \lambda_i}$ 是否满足

      推导：$g^{s_i}=g^{d_i+(e_i\cdot \rho_i)+\lambda_i \cdot x_i \cdot c}=D_j \cdot (E_j)^{\rho_j} \cdot X_i^{c \cdot \lambda_i} = R_i \cdot X_i^{c \cdot \lambda_i}$

    • 计算 $s = \sum s_i$

    • 发布签名 $\sigma = (R,s)$

      推导如下

      $$ \begin{align} s &= k+x \cdot H_2(R,Y,m)= k + x \cdot c \\ &=(k_1 + \lambda_1x_1 \cdot c) + (k_2 + \lambda_2x_2 \cdot c) + (k_3 + \lambda_3x_3 \cdot c))\\ &= (d_1 + e_1\rho_1 + \lambda_1x_1 \cdot c) + (d_2 + e_2\rho_2 + \lambda_2x_2 \cdot c) + (d_3 + e_3\rho_3 + \lambda_3x_3 \cdot c))\\ \end{align} $$

验证签名

椭圆曲线中，群运算用加法符号和乘法符号都是可以的，下面为了让公式中的字符更清晰，采用了加法形式。

  • 计算 $P_1 = z \cdot g$
  • 计算 $P_2 = R + X \cdot H_2(R,Y,m)$

  • 验证 $P_1 == P_2$

    推导如下：

$$ \begin{align} z \cdot g &= (\sum{z_i}) \cdot g \\ &= ((d_1 + e_1\rho_1 + \lambda_1x_1 \cdot c) + (d_2 + e_2\rho_2 + \lambda_2x_2 \cdot c) + (d_3 + e_3\rho_3 + \lambda_3x_3 \cdot c)) \cdot g \\ &=((d_1 + e_1\rho_1) + (d_2 + e_2\rho_2) + (d_3 + e_3\rho_3)) \cdot g + (\lambda_1x_1+\lambda_2x_2+\lambda_3x_3) \cdot g \cdot c\\ &= (k_1 + k_2 + k_3) \cdot g + x \cdot g \cdot c \\ &= R + X \cdot H_2(R,Y,m) \end{align} $$