花点时间研究BLS，BBS，BBS+的算法。

数学基础

0 群

一个群（group），可以理解为一个集合 $G$ 搭配一个运算“$\ast$”（比如加法、乘法），需要满足四条规则：

1. 封闭性：任取 $a,b \in G$，计算 $a\ast b$ 仍然在 $G$ 里。
2. 结合律：$(a\ast b)\ast c = a\ast (b\ast c)$。
3. 单位元：存在一个特殊元素 $e \in G$，使得对任意 $a \in G$，有 $a\ast e = e\ast a = a$。
4. 逆元：对任意 $a \in G$，存在一个 $a^{-1}$，使得 $a\ast a^{-1} = a^{-1}\ast a = e$。

1 循环群

一个群 $G$ 称为循环群，如果存在一个元素 $g \in G$，使得群中每一个元素都可以写成 $g$ 的幂次：

$$G = \{ g^0, g^1, g^2, \dots, g^{n-1} \}$$

其中 $n$ 是群的阶（即元素个数），并且有 $g^n = e$（回到单位元）。

这个特殊的元素 $g$，叫做生成元（generator）。

例子：模 7 加法群

集合：$\{0,1,2,3,4,5,6\}$，运算是“模 7 加法”。

• 生成元可以是 1，因为 $$0, 1, (1+1)\bmod 7=2, (1+1+1)\bmod 7=3, \dots, 6$$ 就把整个集合生成了。
  所以 $\mathbb{Z}_7$ 是一个循环群。

“设 $G=\langle g\rangle$ 是阶为 $n$ 的循环群”：

• $G$：一个群；
• $\langle g\rangle$：表示由元素 $g$ 生成的群（即所有 $g^k$ 的集合）；
• “阶为 $n$”：群里总共有 $n$ 个不同的元素；
• 总结：$G$ 是一个循环群，它的所有元素都能写成 $g^k$ 的形式，且一共 $n$ 个。

1.1 有限域乘法群 $\mathbb{F}_p^\*$

• 设 $p$ 是一个素数；

• $\mathbb{F}_p = \{0,1,2,\dots,p-1\}$，运算是模 $p$ 加法和模 $p$ 乘法；

• $\mathbb{F}_p$ 称为有限域，因为它是一个有限的数集，且加减乘除（除零外）都有意义。

• 考虑非零元素：$\mathbb{F}_p^\* = \{1,2,\dots,p-1\}$，在模 $p$ 乘法下形成一个群；

• 群的阶是 $p-1$（因为零被排除）。

• 重要事实：$\mathbb{F}_p^\*$ 是一个循环群。

  • 意味着存在一个生成元 $g$，使得 $$\mathbb{F}_p^\* = \{ g^1, g^2, \dots, g^{p-1} \} \pmod p$$

取 $p=7$：$\mathbb{F}_7^\* = \{1,2,3,4,5,6\}$。

• 生成元 $g=3$：

  $$3^1=3,\; 3^2=2,\; 3^3=6,\; 3^4=4,\; 3^5=5,\; 3^6=1 \pmod{7}$$

• 所有元素都能生成，所以 3 是一个原根（primitive root）。

1.2 椭圆曲线群

椭圆曲线方程

• 在有限域 $\mathbb{F}_p$ 上定义曲线：

  $$E: y^2 \equiv x^3 + ax + b \pmod p$$

  其中参数 $a,b \in \mathbb{F}_p$，且满足判别式 $4a^3 + 27b^2 \not\equiv 0 \pmod p$，保证曲线“非奇异”。

• 曲线上的点集合：

  $$E(\mathbb{F}_p) = \{ (x,y)\in \mathbb{F}_p^2 \mid y^2 \equiv x^3+ax+b \} \cup \{\mathcal{O}\}$$

  其中 $\mathcal{O}$ 是“无穷远点”，充当群的单位元。

群运算（点加法）

• 定义了一个“点加法”运算 $\oplus$，满足群的四条性质。
• 直观几何解释（在实数域里）：
  • 过点 $P,Q$ 作直线，交椭圆曲线于第三点 $R$，再取其对称点 $-R$，定义为 $P+Q$。
