群签名

一、群签名介绍

群签名是这样一个数字签名：在一个群签名的方案中，一个群体中的任意一个成员可以代表这个群体对消息进行签名，并且其他人可以使用群公钥对这个签名进行公开验证。在验证时，验证者只能验证签名是来自这个群组的，但是无法知道到底是群中的哪个成员对消息进行了签名。

在群签名中，存在一个群管理员，该管理员可以通过对签名进行操作得到签名者的真实身份。

1.1 群签名的形式化定义

一个群签名通常包含下面几个步骤：
创建：该算法用于生成群签名系统需要用的公共参数和群的公私钥对。
加入：一个用户想要生成群签名，首先需要加入这个群获得相应的群成员私钥，然后才能使用它生成合法的群签名。用户可通过该算法与群管理员交互式，从而获得群管理员颁发的群成员私钥。
签名：当群成员想要对一个消息签名时，他使用自己的群成员的私钥计算出相应的签名。
验证：任何验证者在拿到群成员的签名和群公钥后，可以判断签名的生成者是否是合法的群成员。
打开：群管理员可以使用群私钥对群签名去匿名化，得到某个群签名对应的签名人的真实身份。

1.2 群签名的性质

经过多年的发展，群签名已经形成了多种不同的构造方式和变种，不同方案可能具备不同的安全或功能特性。通常可以将群签名的性质分为"所有群签名方案必须满足的核心性质"；和 “部分方案在核心性质之外引入的扩展性质”。

一个签名必须具备以下两个最重要的性质，才能被称为群签名，这也是群签名被提出的初衷：

1. 用户匿名性：匿名性要求任何合法群成员在生成群签名后，外部验证者只能确认该签名确实由群体中的某个成员产生，而无法识别具体的签名者身份。这一性质保证了群签名在需要保护签名者身份的应用场景中具有重要价值，是群签名最核心的特征之一。
2. 条件隐私性：条件隐私性指群签名所提供的匿名性并非无条件，而是受到群管理员的控制。群管理员持有一把特殊的“打开密钥”，能够在必要时通过打开算法揭示某个群签名的实际签名者身份。由此，群签名实现了匿名性与可追责性的平衡：对外保持签名者的匿名，对内则保证在需要时能够追溯签名者的真实身份。【条件隐私性也叫可追踪性】

除了用户匿名性与条件隐私性这两个核心性质，不同的群签名方案还可能具备以下扩展性质：

除了群签名的核心性质（用户匿名性和条件隐私性）之外，不同的群签名方案可能还具备一些扩展性质。下面介绍三种常见的扩展性质及其一般实现思路。

1. 可撤销性： 可撤销性指群管理员可以撤销某些群成员的签名权限，使其在被撤销后无法继续生成有效的群签名。典型的实现思路包括：
   ① 更新群成员证书和群参数：群管理员在撤销成员后更新群参数，并更新合法群成员的群成员私钥。由于被撤销成员无法获得新的参数对应的群成员私钥，因此其后续签名将不再有效。
   ② 基于累加器的方法：利用密码学累加器对群成员身份进行高效的加入与删除操作。签名者在签署消息时，必须使用有效的成员证明；这样可以通过更新累加器和成员证明来撤销群成员。
   ③ 黑名单机制：群管理员可以将非法用户的 ID 加入黑名单，或者由验证者在本地维护一份撤销列表。在验证签名时，验证者需要首先检查签名者是否位于撤销列表中，若是则直接拒绝。值得注意的是，这一机制与群签名的匿名性并不矛盾。通过合理的密码学设计，验证者在执行撤销检查时，并不需要获知签名者的真实身份，仅需判断签名是否对应于已撤销的成员即可。

2. 动态性：动态性要求群签名系统支持成员的动态加入和退出，而无需重新初始化整个群。通常情况下，当有新成员加入时，群管理员为其颁发群私钥，并更新群状态信息。新成员可以立即生成有效签名，而不会影响现有成员。对于退出成员，可以结合撤销机制，将其标记为已撤销，使其签名不再被接受，而无需重新生成所有成员的密钥。

