BBS+ Signature

Threshold BBS+ Signatures for Distributed Anonymous Credential Issuance

Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited

BBS+ 基本流程

1. KeyGen

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

$$\mathbf{H}=(H_0,H_1,\dots ,H_{\ell }),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_0+\sum _{i=1}^{\ell }{m}_i\cdot H_i$$

• 计算

$$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_0+\sum _{i=1}^{\ell }{m}_i\cdot H_i,G_2)$$

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

4. 正确性

因为

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

所以：

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

因此验证方程成立。

弱盲签名下的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_0+\sum _{j\in \mathcal{H}}{m}_j\cdot H_j$$

• 用户将 $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_0+\sum _{j\in \mathcal{H}}{m}_j\cdot H_j$$

这可以用一个基于 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_0+\sum _{j\in \mathcal{H}}{\tilde{m}}_j\cdot H_j$$

• 计算挑战

$$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_0+\sum _{j\in \mathcal{H}}{\hat{m}}_j\cdot H_j\stackrel{?}{=}T+c\cdot C_{blind}$$

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

为什么验证等式成立

因为

$$\begin{array}{rl}\hat{s}\cdot H_0+\sum _{j\in \mathcal{H}}{\hat{m}}_j\cdot H_j& =(\tilde{r}+cr)H_0+\sum _{j\in \mathcal{H}}({\tilde{m}}_j+c{m}_j)H_j\\ & =\tilde{r}{H}_0+\sum _{j\in \mathcal{H}}{\tilde{m}}_j{H}_j+c(r{H}_0+\sum _{j\in \mathcal{H}}{m}_j{H}_j)\\ & =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_0+\sum _{i\in \mathcal{R}}{m}_i\cdot H_i$$

• 计算盲签名

$$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_0+\sum _{i\in \mathcal{R}}{m}_i\cdot H_i\\ & =G_1+(r\cdot H_0+\sum _{j\in \mathcal{H}}{m}_j\cdot H_j)+s^{\prime }\cdot H_0+\sum _{i\in \mathcal{R}}{m}_i\cdot H_i\\ & =G_1+(s^{\prime }+r)\cdot H_0+\sum _{k=1}^{\ell }{m}_k\cdot H_k\end{array}$$

因此用户令：

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

并得到标准 BBS+ 签名：

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

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

6. 为什么解盲成立

由上式可知：

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

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

deprecated

7. 签名重随机

但是很显然，对于签名 $\sigma =(A,e,s)$ , 签名者给出的 $A$ 和用户最终出示的 $A$ 都是一致的，不满足盲签名的不可链接性，我们需要继续进行如下操作：

• sample $r^{\prime }\leftarrow {\mathbb{Z}}_p$
• let $A^{\prime }=A+r^{\prime }\cdot G_1$
• so the signature is $\sigma =(A^{\prime },e,s,r^{\prime })$

此时，我们让验签变为：

$$\begin{array}{rl}e(A^{\prime },X+e\cdot G_2)& =e(A+r^{\prime }{G}_1,X+e{G}_2)\\ & =e(A,X+e{G}_2)\cdot e(r^{\prime }{G}_1,X+e{G}_2)\\ & =e(C,G_2)\cdot e(r^{\prime }{G}_1,(x+e)G_2)\\ & =e(C,G_2)\cdot e(r^{\prime }(x+e)G_1,G_2)\\ & =e(C+r^{\prime }(x+e)G_1,G_2)\\ & \stackrel{?}{=}e(C+r^{\prime }(X+e{G}_1),G_2)\end{array}$$

选择性披露（Selective Disclosure）

BBS+ 的核心优势之一，是签名生成后用户可以只披露部分消息，而其余消息保持隐藏，同时仍能证明签名对完整消息向量有效。

1. 核心思想

签名本质上是对承诺 $C$ 的签名：

$$C=G_1+s\cdot H_0+\sum _{i=1}^{\ell }{m}_i\cdot H_i=(x+e)\cdot A$$

选择性披露的目标：用户持有 $(A,e,s,\mathbf{m})$，希望向验证者证明

• 自己知道一个有效的 BBS+ 签名；
• 公开集合 $\mathcal{D}\subseteq \{1,\dots ,\ell \}$ 中的消息 $m_i$（$i\in \mathcal{D}$）被正确公开；
• 隐藏集合 $\bar{\mathcal{D}}=\{1,\dots ,\ell \}\setminus \mathcal{D}$ 中的消息仍被隐藏，但签名对完整 $\mathbf{m}$ 依然有效。

2. 凭证随机化（Credential Randomization）

用户执行以下随机化步骤：