• 在有限域上，这个过程转化为代数公式（斜率、模逆元等）。

2 离散对数问题（DLP）

2.1 定义

在素数阶循环群 $G=\langle g\rangle$ 上：

• 离散对数问题（DLP）：给定 $g, y=g^x$，求 $x$。

2.2 为什么难解？

没有闭式公式
在实数域里，$\log$ 是指数函数的反函数；但在模运算下（有限域/椭圆曲线），不存在类似的解析反函数。

指数运算像“乱洗牌”
当模数 $p$ 很大时，序列 $g^1,g^2,\dots$ 在 $\mathbb{F}_p^\*$ 看起来几乎是随机均匀分布的。已知一个值 $y$，几乎没有比逐一尝试更快的方法。

暴力搜索代价巨大
群阶若为 $n$，最笨的办法是试 $g^1,g^2,\dots,g^n$，复杂度 $O(n)$。如果 $n$ 大约是 $2^{256}$，即便用超级计算机也完全不可能。

通用攻击（不依赖群结构）

• Baby-Step Giant-Step (BSGS)：时间与空间都是 $O(\sqrt{n})$。
• Pollard ρ：时间 $O(\sqrt{n})$，空间极小 → 实际攻击基线。

特殊攻击（利用群结构）

• 有限域 $\mathbb{F}_p^\*$：有 次指数算法（Index Calculus / Number Field Sieve for DLP）。
  • 复杂度约 $\exp((\log p)^{1/3}(\log\log p)^{2/3})$，比 $\sqrt{p}$ 快得多。
  • 👉 因此在有限域上必须用很大的 $p$（如 3072 位）才能达到 128-bit 安全。
• 椭圆曲线群 ECDLP：目前没有次指数算法，最好的还是 $O(\sqrt{n})$（Pollard ρ）。
  • 👉 因此 256 位阶的曲线群就能提供 ~128-bit 安全，比有限域高效很多。

3 双线性群（bilinear group）

一个 双线性群系统 通常由三部分组成：

$$(G_1, G_2, G_T, e)$$

• $G_1, G_2, G_T$：都是阶为大素数 $p$ 的循环群；
• $g_1 \in G_1, g_2 \in G_2$：生成元；
• $e: G_1 \times G_2 \to G_T$：一个双线性映射（bilinear map，也叫“配对”）。

e 必须满足以下三个条件：

1. 双线性（bilinearity）
   对所有 $u\in G_1, v\in G_2, a,b\in \mathbb{Z}_p$，有

   $$e(u^a, v^b) = e(u,v)^{ab}$$

   👉 这条性质最重要：指数“乘”在映射里变成了“指数积”。

2. 非退化性（non-degeneracy）

   $$e(g_1, g_2) \neq 1$$

   否则映射就没信息量。

3. 有效可计算（computability）
   给定 $u\in G_1, v\in G_2$，能在多项式时间内算出 $e(u,v)$。

可以根据定义推导出 $G_1 \rightarrow G_T$ 和 $G_2 \rightarrow G_T$ 是群同态的。

群同态

设有两个群：

• 群 $G$，运算写作 $\cdot$，单位元记作 $e_G$。
• 群 $H$，运算写作 $*$，单位元记作 $e_H$。

一个函数 $f: G \to H$ 如果满足：

$$f(a \cdot b) = f(a) * f(b),\quad \forall a,b \in G,$$

就叫做 群同态。

直观理解，可以把群同态理解成一个“保持结构的变换”：

• 在原群里做运算，再映射；
• 和先映射，再在目标群里运算，结果一样。

推导

在双线性群中有配对映射

$$e: G_1 \times G_2 \to G_T.$$

固定第二个参数 $v\in G_2$，得到一个函数：

$$f_v: G_1 \to G_T,\quad f_v(u)=e(u,v).$$

要验证它是群同态：

$$\begin{align} f_v(u_1 \cdot u_2) &= e(u_1\cdot u_2, v) \\ &= e(g_1^a \cdot g_1^b, v) \\ &= e(g_1^{a+b}, v) \\ &= e(g_1, v)^{a+b} \\ &= e(g_1, v)^ae(g_1, v)^b \\ &= e(g_1^a, v)e(g_1^b,v)\\ &= e(u_1,v)\cdot e(u_2,v) = f_v(u_1)\cdot f_v(u_2). \end{align}$$

