BBS 签名

BBS 基本流程

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

假设我们有 $l$ 条消息：

\begin{aligned} G_{1} & \overset{$}{\leftarrow} G_{1} \\ H_{1}, \dots, H_{l} & \overset{$}{\leftarrow} G_{1} \\ G_{2} & \overset{$}{\leftarrow} G_{2}^{*} \\ par & \leftarrow (G_{1}, G_{2}, G_{T}, e, G_{1}, H_{1}, G_{2}) \end{aligned}

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

2. 密钥生成（BBS.KG）

输入 $par$ ，执行：

x \overset{$}{\leftarrow} Z_{p}, X \leftarrow x G_{2}

秘密密钥： $sk = x$
公钥： $pk = X$

返回 $(sk, vk)$ 。

3. 签名生成（BBS.Sign）

输入 $sk = x$ 和消息向量 $m = (m_{1}, \dots, m_{l}) \in Z_{p}^{ℓ}$ ，执行：

计算消息承诺： $C \leftarrow G_{1} + \sum_{i = 1}^{l} m_{i} \cdot H_{i} \in G_{1}$
随机选择标量 $e$ ： $e \overset{$}{\leftarrow} Z_{p}$
计算签名： $A \leftarrow \frac{1}{x + e} C \in G_{1}$

输出签名 $σ = (A, e)$ 。
签名长度：1 个 $G_{1}$ 点 + 1 个 $Z_{p}$ 标量（比 BBS+ 少一个标量 $s$ ）。

4. 签名验证（BBS.Ver）

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

重新计算承诺： $C \leftarrow G_{1} + \sum_{i = 1}^{ℓ} m_{i} \cdot H_{i}$
检查配对等式： $e (A, X + e G_{2}) \overset{?}{=} e (C, G_{2})$

若等式成立（且 $A \neq 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})

验证等式恒成立。

6. 存在的问题