3. 前向匿名性（Forward Anonymity）
   前向匿名性要求，即便某个群成员的身份在未来被揭示，其历史签名仍然保持匿名，无法追溯到具体成员。一般的实现思路包括：
   ① 一次性密钥或随机化机制：每次签名时引入随机性或临时密钥，使签名不可链接。即使后来公开长期身份密钥，也无法将其与历史签名对应起来。
   ② 不可逆身份绑定：在签名过程中，身份信息以不可逆的方式嵌入证明中。即便群管理员打开部分签名，历史签名的匿名性依然能够得到保障。

二、群签名的构造

群签名的构造方式有很多，

2.1 基于RSA的群签名

RSA群签名—系统初始化：

1. 群管理员选择 RSA 公钥 $(n, e)$。
2. 群管理员选择生成元为 $g$ 的循环群 $G$，其中 $G$ 的阶为 $n$。
3. 选择一个 $a \in Z_n^*$，其中 $a$ 在 $n$ 的两个素数因子 $p, q$ 下均具有较大的乘法阶。
4. 选择密钥长度的上界 $\lambda$，以及常数 $\varepsilon > 1$。
5. 公共参数为：$\text{params} = \\{n, e, G, g, a, \lambda, \varepsilon\\}$

RSA群签名—成员加入：
假设 Alice 想要加入群组，她与群管理员（GM）的交互过程如下：

1. Alice 执行：
   选择私钥 $x$，并计算 $y = a^x \pmod{n}, \quad z = g^y$，其中 $z$ 作为群成员私钥。
   使用零知识证明 $\pi = \\{(y,a,n;x):y = a^x \pmod{n}\\}$ 证明自己知道 y 关于 a 的离散对数 $x$.
   将 $(y, z)$ 以及自己对 $z$ 的签名，以及零知识证明发送给群管理员。
2. GM 执行：
   验证 $y$ 和 $z$ 是否是循环群上的合法元素 ；验证 Alice 提交的知识证明，以确认她确实知道 $x$。
   将 $(y, z)$ 存储起来，用于日后“打开”群签名。
   生成成员证书：$v = (y + 1)^{1/e} \pmod{n}$ 并将 $v$ 发送给 Alice。
3. Alice 执行：
   验证 $v$ 的正确性。若验证通过，则存储该证书 $v$，用于后续生成群签名。

RSA群签名—成员生成群签名

1. 随机选择 $r \in Z_n^*$ 并计算 $\tilde{g} = g^r$
2. 计算 $\tilde{z} = \tilde{g}^y \pmod{n}$
3. 计算知识证明 $v_1$ = SKLOGLOG[ $x:\widetilde{z}=\widetilde{g}^{α^x}$ ]
4. 计算知识证明 计算$v_2$ = SKROOTLOG[ $v:\widetilde{z}\widetilde{g}=\widetilde{g}^{v^e}$ ]
5. 群签名的结果为$sig=\\{\widetilde{g}, \widetilde{z}, v_1, v_2\\}$

RSA群签名—群签名的验证

1. 验证 $v_1$，证明签名者知道私钥 $x$，并确认 $\tilde{z}$ 的形式为 $\tilde{g}^{a^x}$。
2. 根据 $v_1$ 可推出 $\tilde{z}\tilde{g}$ 的形式为 $\tilde{g}^{a^x + 1}$。
3. 验证 $v_2$ 成功则说明签名者知道 $(a^x + 1)$ 的 $e$ 次根，即 $(a^x + 1)^{1/e} = v$。这意味着签名者同时知道私钥 $x$ 以及对应的成员证书 $v$。综上可验证签名 $\text{sig}$ 确实来自该群的某个合法成员。

RSA群签名—打开群签名

1. 当遇到特殊情况时，需要知道签名者的真实身份，这是群管理员可以做到这一点：由于$\widetilde{z}=\widetilde{g}^{\ y}(mod \ n)$，且GM存储了每个群成员的（y，z）。所以，GM遍历所有的 y ，如果满足上述等式，就能找到签名者的真实身份。

---

参考文献：

• 97年发表的论文《 Efficient Group Signature Schemes for Large Groups 》
• CSDN：https://blog.csdn.net/zhang_hui_cs/article/details/8965338

---

2.2 BBS群签名