4 强 Diffie–Hellman 假设（q-SDH）

4.1 普通 Diffie–Hellman 假设

• 计算型 Diffie–Hellman（CDH）：给定 $(g, g^a, g^b)$，计算 $g^{ab}$。
• 判定型 Diffie–Hellman（DDH）：给定 $(g, g^a, g^b, g^c)$，判断 $c\stackrel{?}=ab$。

这些假设都基于离散对数问题的难解性。

无法通过 $y = g^x$ 推导出 $x = log_gy$ 。没有多项式时间内的对数运算。

4.2 强 Diffie–Hellman (q-SDH) 假设的定义

SDH 假设是在 双线性群（bilinear group） 上定义的，常用于群签名、短签名等方案。

• 设 $G$ 是一个阶为质数 $p$ 的循环群，生成元为 $g$。

• 给定一个秘密数 $x \in \mathbb{Z}_p^*$，公开 $(g, g^x, g^{x^2}, \dots, g^{x^q})$。

• 问题：在不知道 $x$ 的情况下，计算任意形式为

  $$(c, g^{\frac{1}{x+c}})$$

  的对，其中 $c \in \mathbb{Z}_p$ 自由选择。

q-SDH 假设：认为在公开 $(g, g^x, g^{x^2}, \dots, g^{x^q})$ 的条件下，任何多项式时间的算法几乎不可能输出一个新的合法对 $(c, g^{1/(x+c)})$。

BLS

1 直觉

选择大素数 $p$ 的三个循环群：$G_1, G_2, G_T$，阶均为 $p$。

生成元：$g_1\in G_1$，$g_2\in G_2$。

配对：$e: G_1\times G_2\to G_T$，双线性、非退化、可计算。

哈希到曲线：$H:\{0,1\}^\*\to G_1$（或到 $G_2$），把消息映射到群点（需用正规 hash-to-curve 方案）。

假设签名在 $G_1$、公钥在 $G_2$；

BLS 的核心是利用双线性配对把“指数上的乘法”显式化：

若 $e$ 是配对，满足 $e(g^a, h^b)=e(g,h)^{ab}$。

令签名 $\sigma=H(m)^{x}$（在某个群里），公钥 $pk=g^{x}$（在另一个群里），则验证：

$$e(\sigma, g) \stackrel{?}{=} e(H(m), pk)$$

因为左边 $=e(H(m)^x,g)=e(H(m),g)^x$，右边 $=e(H(m),g^x)$，两边相等说明确由同一私钥 $x$ 产生。

2 流程

• 密钥生成

  选私钥 x \xleftarrow{\}\mathbb{Z}_p^*$。

  公钥 $pk=g_2^{x}$（若签名在 $G_1$）。

• 签名（消息 $m$）

  1. $P \leftarrow H(m)\in G_1$。将消息哈希到曲线。
  2. $\sigma \leftarrow P^{x}\in G_1$。

• 检查

  $$e(\sigma, g_2) = e(H(m)^x, g_2) = e(H(m), g_2^x) = e(H(m), pk)$$

  检查方拿到签名 $\sigma$ 和消息$m$ ，已知 $g_2$ 和 $pk$ ，即可验证签名是否正确。

3 聚合签名

设定与符号

• 配对群：$(G_1,G_2,G_T,e)$，阶为素数 $p$，生成元 $g_1\in G_1, g_2\in G_2$。
• 哈希到曲线：$H:\{0,1\}^\*\to G_1$（也可反过来放到 $G_2$，下同）。
• 第 $i$ 个签名者私钥 $x_i\in\mathbb{Z}_p^\*$，公钥 $pk_i=g_2^{x_i}$。
• 对消息 $m$ 的 BLS 签名：$\sigma=H(m)^{x}\in G_1$。

输入

一批三元组 $(pk_i, m_i, \sigma_i)$，其中

$$\sigma_i = H(m_i)^{x_i}\in G_1$$