对于签名 $σ = (A = \frac{C}{x + e}, e)$ 来说，攻击者容易伪造 $σ^{'} = (A^{2} = \frac{C^{2}}{x + e}, e)$ 也是一个对承诺 $C^{2}$ 的有效签名。

7. 盲签名构造

非常简单，只需在发送承诺 $C$ 时构造一个随机值变换为 $r C$ 即可，在接受到签名 $A = \frac{r C}{x + e}$ 时能很容易消去。

零知识披露

BBS 的 Σ-协议

公共输入（Verifier 已知）：

BBS 参数： $G_{1}, H_{i} [1. . ℓ], G_{2}, X$
设 $J =$ 已知分量下标， $I =$ 隐藏分量下标（ $I \cup J = [ℓ]$ ）
部分披露的消息向量 $m_{i} \in J$

私密输入（Prover 知道）：

完整消息 $m$
有效签名 $(A, e)$ ， $A \neq O$

目标：Prover 向 Verifier 证明存在 $(m, A, e)$ 使得 BBS.Ver 接受，同时隐藏 $A, e$ 以及 $m_{i \in I}$ 。

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

Mark: 同态承诺 -> [Proofs, Arguments, and Zero-Knowledge, 12.3]

Prover（P1）：

随机 $r \overset{$}{\leftarrow} Z_{p}^{*}$
计算随机化签名点：
$\overset{―}{A} \leftarrow r \cdot A$
计算辅助点：
$C \leftarrow G_{1} + \sum_{i = 1}^{ℓ} m_{i} \cdot H_{i}$ $\overset{―}{B} \leftarrow r \cdot C - r \cdot e \cdot A$
随机 $α, β \overset{$}{\leftarrow} Z_{p}$
计算同态承诺：
$U \leftarrow α \cdot C + β \cdot \overset{―}{A}$

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

Verifier 发送挑战：

c \overset{$}{\leftarrow} Z_{p}

Prover（P2）响应：

s \leftarrow α + r \cdot c, t \leftarrow β - e \cdot c

发送 $(s, t)$

FS变换：

Prover 计算

c = H a s h (ctx | | \bar{A} | | \bar{B} | | U)

发送 $(\bar{A}, \bar{B}, U, s, t)$

Verifier 检查（PoK.V）：

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

正确性

配对检查：
$\begin{aligned} l h s & = \\ = e (r \cdot A, X) \\ = e (A, r x G_{2}) \\ r h s & = \\ = e (r \cdot C - r \cdot e \cdot A, G_{2}) \\ = e (C - \frac{e C}{x + e}, r G_{2}) \\ = e (\frac{x C}{x + e}, r G_{2}) \\ = e (\frac{C}{x + e}, x r G_{2}) \\ = e (A, r x G_{2}) \\ = l h s \end{aligned}$
同态检查：

\begin{aligned} l h s & = U + c \cdot \overset{―}{B} \\ = α C + β \overset{―}{A} + c (r C - r e A) \\ = (α + r c) C + (β - r e) \overset{―}{A} \\ = s C + t \overset{―}{A} \\ = r h s \end{aligned}

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

Prover（P1）：

随机 $r \overset{$}{\leftarrow} Z_{p}^{*}$
计算 $\overset{―}{A} \leftarrow r \cdot A$
计算公开部分承诺：
$C_{J} \leftarrow G_{1} + \sum_{j \in J} m_{j} \cdot H_{j}$
计算隐藏部分的辅助点：
$\overset{―}{B} \leftarrow r \cdot C - r \cdot e \cdot A$
随机 $α, β \overset{$}{\leftarrow} Z_{p}$ ，并对每个隐藏分量 $i \in I$ 随机 $δ_{i} \overset{$}{\leftarrow} Z_{p}$
计算同态承诺（现在包含隐藏分量）：
$U \leftarrow α C_{J} + β \overset{―}{A} + \sum_{i \in I} δ_{i} \cdot H_{i}$

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

Verifier 发送挑战 $c \overset{$}{\leftarrow} Z_{p}$

Prover（P2）响应：

s \leftarrow α + r \cdot c, t \leftarrow β - e \cdot c

对每个隐藏分量：

u_{i} \leftarrow δ_{i} + r \cdot m_{i} \cdot c (\forall i \in I)

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

Verifier 检查（PoK.V）：

配对检查（同上）： $e (\overset{―}{A}, X) \overset{?}{=} e (\overset{―}{B}, G_{2})$
同态检查（现在使用公开部分 + 隐藏响应）： $U + c \cdot \overset{―}{B} \overset{?}{=} s \cdot C_{J} + t \cdot \overset{―}{A} + \sum_{i \in I} u_{i} \cdot H_{i}$

FS 变换后的非交互证明

证明生成（Prover）

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

随机选择 $r \overset{$}{\leftarrow} Z_{p}^{*}$
计算随机化签名点：
$\overset{―}{A} \leftarrow r \cdot A$
计算公开部分承诺：
$C_{J} \leftarrow G_{1} + \sum_{j \in J} m_{j} \cdot H_{j}$
计算辅助点（隐藏签名信息）：
$\overset{―}{B} \leftarrow r \cdot C - r \cdot e \cdot A （其中 C = G_{1} + \sum_{l = 1}^{ℓ} m_{l} \cdot H_{l} ）$
随机选择：
$α, β \overset{$}{\leftarrow} Z_{p}$
对每个隐藏分量 $i \in I$ ： $δ_{i} \overset{$}{\leftarrow} Z_{p}$
计算同态承诺：
$U \leftarrow α C_{J} + β \overset{―}{A} + \sum_{i \in I} δ_{i} \cdot H_{i}$
计算Fiat-Shamir 挑战：
计算
$c \leftarrow H (ctx ‖ m_{j} ‖ \overset{―}{A} ‖ \overset{―}{B} ‖ U)$
（ $ctx$ 为领域分隔字符串，例如 "BBS_PoK_1||ChainID" 或具体应用定义的上下文，防止重放/混淆攻击，例如在Dapp1生成的c用到了Dapp2中）
计算响应：
$s \leftarrow α + r \cdot c, t \leftarrow β - e \cdot c$
对每个隐藏分量 $i \in I$ ：
$u_{i} \leftarrow δ_{i} + r \cdot m_{i} \cdot c$

输出证明 $π$ :

π = (\overset{―}{A}, \overset{―}{B}, U, s, t, {u_{i}}_{i \in I})

（共 2 个 $G_{1}$ 点 + (k + 3) 个 $Z_{p}$ 标量， $k = | I |$ ）

验证（Verifier）

输入： $par$ 、 $X$ 、 $m_{j}$ 、证明 $π$ 。

重新计算公开部分承诺：
$C_{J} \leftarrow G_{1} + \sum_{j \in J} m_{j} \cdot H_{j}$
重新计算挑战（与 Prover 完全相同）：
$c^{'} \leftarrow H (ctx ‖ m_{j} ‖ \overset{―}{A} ‖ \overset{―}{B} ‖ U)$
检查两个等式（若任意一个失败则拒绝）：
配对检查（确认随机化签名合法）：
$e (\overset{―}{A}, X_{2}) \overset{?}{=} e (\overset{―}{B}, G_{2})$
同态检查（确认 $\overset{―}{B}$ 的表示正确）：
$U + c^{'} \cdot \overset{―}{B} \overset{?}{=} s \cdot C_{J} + t \cdot \overset{―}{A} + \sum_{i \in I} u_{i} \cdot H_{i}$

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

BBS 签名 ​

BBS 基本流程 ​

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

2. 密钥生成（BBS.KG） ​

3. 签名生成（BBS.Sign） ​

4. 签名验证（BBS.Ver） ​

5. 正确性 ​

6. 存在的问题 ​

7. 盲签名构造 ​

零知识披露 ​

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

2. 部分披露（Partial Disclosure，对于Verifier隐藏部分消息） ​

FS 变换后的非交互证明 ​

证明生成（Prover） ​

验证（Verifier） ​