BBS群签名算法由Boneh、Boyen和Shacham于2004年提出，是群签名发展史上的一个重要里程碑。它首次在强安全模型下实现了高效且简洁的设计，其中群签名的大小为常数，生成签名和验证签名的时间复杂度也为常数。相比早期方案，BBS在签名长度和验证效率上都有显著改进，因此被广泛视为现代群签名的标准构造之一。BBS签名也已经在实际中得到应用，例如在W3C的Verifiable Credentials标准草案中被用于实现选择性披露和隐私保护，在新西兰的身份技术公司MATTR的去中心化身份产品中也被全面实现，并被作为隐私设计的核心组件。

线性加密(LE)： 为便于理解 BBS 签名，先简要介绍线性加密。LE 基于决策线性假设，是 ElGamal 的自然扩展；与依赖 DDH 难性的 ElGamal 不同，LE 即便在 DDH 可判定（例如配对群）中仍可达到 IND-CPA 安全。具体来说，线性加密的过程如下：

• 系统初始化：设 $G_1$ 为素数阶 $p$ 的循环群(通常取自双线性配对环境)，公开参数为 $u,v,h \in G_1$ 密钥生成选择秘密指数 $x,y \in \mathbb{Z}_p$ 使得 $h = u^x = v^y$ 公钥为 $(u,v,h)$，私钥为 $(x,y)$。
• 加密：对于消息 $M \in G_1$，随机取 $a,b \leftarrow \mathbb{Z}_p$，输出密文 $(T_1,T_2,T_3) = (u^a, v^b, M \cdot h^{a+b})$
• 解密：利用私钥计算 $M = \frac{T_3}{T_1^x \cdot T_2^y}$，正确性来自 $T_1^x \cdot T_2^y = u^{ax} \cdot v^{by} = h^a \cdot h^b = h^{a+b}$。

安全性方面，在“决策线性”假设成立时（非正式地说：给定 $(g,u,v,g^a,u^b,T)$ 难以区分元素 T 是 $v^{a+b}$ 还是 $v^c$ 的情形），该方案满足选择明文攻击下的语义安全（IND-CPA）。这说明 LE 的安全性并不依赖 DDH 的困难性，因此适合在 DDH 可判定的配对群中使用。

---

BBS群签名–系统初始化

1. 选取双线性映射 $e:G_1\times G_2\to G_T$，生成元 $g_2\in G_2$ 和 $g_1\leftarrow \psi(g_2)$（$\psi$ 为同构映射）。
2. 随机选 $h\leftarrow G_1\setminus\\{1\\}$，并选取 $\xi_1,\xi_2\leftarrow \mathbb{Z}_p^\*$，取 $u,v\in G_1$ 使得 $u^{\xi_1}=v^{\xi_2}=h$ 。
3. 随机选 $\gamma\leftarrow \mathbb{Z}_p^\*$ 并置 $w=g_2^\gamma$。
4. 公钥为 $gpk=(g_1,g_2,h,u,v,w)$。群管理员私钥为 $gmsk=(\xi_1,\xi_2)$。
   用户 $i$ 的群成员私钥为 $gsk[i]=(A_i,x_i)$。
   参数 $\gamma$ 仅为证书签发方所知，不用于追踪。

BBS群签名–成员加入

1. 加入方选择随机 $x_i\in \mathbb{Z}_p^\*$ 发送给证书签发者【可由群管理员充当】
2. 证书签发者使用 $\gamma$ 计算群成员证书 $A_i=g_1^{1/(\gamma+x_i)}$ 发给用户。
3. 用户保存 $gsk[i] = (A_i,x_i)$ 作为自身的群成员私钥。

BBS群签名–成员生成群签名

1. 对消息 $M$，持有群成员私钥的 $(A_i,x_i)$ 的用户 i 生成随机数 $\alpha,\beta\leftarrow \mathbb{Z}_p$；
2. 以计算 $A_i$ 的线性加密密文 $ T_1=u^\alpha,\ T_2=v^\beta,\ T_3=A_i\cdot h^{\alpha+\beta}. $
3. 同时分别计算 $\delta_1=x_i\alpha$，$\delta_2=x_i\beta$。
4. 生成五个随机数 $r_{\alpha},r_{\beta},r_x,r_{\delta_1},r_{\delta_2}\leftarrow \mathbb{Z}_p$，并计算这些随机数的承诺：