聚合

$$\boxed{\;\sigma_{\text{agg}}=\prod_{i=1}^n \sigma_i\;}\quad\in G_1.$$

这就是把各签名（群元素）相乘（椭圆曲线是“点加/标量乘”的对应群运算；在 $G_1$ 里用群运算累乘即可）。

验证

$$\begin{aligned} e(\sigma_{\text{agg}}, g_2) &=e\!\Big(\prod_i H(m_i)^{x_i},\, g_2\Big) =\prod_i e\!\left(H(m_i)^{x_i}, g_2\right)\\ &=\prod_i e\!\left(H(m_i), g_2\right)^{x_i} =\prod_i e\!\left(H(m_i), g_2^{x_i}\right) =\prod_i e\!\left(H(m_i), pk_i\right). \end{aligned}$$

4 为什么聚合签名验证更快

具体公式推导没有看懂，总之可以分成两种运算，其中可合并ML后运算FE。

对单个配对 $e(P,Q)$ 来说：

1. Miller loop (ML)：算出 $f_{r,Q}(P) \in \mathbb{F}_{p^k}^\*$，但它还没在目标子群 $G_T$；

2. Final exp (FE)：把结果提到指数 $(p^k-1)/r$，得到

   $$e(P,Q) = f_{r,Q}(P)^{(p^k-1)/r}\in G_T.$$

所以配对的“真正结果” = ML 输出 + 一次 FE。

对于逐个验证：

$$e(\sigma_i, g_2) = e(H(m_i), pk_i)$$

需要做 2n 次 ML + 2n 次 FE。

而聚合签名：

$$e(\sigma_{agg},g_2) = \prod_ie(H(m_i), pk_i)$$

左侧做 1次ML + 1次FE，右侧可合并ML后做FE，即 n 次 ML + 1次 FE。
总共 n+1 次ML + 2次 FE。

BBS

1 作用

BBS（Boneh–Boyen–Shacham，2004）主要提出的是一种短群签名方案。它的作用可以用三句话概括：

1. 匿名签名

   群签名的核心功能：群里任何一个成员都能代表整个群签名，但外部验证者只能知道“这是群里某个人签的”，而不知道具体是谁。

2. 可追踪性

   系统里有一个“管理者/开盖者”，在必要的时候（例如发生违法、作恶行为），可以打开匿名性，查出具体是谁签的。

3. 高效与简洁

   在 BBS04 方案里，签名长度非常短（≈ 一个常规 RSA 签名大小），且验证效率高，满足当时一些实际应用（如 可信计算 attestation、车联网安全广播）对“匿名+短消息签名”的需求。

2 流程

设定与符号

1. 选定双线性群：

   • 两个椭圆曲线群 $G_1, G_2$，阶为素数 $p$；
   • 生成元 $g_1 \in G_1, g_2 \in G_2$；
   • 双线性配对 $e: G_1 \times G_2 \to G_T$。

2. 管理者生成秘密：

   • 随机挑 $\gamma \in \mathbb{Z}_p$；
   • 公钥元素 $w = g_2^\gamma \in G_2$。
   • $w$ 在追踪时会用到。

3. 每个群成员的私钥：

   • 群成员 $i$ 得到一个私钥

     $$A_i = g_1^{1/(\gamma + x_i)} \in G_1,$$

     其中 $x_i \in \mathbb{Z}_p$ 是该成员的身份值。

   • 注意：只有管理者能生成这样的 $A_i$，因为需要知道 $\gamma$。

这样，每个成员的身份 = $(A_i, x_i)$。

签名

群成员 $i$ 要签消息 $M$：

1. 先把消息映射到 $h = H(M) \in G_1$。
   （这里 $H$ 是 hash-to-curve）

2. 成员用私钥 $(A_i, x_i)$ 生成签名：

   • 随机选 $r \in \mathbb{Z}_p$；

   • 计算：

     $$T_1 = A_i \cdot h^r \in G_1,$$ $$T_2 = g_1^r \in G_1,$$ $$T_3 = w^{r+x_i} \in G_2.$$

   • 再加一个 零知识证明 $\pi$：证明“在不透露 $A_i, x_i$ 的前提下，确实有 $A_i, x_i$ 是有效成员凭证”。

