Theshold BBS+

Threshold BBS+ Signatures for Distributed Anonymous Credential Issuance

BBS+ 基本流程

1. KeyGen

• 假设待签名消息数量为 $\ell$
• 选择生成元 $G_1\in {\mathbb{G}}_1$、$G_2\in {\mathbb{G}}_2$
• 随机选择 $\ell +1$ 个元素，记为

$$\mathbf{H}=(H_1,H_2,\dots ,H_{\ell +1}),H_i\in {\mathbb{G}}_1$$

• 随机选择私钥 $x\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$
• 计算公钥元素

$$X=x\cdot G_2\in {\mathbb{G}}_2$$

• 输出：
  • 公钥 $pk=(G_1,G_2,\mathbf{H},X)$
  • 私钥 $sk=x$

2. Sign

给定消息向量：

$$\mathbf{m}=(m_1,m_2,\dots ,m_{\ell }),m_i\in {\mathbb{Z}}_p$$

签名者执行：

• 采样随机数 $e,s\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$
• 构造承诺基点：

$$C=G_1+s\cdot H_1+\sum _{i=1}^{\ell }{m}_i\cdot H_{i+1}$$

• 计算

$$A=(x+e{)}^{-1}\cdot C$$

• 输出签名：

$$\sigma =(A,e,s)$$

3. Verify

给定消息向量 $\mathbf{m}$ 和签名 $\sigma =(A,e,s)$，验证者检查：

$$e(A,X+e\cdot G_2)\stackrel{?}{=}e(G_1+s\cdot H_1+\sum _{i=1}^{\ell }{m}_i\cdot H_{i+1},G_2)$$

若等式成立，则接受该签名。

4. 正确性

因为

$$A=(x+e{)}^{-1}\cdot (G_1+s\cdot H_1+\sum _{i=1}^{\ell }{m}_i\cdot H_{i+1})$$

所以：

$$\begin{array}{rl}e(A,X+e\cdot G_2)& =e((x+e{)}^{-1}\cdot (G_1+s\cdot H_1+\sum _{i=1}^{\ell }{m}_i\cdot H_{i+1}),(x+e)\cdot G_2)\\ & =e(G_1+s\cdot H_1+\sum _{i=1}^{\ell }{m}_i\cdot H_{i+1},G_2)\end{array}$$

因此验证方程成立。

Blind BBS+

普通 BBS+ 中，签名者直接看到全部消息。盲签名场景下，用户希望：

• 某些消息对签名者可见；
• 某些消息对签名者隐藏；
• 签名者最终仍然对完整消息向量签名。

这时需要补充 blind、blind sign 和 unblind 三步。

1. 消息划分

设消息集合被拆成两部分：

• 显式消息（签名者可见）：$\{m_i{\}}_{i\in \mathcal{R}}$
• 隐藏消息（签名者不可见）：$\{m_j{\}}_{j\in \mathcal{H}}$

其中 $\mathcal{R}\cup \mathcal{H}=\{1,2,\dots ,\ell \}$，且 $\mathcal{R}\cap \mathcal{H}=\varnothing$。

2. Blind

用户先对隐藏消息做一个承诺，并发送给签名者。

• 用户随机选择盲化因子 $r\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$
• 计算隐藏消息承诺：

$$C_{blind}=r\cdot H_1+\sum _{j\in \mathcal{H}}{m}_j\cdot H_{j+1}$$

• 用户将 $C_{blind}$ 发送给签名者

在更严格的协议中，用户还需要附带一个零知识证明，证明自己确实知道 $(r,\{m_j{\}}_{j\in \mathcal{H}})$，否则签名者可能会在无效承诺上签名。

3. Proof of Knowledge of Commitment（PoK）

为了让签名者相信用户不是随意伪造一个群元素，而是真的知道隐藏消息与盲化因子，用户需要对 $C_{blind}$ 附带一个知识证明。

设隐藏消息个数为 $|\mathcal{H}|$，用户要证明自己知道：

• 盲化因子 $r$；
• 隐藏消息 $\{m_j{\}}_{j\in \mathcal{H}}$；
• 且它们满足

$$C_{blind}=r\cdot H_1+\sum _{j\in \mathcal{H}}{m}_j\cdot H_{j+1}$$

这可以用一个基于 Fiat--Shamir 变换的 Sigma 协议来实现。

Prove

用户执行：

• 随机选择掩码

$$\tilde{r}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p,{\tilde{m}}_j\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p(j\in \mathcal{H})$$

• 构造临时承诺

$$T=\tilde{r}\cdot H_1+\sum _{j\in \mathcal{H}}{\tilde{m}}_j\cdot H_{j+1}$$

• 计算挑战

$$c=Hash(C_{blind},T,|\mathcal{H}|)$$

• 计算响应值

$$\hat{s}=\tilde{r}+c\cdot r$$$${\hat{m}}_j={\tilde{m}}_j+c\cdot m_j(j\in \mathcal{H})$$

• 输出证明

$${\pi }_{pok}=(T,c,\hat{s},\{{\hat{m}}_j{\}}_{j\in \mathcal{H}})$$

Verify

签名者收到 $(C_{blind},{\pi }_{pok})$ 后，执行：

• 重新计算挑战

$$c^{\prime }=Hash(C_{blind},T,|\mathcal{H}|)$$

• 检查 $c^{\prime }=c$

• 检查如下等式是否成立：

$$\hat{s}\cdot H_1+\sum _{j\in \mathcal{H}}{\hat{m}}_j\cdot H_{j+1}\stackrel{?}{=}T+c\cdot C_{blind}$$