$$\begin{aligned} R_1 &= u^{r_\alpha}, \quad R_2 = v^{r_\beta}, \quad R_4 = T_1^{\,r_x}\cdot u^{-r_{\delta_1}}, \quad R_5 = T_2^{\,r_x}\cdot v^{-r_{\delta_2}}, \\ R_3 &= e(T_3,g_2)^{r_x}\cdot e(h,w)^{-r_\alpha-r_\beta} \cdot e(h,g_2)^{-r_{\delta_1}-r_{\delta_2}}. \end{aligned}$$

5. 计算挑战 $c=H(M,T_1,T_2,T_3,R_1,R_2,R_3,R_4,R_5)\in\mathbb{Z}_p$
6. 计算响应：【BBS可以看成一个NIZK，这里的承诺+挑战+响应真实sigma协议的标准步骤】
   $$s_\alpha=r_\alpha+c\alpha,\ \ s_\beta=r_\beta+c\beta,\ \ s_x=r_x+cx_i,\ \ s_{\delta_1}=r_{\delta_1}+c\delta_1,\ \ s_{\delta_2}=r_{\delta_2}+c\delta_2.$$
7. 输出群签名 $ \sigma=(T_1,T_2,T_3,\ c,\ s_\alpha,s_\beta,s_x,s_{\delta_1},s_{\delta_2}). $

BBS群签名–签名验证

1. 给定 $gpk=(g_1,g_2,h,u,v,w)$、消息 $M$ 与签名 $\sigma$，由响应值重构承诺
   $$\begin{array}{l} \tilde R_1=u^{s_\alpha}\cdot T_1^{-c}, \quad \tilde R_2=v^{s_\beta}\cdot T_2^{-c}, \quad \tilde R_4=T_1^{\,s_x}\cdot u^{-s_{\delta_1}}, \quad \tilde R_5=T_2^{\,s_x}\cdot v^{-s_{\delta_2}},\\ \tilde R_3=e(T_3,g_2)^{s_x}\cdot e(h,w)^{-s_\alpha-s_\beta}\cdot e(h,g_2)^{-s_{\delta_1}-s_{\delta_2}}\cdot\Big(\frac{e(T_3,w)}{e(g_1,g_2)}\Big)^{c}. \end{array}$$
2. 接受群签名的合法性，当且仅当下式成立 $ c\stackrel{?}=H\left(M,T_1,T_2,T_3,\tilde R_1,\tilde R_2,\tilde R_3,\tilde R_4,\tilde R_5\right). $

BBS群签名–打开签名（追踪）

1. 先验证 $\sigma$ 的有效性；若无效则拒绝。
2. 将 $(T_1,T_2,T_3)$ 视为线性加密密文，用追踪私钥 $gmsk=(\xi_1,\xi_2)$ 复原 $ A\leftarrow T_3/ (T_1^{\xi_1}\cdot T_2^{\xi_2}). $
3. 在登记表中查找与 $A$ 对应的成员索引（或与 $(A_i,x_i)$ 关联的身份），从而确定真实签名者。

---

关于BBS的简单注释：

1. BBS 群签名方案的总体思路：

   • 群管理员（GM）首先生成群签名所需的全局参数，以及群公钥和群私钥等。其中还包含一个秘密参数 $\gamma$，它将被用于为群成员颁发成员证书。
   • 当某个用户申请加入群组时，GM 使用秘密参数 $\gamma$ 为该用户生成一对群成员证书 $(A_i, x_i)$。
   • 当成员需要对消息进行群签名时，他会证明自己确实持有合法的群成员证书$(A_i, x_i)$，同时使用 GM 的公钥通过加密机制（LE 加密）将自己的真实身份加密在签名中，使得 GM 在必要时可以用私钥解密并追踪到签名者的身份。