3. 签名整体是：

   $$\sigma = (T_1, T_2, T_3, \pi).$$

验证

验证者拿到 $\sigma=(T_1,T_2,T_3,\pi)$，做：

1. 验证零知识证明 $\pi$，保证签名者确实持有有效的成员凭证；

2. 检查配对等式是否成立，例如：

   $$e(T_1, g_2) \stackrel{?}{=} e(h, T_3)\cdot e(T_2, w).$$

这个等式成立，当且仅当签名确实来自某个有效成员。

因为整个过程中没有暴露 $x_i$，外部无法知道具体是谁签的 → 匿名性。

追踪

如果需要“开盖”，群管理者可以用秘密 $\gamma$ 来解出签名者：

• 管理者有 $\gamma$，知道 $T_3 = w^{r+x_i} = g_2^{\gamma(r+x_i)}$。
• 结合 $T_2=g_1^r$，可以还原出与成员身份绑定的元素，从而确定是哪个 $x_i$。

这样就能追踪出签名者身份。

其中的“零知识证明”

签名后还有一个零知识证明，证明 T1 T2 T3 是有效的。

这里用到的就是之前提过的非交互式零知识证明，

承诺

• 签名者挑一些随机数 $s_1,s_2$，
• 计算若干承诺值（类似“我先放几个锁住的盒子”），记为 $C_1,C_2,\dots$，
• 这些是群元素（点或指数），依赖 $s_1,s_2$，但不依赖秘密 $(A_i,x_i)$。

挑战

• 在交互式协议里，验证者随机发一个挑战数 $c \in \mathbb{Z}_p$；

• 在非交互式协议里（实际 BBS 用的），挑战由哈希函数生成：

  $$c = H(C_1 \| C_2 \| \cdots \| M).$$

响应

• 签名者用秘密 $(A_i,x_i)$ 和随机数 $s_1,s_2$，结合挑战 $c$，计算响应值 $z_1,z_2,\dots$。
• 这些响应能让验证者确认等式成立，但不会暴露 $(A_i,x_i)$。

验证

验证者收到：$(C_1,\dots,c,z_1,z_2,\dots)$。
他会检查一组等式，比如：

$$\text{Check: } C_1 \cdot T_1^c \stackrel{?}{=} g_1^{z_1}, \quad C_2 \cdot T_2^c \stackrel{?}{=} w^{z_2}, \quad \dots$$

这些等式保证：

• 如果签名者没有正确的 $(A_i,x_i)$，就几乎不可能通过验证；
• 如果签名者有合法参数，那么响应一定能满足这些验证等式；
• 验证者无法从 $(C,z)$ 推出 $(A_i,x_i)$，因为它们被随机化隐藏了。

BBS+

1 作用

不是BBS的增强版！

BBS+更多表示在结构上参考了BBS，但是两者作用完全不同。

BBS+不具备群签名、可追踪等功能。

他的作用更加直接：多消息签名+选择性披露。

• 可以对一组消息 $(m_1,\dots,m_k)$ 签名；
• 签名长度固定（3 个群元素），和消息数无关；
• 支持 选择性披露：持有人能证明“我有一个覆盖所有消息的签名”，但只展示其中一部分；

2 流程

设定与符号

• 选双线性配对 $(G_1,G_2,G_T,e)$，阶为素数 $p$，生成元 $g_1\in G_1,\; g_2\in G_2$
• 取额外基元：$u,h_1,\dots,h_\ell \in G_1$（用于“多消息”与盲化）
• 签名者密钥：随机 $x\in\mathbb{Z}_p$；公钥：$W=g_2^x\in G_2$
• Hash-to-curve：$H:\{0,1\}^\*\to G_1$（仅当需要把任意消息先映到群；BBS+常直接把整数消息当指数）

参数：$\mathsf{pp}=(G_1,G_2,G_T,e,p; g_1,g_2,u,h_1,\dots,h_\ell)$。
密钥：$\mathsf{sk}=x,\; \mathsf{pk}=W=g_2^x$。