1. 采样随机化因子 $r_1\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p^{\ast }$

2. 计算随机化后的 $A^{\prime }$：

   $$A^{\prime }\leftarrow r_1\cdot A$$

3. 计算 $r_3\leftarrow r_1^{-1}$

4. 计算 $\overline{A}$（隐藏 $x$ 的信息）：

   $$\overline{A}\leftarrow r_1\cdot C-e\cdot A^{\prime }$$

5. 采样 $r_2\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$

6. 计算辅助值 $d$ 和 $s^{\prime }$：

   $$d\leftarrow r_1\cdot C-r_2\cdot H_0,s^{\prime }\leftarrow s-r_2\cdot r_3$$

3. 零知识证明（NIZK / SPK）

用户生成非交互零知识证明（NIZK），证明自己知道隐藏消息、$e$、$r_2$、$r_3$、$s^{\prime }$。

Prover（生成证明 $\pi$）

1. 生成随机掩码（Commit）：

   $${\tilde{m}}_i\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p(i\in \bar{\mathcal{D}}),\tilde{e},{\tilde{r}}_2,{\tilde{r}}_3,{\tilde{s}}^{\prime }\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$$

2. 计算临时承诺 $t_1,t_2$：

   $$t_1=A^{\prime \tilde{e}}\cdot H_0^{{\tilde{r}}_2}\cdot (\overline{A}/d{)}^{-\tilde{e}}$$$$t_2=d^{{\tilde{r}}_3}\cdot H_0^{{\tilde{s}}^{\prime }}\cdot \prod _{i\in \bar{\mathcal{D}}}{H}_i^{-{\tilde{m}}_i}\cdot (G_1+\sum _{i\in \mathcal{D}}{m}_i\cdot H_i{)}^{-\tilde{e}}$$

3. 计算挑战（Fiat-Shamir）：

   $$\mathcal{c}=\mathrm{Hash}(A^{\prime },\overline{A},d,t_1,t_2,G_1,H_0,\dots ,H_{\ell },X,m)$$

4. 计算响应值：

   $$s_i={\tilde{m}}_i+c\cdot m_i(i\in \bar{\mathcal{D}})$$$$s_e=\tilde{e}+c\cdot e,s_{r2}={\tilde{r}}_2+c\cdot r_2,s_{r3}={\tilde{r}}_3+c\cdot r_3,s_{s^{\prime }}={\tilde{s}}^{\prime }+c\cdot s^{\prime }$$

5. 输出证明：

   $$\pi =(c,\{s_i{\}}_{i\in \bar{\mathcal{D}}},s_e,s_{r2},s_{r3},s_{s^{\prime }})$$

最终输出的选择性披露凭证为四元组：

$$\sigma =(A^{\prime },\overline{A},d,\pi )$$

Verifier（验证 $\pi$）

1. 检查 $A^{\prime }\ne 0_{{\mathbb{G}}_1}$

2. 检查一个 pairing 等式（只需 1 个 pairing）：

   $$e(A^{\prime },X)\stackrel{?}{=}e(\overline{A},G_2)$$

3. 重新计算承诺并验证挑战：

   $${\hat{t}}_1=A^{\prime s_e}\cdot H_0^{s_{r2}}\cdot (\overline{A}/d{)}^{-s_e}$$$${\hat{t}}_2=d^{s_{r3}}\cdot H_0^{s_{s^{\prime }}}\cdot \prod _{i\in \bar{\mathcal{D}}}{H}_i^{-s_i}\cdot (G_1+\sum _{i\in \mathcal{D}}{m}_i\cdot H_i{)}^{-s_e}$$$$c^{\prime }=\mathrm{Hash}(A^{\prime },\overline{A},d,{\hat{t}}_1,{\hat{t}}_2,G_1,H_0,\dots ,H_{\ell },X,m)$$

   检查 $c^{\prime }\stackrel{?}{=}c$

若全部通过，则接受该选择性披露证明。

4. 正确性证明

• pairing:

• $$\begin{array}{rl}lhs& =e(A^{\prime },X)\\ & =e(r_{1}A,X)\\ & =e(\frac{r_{1}C}{x+e},X)\\ & =e(\frac{r_{1}xC}{x+e},G_2)\\ rhs& =e(\overline{A},G_2)\\ & =e(r_{1}C-e{r}_{1}A,G_2)\\ & =e(r_{1}C-\frac{e{r}_{1}C}{x+e},G_2)\\ & =e(\frac{x{r}_{1}C+e{r}_{1}C-e{r}_{1}C}{x+e},G_2)\\ & =e(\frac{r_{1}xC}{x+e},G_2)\end{array}$$