2. 正确性证明
   在验证过程中，需要检查以下五个等式：

   $$u^{s_\alpha} \stackrel{?}{=} T_1^{c} \cdot R_1 \tag{4}$$
   $$v^{s_\beta} \stackrel{?}{=} T_2^{c} \cdot R_2 \tag{5}$$
   $$e(T_3, g_2)^{s_c} \cdot e(h, w)^{-s_\alpha - s_\beta} \cdot e(h, g_2)^{-s_{\delta_1} - s_{\delta_2}} \stackrel{?}{=} \left( \frac{e(g_1, g_2)}{e(T_3, w)} \right)^c \cdot R_3 \tag{6}$$
   $$T_1^{s_x} \cdot u^{-s_{\delta_1}} \stackrel{?}{=} R_4 \tag{7}$$
   $$T_2^{s_x} \cdot v^{-s_{\delta_2}} \stackrel{?}{=} R_5 \tag{8}$$
   首先证明 (4) 式的正确性，(5)式的证明同理可得，这里不再赘述。由构造可得：
   $$u^{s_\alpha} = u^{r_\alpha + c \alpha} = (u^{\alpha})^{c} \cdot u^{r_\alpha} = T_1^{c} \cdot R_1$$
   然后，我们证明 (7) 式的正确性，(8) 式的证明同理可得。由构造可得：
   $$T_1^{s_x} \cdot u^{-s_{\delta_1}} = (u^{\alpha})^{cx} \cdot u^{r_x} \cdot u^{-r_{\delta_1}} = T_1^{cx} \cdot u^{r_x - r_{\delta_1}} = R_4$$
   最后，我们证明 (6) 式的正确性，由构造可得：
   $$\begin{array}{c} e(T_3, g_2)^{s_c} \cdot e(h, w)^{-s_\alpha - s_\beta} \cdot e(h, g_2)^{-s_{\delta_1} - s_{\delta_2}} \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ e(T_3, g_2)^{c x_c + r_c} \cdot e(h, w)^{-r_\alpha - r_\beta - c \alpha - c \beta} \cdot e(h, g_2)^{-r_{\delta_1} - r_{\delta_2}} \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ e(T_3, g_2)^{cx_c} \cdot e(T_3, g_2)^{r_c} \cdot e(h, w)^{-r_\alpha - r_\beta} \cdot e(h, w)^{-c(\alpha + \beta)} \cdot e(h, g_2)^{-r_{\delta_1} - r_{\delta_2}} \\ \Downarrow \quad \Downarrow \quad \Downarrow \\ \left( \frac{e(g_1, g_2)}{e(T_3, w)} \right)^{c} \cdot \underbrace{ \Big( e(T_3, g_2)^{r_c} \cdot e(h, w)^{-r_\alpha - r_\beta} \cdot e(h, g_2)^{-r_{\delta_1} - r_{\delta_2}} \Big) }_{R_3} \end{array}$$

3. 关于方案的说明：

   • BBS群签名方案可以被看作是一非交互式的零知识证明 $π_i$，其具体形式可参考原论文中的详细描述。
   • BBS 群签名的核心思想是通过零知识证明来表明签名者确实持有合法的群成员证书 $(A, x)$，使得：$A^{\gamma + x} = g_1$ 。等价地，可以写作：$e(A, w g_1^x) = e(g_1, g_2)$ 。
     由于在不知道 $\gamma$ 的情况下，计算一个伪造的 $(A,x)$ 满足 $A = g_1^{1/(\gamma+x)}$ 在计算上是不可行的，因此，验证该零知识证明等价于验证签名者确实拥有有效的群成员证书。
   • 在签名过程中，$\{R_1, R_2, R_3, R_4, R_5\}$ 以及 $\{S_\alpha, S_\beta, S_x, S_{\delta_1}, S_{\delta_2}\}$ 的计算过程本质上是将一个交互式 Sigma 协议通过 Fiat–Shamir 启发式转换为非交互式零知识证明。

参考文献

• BBS签名原论文：《Short Group Signatures》
• BBS签名的Go语言实现：https://blog.csdn.net/Gassuih/article/details/117417328

---

2.3 CL签名方案

作者在论文中循序渐进的提出CL签名方案，前两个方案是为第三个方案做铺垫的。这里第一个版本和第二个版本是第三个版本的特例

第一个版本的CL签名:【记作CL01】

