BLS Threshold Signature

本文将介绍 BLS 门限签名，它比 ECDSA 门限签名要简单很多。

设共有 $n$ 个参与者，下面将介绍一个门限为 $t$ 的 BLS 签名方案，即生成群体签名时至少需要 $t$ 个参与者配合（小于 $t$ 个参与者不能生成群体签名）。

这里关注的重点是签名方案，不关心它的 DKG 方案。假设采用 Shamir's Secret Sharing 方案，Trusted Dealer 把群体私钥 $k$ 做为某个 $t-1$ 次多项式 $x=0$ 时的值 $f(0)$ ，这个多项式中取 $n$ 个点 $(x_1,k_1),\cdots ,(x_n,k_n)$ ，分别发送给 $n$ 个参与者。

任何 $t$ 个参与者，利用 $(x_1,k_1),\cdots ,(x_t,k_t)$ 可以恢复出完整私钥 $$k=\sum _{i=1}^t\left(\prod _{j=1,j\ne i}^t\frac{x_j}{x_j-x_i}\right)k_i$$

BLS 门限签名的思路： 每个参与者把 $k_i$ 作为 BLS 私钥生成签名 $S_i=k_i\cdot H(m)$ ，发送给其它的参与者；每个参与者收集到其它人发来的签名后，进行签名校验，一旦收集到 $t$ 个通过校验的合法签名后，把这 $t$ 个签名 $S_i$ 通过 Lagrange 插值计算出对应的零点函数值，把它记为 $S$ ， $S$ 就是群体签名。

下面验证一下 $S$ 确实是群体私钥 $k$ 对应的签名 $$\begin{array}{rl}S& \triangleq \sum _{i=1}^t\left(\prod _{j=1,j\ne i}^t\frac{x_j}{x_j-x_i}\right)\cdot S_i\\ & =\sum _{i=1}^t\left(\prod _{j=1,j\ne i}^t\frac{x_j}{x_j-x_i}\right)\cdot (k_i\cdot H(m))\\ & =\left(\sum _{i=1}^t\left(\prod _{j=1,j\ne i}^t\frac{x_j}{x_j-x_i}\right)k_i\right)\cdot H(m)\\ & =k\cdot H(m)\end{array}$$

1. Threshold BLS Signatures, by Jake Craige
   
2. Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme
   
3. Fast and Scalable BLS Threshold Signatures 介绍利用更快的多项式插值来加快门限签名的计算