若成立，则说明用户确实知道对应的盲化因子和隐藏消息；否则拒绝继续 blind signing。

为什么验证等式成立

因为

$$\begin{array}{rl}\hat{s}\cdot H_1+\sum _{j\in \mathcal{H}}{\hat{m}}_j\cdot H_{j+1}& =(\tilde{r}+cr)H_1+\sum _{j\in \mathcal{H}}({\tilde{m}}_j+c{m}_j)H_{j+1}\\ & =\tilde{r}{H}_1+\sum _{j\in \mathcal{H}}{\tilde{m}}_j{H}_{j+1}+c(r{H}_1+\sum _{j\in \mathcal{H}}{m}_j{H}_{j+1})\\ & =T+c\cdot C_{blind}\end{array}$$

因此只要用户知道 $(r,\{m_j\})$，它就能构造出可验证的响应；而不知道这些值的一方通常无法通过该检查。

4. BlindSign

签名者拿到：

• 可见消息 $\{m_i{\}}_{i\in \mathcal{R}}$
• 用户提交的承诺 $C_{blind}$
• 用户提交的知识证明 ${\pi }_{pok}$

签名者先验证 ${\pi }_{pok}$，仅在验证通过后继续签名。

然后：

• 采样随机数 $e,s^{\prime }\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$
• 构造待签名项

$$C^{\prime }=G_1+C_{blind}+s^{\prime }\cdot H_1+\sum _{i\in \mathcal{R}}{m}_i\cdot H_{i+1}$$

• 计算盲签名

$$A=(x+e{)}^{-1}\cdot C^{\prime }$$

• 输出给用户：

$${\sigma }^{\prime }=(A,e,s^{\prime })$$

5. Unblind

用户收到盲签名 ${\sigma }^{\prime }=(A,e,s^{\prime })$ 后，利用自己掌握的盲化因子 $r$ 计算最终签名。

注意到：

$$\begin{array}{rl}{C}^{\prime }& =G_1+C_{blind}+s^{\prime }\cdot H_1+\sum _{i\in \mathcal{R}}{m}_i\cdot H_{i+1}\\ & =G_1+(r\cdot H_1+\sum _{j\in \mathcal{H}}{m}_j\cdot H_{j+1})+s^{\prime }\cdot H_1+\sum _{i\in \mathcal{R}}{m}_i\cdot H_{i+1}\\ & =G_1+(s^{\prime }+r)\cdot H_1+\sum _{k=1}^{\ell }{m}_k\cdot H_{k+1}\end{array}$$

因此用户令：

$$s=s^{\prime }+r$$

并得到标准 BBS+ 签名：

$$\sigma =(A,e,s)$$

这个签名可直接按普通 Verify 算法验证。

6. 为什么解盲成立

由上式可知：

$$A=(x+e{)}^{-1}\cdot (G_1+s\cdot H_1+\sum _{k=1}^{\ell }{m}_k\cdot H_{k+1})$$

其中 $s=s^{\prime }+r$。所以解盲后的 $\sigma =(A,e,s)$ 与普通 BBS+ 输出格式完全一致。

门限设置下的 BBS+

在门限场景中，可将私钥 $x$ 通过秘密分享拆成 $n$ 份，使得任意 $t$ 份可恢复或协同计算。此时：

• 各参与方分别持有 $x$ 的份额；
• 在签名阶段通过 MPC 协同计算 $(x+e{)}^{-1}$；
• 最终得到与普通 BBS+ 一致的签名结果。

如果系统还要支持 blind signing，那么 MPC 参与方实际上是在对用户提交的承诺 $C_{blind}$ 与可见消息共同构成的目标项执行门限签名。

选择性披露（Selective Disclosure）

BBS+ 的核心优势之一，是签名生成后用户可以只披露部分消息，而不暴露全部消息内容。

1. 将 BBS+ 看作对承诺的签名

定义：

$$\begin{array}{rl}C& =G_1+s\cdot H_1+\sum _{i=1}^{\ell }{m}_i\cdot H_{i+1}\\ & =(x+e)\cdot A\end{array}$$

因此，签名实际上证明了签名者认可这组消息被编码进了承诺 $C$ 中。

2. 选择性披露的目标

用户持有 $(A,e,s,\mathbf{m})$，希望向验证者证明：

• 自己知道一个有效 BBS+ 签名；
• 某些消息 $m_i$ 被公开；
• 其余消息仍被隐藏，但签名依然对完整消息集有效。

设公开集合为 $\mathcal{R}$，隐藏集合为 $\mathcal{H}$，则目标关系可写成：

$$e(A,X+e{G}_2)=e(G_1+s{H}_1+\sum _{i\in \mathcal{R}}{m}_i{H}_{i+1}+\sum _{j\in \mathcal{H}}{m}_j{H}_{j+1},G_2)$$

验证者直接看到的是公开消息，而对隐藏消息部分，需要用户给出零知识证明，说明“存在某些未公开消息使得上式成立”。

3. 可用的证明工具

• 可以使用多底数离散对数知识证明；
• 实现上通常可借助一个或多个 Sigma 协议；
• 若还要证明隐藏属性满足区间、年龄门槛等条件，则可叠加范围证明，如 Bulletproofs。

4. 不可链接性

选择性披露协议通常会对签名进行随机化处理。由于每次证明都会重新采样随机数，验证者即使多次看到同一份凭证导出的证明，也无法轻易判断它们是否来自同一用户，因此具备较好的不可链接性。