1. 参数生成： 通过安全参数生成双线性映射的相关参数:$Params=\\{q,G_1,G_2,e,g_1,g_2,e\\}$。其中 $G_1,G_2$ 分别是生成元为 $g_1$ 和 $g_2$ 的循环群, $e:G_1×G_1→G_2$ 是一个双线性映射.
2. 密钥生成： 选择 $x∈_RZ_q^* \ ;\ y∈_RZ_q^*$ 计算 $X=g_1^x\ ; Y=g_1^y$ ; 则私钥为$(x,y)$公钥为$(X,Y)$
3. 签名： 对于消息m , 签名者选择$a∈_RG$ ; 计算 $\sigma=(a,a^y,a^{x+mxy})$ 作为签名。
4. 验签： 如果 $e(a,Y) =e (g_1,b)$ 和 $e(X,a)e(X,b)^m = e(g_1,c)$ 都成立，则验证通过。

关于上述方案的说明:

• 事实上,签名者不需要知道消息m也能对消息m进行签名. 例如: V给签名者S一个$M=g^m$; 则签名者S可以通过下面的式子计算签名: $\sigma=(a,a^y,a^xM^{rxy})$
• 容易看出,上述方式可在不知道消息 m 的情况下计算出 m 的签名，类似于盲签名.
• 在构造群签名时：
  • 为了加入一个组，一个新成员将选择一个秘密m，然后向群管理员提供 $g^m$ 以及一个零知识证明，证明自己知道 $g^m$ 中的离散对数 m。从而获得群管理员颁发的成员证书 $(a, b, c)$。
  • 如果用户使用相同的秘密m成为多个组的成员，不同组的组管理员可以发现他们正在与同一个用户交谈。这是因为：当两个组管理器使用相同的生成元 $g$ 时,该用户在两个群中的证书完全相同。 而当一个群管理员使用生成元 $g$，另一个群管理员使用生成元 $h$ 时，两个组管理员通过比较$e(g^m,h) = e(g,h)^m = e(g,h^m)$ 是否相等即可判断用户是否为同一个人.

第二个签名:【记作CL02】

1. 参数生成： 通过安全参数生成双线性映射的相关参数:$Params=\\{q,G_1,G_2,e,g_1,g_2,e\\}$。其中 $G_1,G_2$ 分别是生成元为 $g_1$ 和 $g_2$ 的循环群, $e:G_1×G_1→G_2$ 是一个双线性映射.
2. 密钥生成： 选取随机值 $x, y, z \in \mathbb{Z}_q$ 作为私钥，并计算公钥 $X = g^x, \ Y = g^y, \ Z = g^z$。
3. 签名： 给定待签名消息 $m \in G$，生成随机群元素 $a \in G$，并计算 $A = a^z, \ b = a^x, \ B = a^y$ 和 $c = a^{x + xy m} \cdot A^{x y r}$。 最终输出签名为：$\sigma = (a, A, b, B, c)$
4. 验证： 给定消息 $m$、签名 $\sigma$ 和公钥 $\text{pk}$，若以下等式均成立，则验证通过。

$$\begin{array}{c} e(a, Z) = e(g, A) \quad; \quad e(a, Y) = e(g, b) \quad; \quad e(A, Y) = e(g, B) \\ e(X, a) \cdot e(X, b)^m \cdot e(X, B)^{r} = e(g, c) \end{array}$$

关于上述方案的说明:

• 事实上,签名者不需要知道消息m也能对消息m进行签名. 例如: V给签名者S一个$M=g^mZ^r$; 则签名者S可以通过下面的式子计算签名: $\sigma=(a,A=a^z,b=a^y,B=A^y,c=a^xM^{αxy})$
• 容易看出,上述方式计算出的签名和正常计算得到的签名是完全一样的,区别在于用上述方法生成签名不需要知道消息m. 类似于盲签名.
• 在这种签名中,敌手在不知道消息m的情况下,可以直接向喻言机请求M的签名,从而伪造签名.,尽管他不知道如何用g和Z去表示M. 为了防止这种预测,可以使用一个零知识证明向签名方证明自己知道如何用g和Z去表示M也就是知道$M=g^mZ^r$中的m和r .

第三个签名:【记作CL03】

1. 参数生成： 通过安全参数生成双线性映射的相关参数：$Params = \\{q, G_1, G_2, e, g\\}$，其中$G_1, G_2$均为阶为大素数$q$的循环群，$g$是$G_1$的生成元，$e: G_1 \times G_1 \to G_2$ 是双线性映射。
2. 密钥生成： 选取随机值 $x, y \in Z_q$ 和 $\\{z_i \in Z_q\\}_{i=1,2,\cdots,l}$ 作为私钥，其中 $l$ 为消息分量的个数；并计算公钥如下：