签名

要签 $\ell$ 条消息 $m_1,\dots,m_\ell\in \mathbb{Z}_p$。

1. 采样随机 $e,s \leftarrow \mathbb{Z}_p$

2. 计算“消息基底”：

   $$B \;=\; g_1 \cdot u^{s} \cdot \prod_{i=1}^{\ell} h_i^{m_i} \;\in G_1$$

   补充说明 $h_i^{m_i}$ 的运算：要先把 $m_i$ hash to scalar，映射到整数域。

3. 计算

   $$A \;=\; B^{\,1/(x+e)} \;\in G_1 \quad\big(\text{即 } A^{x+e}=B\big)$$

4. 输出签名：$\sigma=(A,e,s)$

直觉：$(A,e,s)$ 使得 $e(A,\,W\cdot g_2^{e})=e(B,\,g_2)$，从而把“消息向量”压进一条等式里；签名长度固定 3 个元素，与消息条数无关。

验证

给定 $\sigma=(A,e,s)$、公钥 $W$ 与消息 $m_1,\dots,m_\ell$：

1. 复算

   $$B \;=\; g_1 \cdot u^{s} \cdot \prod_{i=1}^{\ell} h_i^{m_i} \in G_1$$

2. 检查配对等式

   $$\boxed{\,e\!\left(A,\; W\cdot g_2^{e}\right)\;\stackrel{?}{=}\; e\!\left(B,\; g_2\right)\,}$$

若成立则验签通过。

选择性披露

目标：已持有 BBS+ 签名 $\sigma=(A,e,s)$ 覆盖的消息向量 $(m_1,\dots,m_\ell)$，现在只公开其中一部分索引集合 $R$ 的消息 $\{m_i:i\in R\}$，而把其余 $H=\{1,\dots,\ell\}\setminus R$ 隐藏；同时向验证者零知识证明：确实存在隐藏消息与签名使得原验证等式成立。

要证明的语句（正式 PoK 声明）

证明者要给出一个非交互零知识证明，证明如下命题成立：

$$\mathsf{PoK}\left\{\,A,e,s,\{m_i\}_{i\in H}\;:\; \begin{array}{l} e\!\big(A,\; W\cdot g_2^{e}\big)=e\!\big(g_1 \cdot u^{s}\cdot \prod_{i=1}^{\ell} h_i^{m_i},\; g_2\big)\\[2pt] \text{且对所有 } i\in R,\; m_i \text{ 等于已公开的值 } m_i^\* \end{array} \right\}.$$

这句话的含义：验证者只拿到 $\{m_i^\*: i\in R\}$ 与一个 NIZK 证明；验证者被说服：确实存在某些隐藏消息 $\{m_i: i\in H\}$ 和 $(A,e,s)$ 使上式成立，但看不见这些秘密的具体数值。

证明与验证的结构（Σ-协议 + Fiat–Shamir，示意）

• 承诺（Prover）：
  选择盲化随机数（对 $e,s$ 和每个隐藏 $m_i$ 都选一份），基于等式右侧的乘法线性与配对的双线性，构造一组承诺值（群元素），把“隐藏消息的线性组合”锁进去；
• 挑战：
  用 Fiat–Shamir：$c=H(\text{承诺}\,\|\,\text{上下文/域分离}\,\|\,\text{已公开消息})$；
• 响应（Prover）：
  计算响应向量 $(z_e,z_s,\{z_i\}_{i\in H})$，它们是“盲化量 + 挑战 × 真值”的线性组合；
• 验证（Verifier）：
  依据响应
• 并检查一组等式是否成立（等价于把“挑战”分离开后，回到原始配对关系的加法/乘法同态形式）。若全部成立，则验明：上面的 PoK 语句为真。

关键点：

• 公开消息集合 $R$ 直接放进验证等式；
• 隐藏消息集合 $H$ 仅通过承诺与响应“出现”为指数上的线性项，验证者无法反推出具体数值；
• 整个证明能与不同会话不可链接（因有新盲化随机数）；
• 安全性基于配对群里的 CDH/SDH 类假设与随机预言机（Fiat–Shamir）模型。