BBS 签名

Revisiting BBS Signatures

BBS 基本流程

1. 系统参数生成（BBS.Setup）

假设我们有 $\mathcal{l}$ 条消息：

$$\begin{array}{rl}{G}_1& \stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{G}}_1\\ H_1,\dots ,H_{\mathcal{l}}& \stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{G}}_1\\ G_2& \stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{G}}_2^{\ast }\\ \mathsf{par}& \leftarrow ({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_T,e,G_1,H_1,G_2)\end{array}$$

输出公共参数 $\mathsf{par}$。这里的 $\overrightarrow{H}$ 可以是任意点。

2. 密钥生成（BBS.KG）

输入 $\mathsf{par}$，执行：

$$x\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p,X\leftarrow x{G}_2$$

• 秘密密钥：$\mathsf{sk}=x$
• 公钥：$\mathsf{pk}=X$

返回 $(\mathsf{sk},\mathsf{vk})$。

3. 签名生成（BBS.Sign）

输入 $\mathsf{sk}=x$ 和消息向量 $\mathbf{m}=(m_1,\dots ,m_l)\in {\mathbb{Z}}_p^{\ell }$，执行：

1. 计算消息承诺：$$C\leftarrow G_1+\sum _{i=1}^{\mathcal{l}}{m}_i\cdot H_i\in {\mathbb{G}}_1$$
2. 随机选择标量 $e$：$$e\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$$
3. 计算签名：$$A\leftarrow \frac{1}{x+e}C\in {\mathbb{G}}_1$$

输出签名 $\sigma =(A,e)$。
签名长度：1 个 ${\mathbb{G}}_1$ 点 + 1 个 ${\mathbb{Z}}_p$ 标量（比 BBS+ 少一个标量 $s$）。

4. 签名验证（BBS.Ver）

输入公钥 $X$、消息 $\mathbf{m}$、签名 $(A,e)$，执行：

1. 重新计算承诺：$$C\leftarrow G_1+\sum _{i=1}^{\ell }{m}_i\cdot H_i$$
2. 检查配对等式：$$e(A,X+e{G}_2)\stackrel{?}{=}e(C,G_2)$$

若等式成立（且 $A\ne \mathcal{O}$），则验证通过；否则拒绝。

5. 正确性

诚实生成的签名满足 $(x+e)A=C$。
对两边同时与 $G_2$ 配对：

$$e((x+e)A,G_2)=e(C,G_2)$$

由双线性得到：

$$e(A,(x+e)G_2)=e(C,G_2)⟺e(A,X+e\cdot G_2)=e(C,G_2)$$

验证等式恒成立。

零知识披露

BBS 的 零知识 Σ-协议（Sigma-Protocol
（用于证明知道有效 BBS 消息-签名对，同时隐藏签名 (A, e) 和部分消息分量）

公共输入（Verifier 已知）：

• BBS 参数：$G_1,H_i[1..\ell ],G_2,X$
• 设 $J=$ 已知分量下标，$I=$ 隐藏分量下标（$I\cup J=[\ell ]$）
• 部分披露的消息向量 ${\mathbf{m}}_i\in J$

私密输入（Prover 知道）：

• 完整消息 $\mathbf{m}$
• 有效签名 $(A,e)$，$A\ne \mathcal{O}$

目标：Prover 向 Verifier 证明存在 $(\mathbf{m},A,e)$ 使得 BBS.Ver 接受，同时隐藏 $A,e$ 以及 $\mathbf{m}$ 中标有 $\ast$ 的分量。

1. 完整披露, 所有消息已知

Prover（P1）：

1. 随机 $r\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p^{\ast }$

2. 计算随机化签名点：

   $$\bar{A}\leftarrow r\cdot A$$

3. 计算辅助点：

   $$C\leftarrow G_1+\sum _{i=1}^{\ell }{m}_i\cdot H_i$$$$\bar{B}\leftarrow r\cdot C-r\cdot e\cdot A$$

4. 随机 $\alpha ,\beta \stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$

5. 计算同态承诺：

   $$U\leftarrow \alpha \cdot C+\beta \cdot \bar{A}$$

发送 $(\bar{A},\bar{B},U)$ 给 Verifier。

Verifier 发送挑战：

$$c\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$$

Prover（P2）响应：

$$s\leftarrow \alpha +r\cdot c,t\leftarrow \beta -e\cdot c$$

发送 $(s,t)$

Verifier 检查（PoK.V）：

1. 配对检查（确认随机化签名合法）：$$e(\bar{A},X)\stackrel{?}{=}e(\bar{B},G_2)$$
2. 同态检查（证明 $\bar{B}$ 的表示）：$$U+c\cdot \bar{B}\stackrel{?}{=}s\cdot C+t\cdot \bar{A}$$

正确性

1. 配对检查：

   $$\begin{array}{rl}lhs& =\\ & =e(r\cdot A,X)\\ & =e(A,rx{G}_2)\\ rhs& =\\ & =e(r\cdot C-r\cdot e\cdot A,G_2)\\ & =e(C-\frac{eC}{x+e},r{G}_2)\\ & =e(\frac{xC}{x+e},r{G}_2)\\ & =e(\frac{C}{x+e},xr{G}_2)\\ & =e(A,rx{G}_2)\\ & =lhs\end{array}$$

2. 同态检查：

$$\begin{array}{rl}lhs& =U+c\cdot \bar{B}\\ & =\alpha C+\beta \bar{A}+c(rC-reA)\\ & =(\alpha +rc)C+(\beta -re)\bar{A}\\ & =sC+t\bar{A}\\ & =rhs\end{array}$$

2. 部分披露（Partial Disclosure，隐藏部分消息）

Prover（P1）：

1. 随机 $r\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p^{\ast }$
2. 计算 $\bar{A}\leftarrow r\cdot A$
3. 计算公开部分承诺（Verifier 也能算）：$$C_J\leftarrow G_1+\sum _{j\in J}{m}_j\cdot H_j$$
4. 计算隐藏部分的辅助点：$$\bar{B}\leftarrow r\cdot C-r\cdot e\cdot A$$
5. 随机 $\alpha ,\beta \stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$，并对每个隐藏分量 $i\in I$ 随机 ${\delta }_i\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$
6. 计算同态承诺（现在包含隐藏分量）：$$U\leftarrow \alpha C_J+\beta \bar{A}+\sum _{i\in I}{\delta }_i\cdot H_i$$

发送 $(\bar{A},\bar{B},U)$ 给 Verifier。

Verifier 发送挑战 $c\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$

Prover（P2）响应：

$$s\leftarrow \alpha +r\cdot c,t\leftarrow \beta -e\cdot c$$

对每个隐藏分量：

$$u_i\leftarrow {\delta }_i+r\cdot m_i\cdot c(\mathrm{\forall }i\in I)$$

发送 $(s,t,\{u_i{\}}_{i\in I})$

Verifier 检查（PoK.V）：

1. 配对检查（同上）：$$e(\bar{A},X)\stackrel{?}{=}e(\bar{B},G_2)$$
2. 同态检查（现在使用公开部分 + 隐藏响应）：$$U+c\cdot \bar{B}\stackrel{?}{=}s\cdot C_J+t\cdot \bar{A}+\sum _{i\in I}{u}_i\cdot H_i$$

FS 变换后的非交互证明

证明生成（Prover）

输入：公共参数 $\mathsf{par}$、公钥 $X$、部分披露消息 ${\mathbf{m}}_j$、私密完整消息 $\mathbf{m}$、私密签名 $(A,e)$ 。$J$ 为公开分量下标集合，$I$ 为隐藏分量下标集合。

1. 随机选择 $r\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p^{\ast }$

2. 计算随机化签名点：

   $$\bar{A}\leftarrow r\cdot A$$

3. 计算公开部分承诺：

   $$C_J\leftarrow G_1+\sum _{j\in J}{m}_j\cdot H_j$$

4. 计算辅助点（隐藏签名信息）：

   $$\bar{B}\leftarrow r\cdot C+-r\cdot e\cdot A\text{（其中 }C=G_1+\sum _{i=1}^{\ell }{m}_1\cdot H_i\text{）}$$

5. 随机选择：
   $\alpha ,\beta \stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$
   对每个隐藏分量 $i\in I$：${\delta }_i\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_p$

6. 计算同态承诺：

   $$U\leftarrow \alpha C_J+\beta \bar{A}+\sum _{i\in I}{\delta }_i\cdot H_i$$

7. 计算Fiat-Shamir 挑战：
   计算

   $$c\leftarrow H(\mathsf{ctx}\Vert X\Vert {\mathbf{m}}_j\Vert \bar{A}\Vert \bar{B}\Vert U)$$

   （$\mathsf{ctx}$ 为领域分隔字符串，例如 "BBS_PoK_1" 或具体应用定义的上下文，防止重放/混淆攻击）

8. 计算响应：

   $$s\leftarrow \alpha +r\cdot c,t\leftarrow \beta -e\cdot c$$

   对每个隐藏分量 $i\in I$：

   $$u_i\leftarrow {\delta }_i+r\cdot m_i\cdot c$$

输出证明 $\pi$:
[ \pi = \bigl( \overline{A},\ \overline{B},\ U,\ s,\ t,\ {u_i}_{i \in I} \bigr) ]
（共 2 个 ${\mathbb{G}}_1$ 点 + (k + 3) 个 ${\mathbb{Z}}_p$ 标量，$k=|I|$）

验证（Verifier）

输入：$\mathsf{par}$、$X$、${\mathbf{m}}_j$、证明 $\pi$。

1. 重新计算公开部分承诺：

   $$C_J\leftarrow G_1+\sum _{j\in J}{m}_j\cdot H_j$$

2. 重新计算挑战（与 Prover 完全相同）：

   $$c^{\prime }\leftarrow H(\mathsf{ctx}\Vert X\Vert {\mathbf{m}}_j\Vert \bar{A}\Vert \bar{B}\Vert U)$$

3. 检查两个等式（若任意一个失败则拒绝）：
   配对检查（确认随机化签名合法）：

   $$e(\bar{A},X_2)\stackrel{?}{=}e(\bar{B},g_2)$$

   同态检查（确认 $\bar{B}$ 的表示正确）：

   $$U+c^{\prime }\cdot \bar{B}\stackrel{?}{=}s\cdot C_J+t\cdot \bar{A}+\sum _{i\in I}{u}_i\cdot H_i$$

若两个检查都通过，则接受证明（证明者知道有效 BBS 签名且公开消息与 ${\mathbf{m}}_j$ 一致）。