$$X = g^x, \quad Y = g^y, \quad \\{Z_i = g^{z_i}\\}_{i=1,\cdots,l}$$

3. 签名： 给定待签名消息向量 $m = (m_0, m_1, \ldots, m_l) \in \mathbb{Z}_q^{l+1}$，随机选择 $a \in G_1$ 计算签名

$$A_i = a^{z_i} \quad (i=1,2,\ldots,l), \quad b = a^y, \quad B_i = A_i^y = b^{z_i} \quad (i=1,2,\ldots,l)$$

$$C = a^{x + x y m_0} \cdot \prod_{i=1}^l A_i^{x y m_i}$$

4. 验证： 给定消息向量 $m = (m_0, m_1, \ldots, m_l)$、签名 $\sigma$ 和公钥 $pk$，若下式均成立验证通过：
   $$\begin{array}{c} e(a, Z_i) = e(g, A_i) \quad ; \quad e(a, Y) = e(g, b) \quad ; \quad e(A_i, Y) = e(g, B_i) \quad (i=1,2,\ldots,l) \\ e(X, a) \cdot e(X, b)^{m_0} \cdot \prod_{i=1}^l e(X, B_i)^{m_i} = e(g, C) \end{array}$$

关于上述方案的说明：

• CL03是CL01、CL02的推广形式，其盲签名特性与CL02类似，但需针对多消息分量构造零知识证明。签名者可在不知道具体消息 $(m_0, m_1, \ldots, m_l)$ 的情况下生成签名，只需接收消息承诺 $M = g^{m_0} \prod_{i=1}^l Z_i^{m_i}$，并通过零知识证明验证承诺的有效性（即证明者知道 $M$ 中隐藏的消息分量），零知识证明形式为： $ PK{(\mu_0, \mu_1, \ldots, \mu_l) : M = g^{\mu_0} \prod_{i=1}^l Z_i^{\mu_i}} $
• CL03支持多消息分量的盲签名。签名者无需知道具体消息 $(m_0, m_1, \ldots, m_l)$，只需获取消息承诺 $M = g^{m_0} \prod_{i=1}^l Z_i^{m_i}$，即可生成有效签名。具体步骤为：
  1. 选择随机值 $α \in \mathbb{Z}_q$，令 $a = g^α$（与正常签名的 $a$ 生成方式一致）；
  2. 计算 $A_i = a^{z_i}$（$i=1,\ldots,l$）、$b = a^y$、$B_i = A_i^y$（$i=1,\ldots,l$）；
  3. 计算 $C = a^x \cdot M^{x y}$；
  4. 输出签名 $\sigma = (a, \{A_i\}, b, \{B_i\}, C)$。 此时生成的签名与正常签名完全一致，因为：
     $$C = a^x \cdot M^{x y} = a^x \cdot \left(g^{m_0} \prod_{i=1}^l Z_i^{m_i}\right)^{x y} = a^x \cdot g^{x y (m_0 + \sum_{i=1}^l z_i m_i)}$$
     而正常签名的 $C$ 可展开为：
     $$C = a^{x + x y m_0} \prod_{i=1}^l A_i^{x y m_i} = a^x \cdot a^{x y m_0} \prod_{i=1}^l (a^{z_i})^{x y m_i} = a^x \cdot a^{x y (m_0 + \sum_{i=1}^l z_i m_i)}$$
     由于 $a = g^α$，$g^{x y (m_0 + \sum_{i=1}^l z_i m_i)} = (g^{m_0 + \sum_{i=1}^l z_i m_i})^{x y} = M^{x y}$，故两者等价。

---

CL组签名方案【记作CL04】

CL04群签名–系统初始化

1. 群管理器选取双线性映射参数集合 $(q,G_1,G_2,e,g_1,g_2)$，其中 $G_1$ 的生成元为 $g_1$、$G_2$ 的生成元为 $g_2 = e(g_1, g_1)$，双线性映射函数则为 $e: G_1 \times G_1 \to G_2$。
2. 选择两个随机数 $(x, y) \in Z_q^2$ 作为群私钥 $sk_{GM}$，并计算群公钥 $pk_{GM} = \\{X = g_1^x, Y = g_1^y \\}$ 将 $\\{ X = g_1^x, Y = g_1^y, g_1, G_1, G_2, e \\}$ 作为公共参数公开。
3. 选择 $x_1, x_2, x_3, x_4, x_5 \in Z_q$，$h \in G_2$ 并计算 $ y_1 = g_2^{x_1} \cdot h^{x_2}, \ y_2 = g_2^{x_3} \cdot h^{x_4}, \ y_3 = g_2^{x_5} $ 全局公钥为： $pk_{G} = \\{ h, y_1, y_2, y_3, H(\cdot) \\}$，其中 $H(\cdot)$ 是哈希函数。

CL04群签名–群成员加入

1. 用户选择随机私钥 $k \in \mathbb{Z}_q$，将成员公钥 $P = g_1^k$ 和 $\pi=\text{SPK}\\{k: P = g_1^k\\}$ 发送给 GM。
2. 群管理员验证 $P \in G_1$ 后，选择随机数 $r \in \mathbb{Z}_q$，计算证书：
   $$a = g_1^r, \quad b = a^y = Y^r, \quad c = a^x \cdot P^{xy} = X^r \cdot (P^y)^x$$
   群管理员将证书 $\text{cert} = (a, b, c)$ 发送给用户，用户拿到证书后即成功加入了群组。

CL04群签名–群签名生成

用户持有 $(sk_{\text{user}} = k, P = g_1^k, \text{cert} = (a, b, c))$，对消息 $m \in \\{0,1\\}^*$ 生成群签名：

1. 计算 $\phi = e(P, g_1) = e(g_1^k, g_1) = g_2^k$，
2. 选择随机数 $\gamma, \gamma' \in \mathbb{Z}_q$，对证书 $\text{cert} = (a, b, c)$ 进行盲化：
   $$\tilde{a} = a^\gamma = g_1^{r\gamma}, \quad \tilde{b} = b^\gamma = Y^{r\gamma} = \tilde{a}^y, \quad \tilde{c} = c^\gamma \cdot \phi^{\gamma'} = (X^r \cdot P^{xy})^\gamma \cdot g_2^{k\gamma'}$$
3. 选择随机数 $u \in \mathbb{Z}_q$，计算：
   $$c_1 = g_2^u , \ c_2 = h^u , \ c_3 = y_1^u \cdot \phi , \ c_4 = y_2^u \cdot y_3^{H(c_1, c_2, c_3, m)}$$
4. 构造零知识证明 $\Sigma$，证明以下陈述（不泄露隐私）： $$ \Sigma = \text{SPK} \left\{ \left. \vcenter{ \hbox{($\mu, \rho, \nu$):} % 左边元素 } \right. \quad \begin{aligned} & e(\tilde{a}, Y) = e(g_1, \tilde{b})\ \ \land \ \ c_1 = g_1^\nu \ \ \land \ \ c_2 = h^\nu \ \ \land \ \ \ &c_3 = y_1^\nu \cdot g_2^\rho \land \ c_4 = \left(y_2 \cdot y_3^{H(c_1, c_2, c_3, m)}\right)^\nu \end{aligned} \right\} $$
5. 生成群签名 $ \delta = \left( \tilde{a}, \tilde{b}, \tilde{c}, c_1, c_2, c_3, c_4, \Sigma \right) $

CL04群签名–验证群签名

验证者收到群签名 $\delta = (\tilde{a}, \tilde{b}, \tilde{c}, c_1, c_2, c_3, c_4, \Sigma)$ 和消息 $m$，执行以下验证：

1. 运行 $\Sigma$ 的验证算法，检查证明是否有效（若失败，直接拒绝签名）。
2. 验证盲化后的证书 $(\tilde{a}, \tilde{b})$ 是否符合GM公钥 $Y = g_1^y$ 的约束 $e(\tilde{a}, Y) \stackrel{?}{=} e(g_1, \tilde{b})$，这个等式成立是因为 盲化时，$\tilde{b} = \tilde{a}^y$，故 $e(\tilde{a}, Y) = e(\tilde{a}, g_1^y) = e(g_1, \tilde{a})^y = e(g_1, \tilde{b})$，等式成立。

参考文献 CL原论文：

• 《Signature Schemes and Anonymous Credentials from Bilinear Maps》