知识库 / 群签名算法原理：从匿名集体到可追溯问责

群签名算法原理：从匿名集体到可追溯问责

算法原理 · 2026-10-15

概述

群签名（Group Signature）是 1991 年由 David Chaum 和 Evester Van Heyst 在论文《Group Signatures》中首次提出的密码学原语。它解决了一个看似矛盾的需求：如何既能匿名地代表群体签名，又能在必要时追溯签名者身份。

群签名的形式化安全定义由 Bellare、Micciancio 和 Warinschi 在 2003 年的论文《Foundations of Group Signatures》中首次给出。他们将安全属性分解为两个安全游戏：

不可伪造性游戏

CODE
challenger ← Setup(1^λ) → (gpk, gmsk)
 challenger ← KeyGen(gmsk) → (sk_i, gpk)  for i ∈ [n]
 adversary ← Oracles(sk_i) → σ
 若 Verify(gpk, m, σ) = 1 且 σ 未被之前的 KeyGen 查询生成
 且 adversary 不是有效成员 → 胜出

形式化要求：任何 PPT adversary 获胜概率可忽略。

匿名性游戏

CODE
challenger ← Setup(1^λ) → (gpk, gmsk)
 challenger ← KeyGen(gmsk) → (sk_i, gpk)  for i ∈ [n]
 adversary → m*, 选择两个成员 i0, i1
 challenger ← b ∈ {0,1}, σ* ← Sign(sk_ib, m*)
 adversary 获得访问 KeyGen 和 Open 的预言机
 adversary → b'
 若 b' = b 且 i_b 未被撤销 → 胜出

形式化要求：任何 PPT adversary 的区分优势可忽略。

可追溯性

形式化定义为：任何 PPT adversary 无法生成一个通过 Verify 但 Open 失败或返回错误身份的签名。

原始方案：Chaum-Van Heyst 构造

Chaum 和 Van Heyst 的原始方案基于 RSA 困难问题，包含四个算法：

1. Setup

  • 选择大素数 p, q，令 n = pq
  • 选择 e 使得 gcd(e, (p-1)(q-1)) = 1
  • 计算 d = e^{-1} mod (p-1)(q-1)
  • 群公钥 gpk = (n, e)，群管理私钥 gmsk = (p, q)

2. KeyGen

每个成员 i 选择随机 r_i ∈ Z_n^*，计算：

  • 私钥 sk_i = r_i
  • 公钥组件 pk_i = r_i^e mod n
GM 维护成员列表 L = {(pk_1, ID_1), ..., (pk_n, ID_n)}。

3. Sign

成员 i 对消息 m 签名：

  • 选择随机 s ∈ Z_n^*
  • 计算 h = H(m || s^e mod n)
  • 计算 e' = (h + d) mod (p-1)(q-1)，其中 d 是 GM 私钥的一部分
  • 计算 σ = (s, e')

4. Verify

验证者检查：

  • 计算 h = H(m || σ_1^e mod n)
  • 验证 σ_2 = e^{-1}(h - σ_2') mod (p-1)(q-1) 是否成立

5. Open

GM 使用 gmsk = (p, q) 打开签名：

  • 从 σ_1 恢复 s
  • 查找 L 中满足 pk_i = s^e mod n 的成员 ID
安全性分析：原始方案存在以下缺陷：
  • 签名长度与群大小线性相关，不适用于大规模群体
  • 抗共谋性证明不完整
  • 效率较低，每次签名需要 O(n) 次运算

高效构造：Camenisch-Michels 方案

Camenisch 和 Michels 在 1998 年提出了第一个满足完全匿名性和完全可追溯性的高效群签名方案，解决了原始方案的三大缺陷。

核心思想

Camenisch-Michels 方案基于以下密码学工具：

  • RSA 假设：用于签名生成和验证
  • 强 Rabin 签名：用于成员证书的生成
  • 零知识证明：用于匿名性的保证
  • 模拟证明：用于安全归约

算法结构

Setup(n)：

  • 选择 RSA 模数 N = p·q，其中 p, q 为大素数
  • 选择公开指数 e
  • 计算私钥 d = e^{-1} mod φ(N)
  • 群公钥 gpk = (N, e)
  • 群管理私钥 gmsk = (d, 信息用于成员管理)
KeyGen(gmsk)：
  • GM 为成员 i 选择随机 r_i
  • 计算 u_i = r_i^e mod N
  • 生成成员私钥 sk_i = (r_i, 证书)
  • 证书 cert_i 是 GM 对 u_i 的签名
Sign(sk_i, m)：
  • 选择随机 a, b ∈ Z_N^*
  • 计算 commitment C = a^e · u_i^b mod N
  • 生成零知识证明 π 证明：
  • 知道 (a, b) 使得 C = a^e · u_i^b
  • 知道 (r_i, cert_i) 使得 u_i = r_i^e 且 cert_i 是有效签名
  • 计算签名 σ = (C, π, h, s)
Verify(gpk, m, σ)：
  • 验证零知识证明 π 的有效性
  • 验证签名结构完整性
Open(gmsk, σ)：
  • 使用 GM 私钥解密 C 恢复 u_i
  • 查表找到对应的成员 ID_i

安全性证明

Camenisch-Michels 方案的安全性基于以下假设：

  • RSA 假设：给定 (N, e) 和 y，难以找到 x 使得 x^e = y mod N
  • 强 RSA 假设：即使知道因子分解，也难以找到 e 次根
  • Fermat 素数假设：用于证明抗共谋性
证明策略采用归约法：假设存在攻破匿名性的 adversary，可以构造算法求解 RSA 问题，与假设矛盾。

效率分析

操作时间复杂度空间复杂度
SetupO(log N)O(1)
KeyGenO(log N)O(log N)
SignO(log²N)O(log N)
VerifyO(log²N)O(log N)
OpenO(log N)O(1)
相比原始方案，Camenisch-Michels 方案的签名长度不依赖群大小，实现了真正的"紧凑型"群签名。

现代进展与优化

Short Group Signatures

Boneh、Boyen 和 Shacham等人在 2004 年提出了基于双线性对的短群签名方案，显著减少了签名长度。

核心思想：

  • 使用 Boneh-Boyen 短签名作为基础
  • 利用双线性对的同态性质构造零知识证明
  • 签名长度从 O(log N) 压缩到 O(1)

Forward-Secure Group Signatures

forward-security 要求即使 GM 私钥在未来泄露，之前的签名仍然保持匿名性。构造方法：

  • 使用增量密钥更新机制
  • 结合时间戳和单向函数链
  • GM 私钥按时间段分段管理

Revocation 机制

成员撤销是群签名的核心挑战。主要方法：

方法一：黑名单机制

  • GM 维护撤销列表 Rev
  • 签名中必须包含对撤销列表的证明
  • 缺点：撤销列表 grows unboundedly
方法二： accumulator 机制
  • 使用累积器动态维护有效成员集合
  • 优点：常数大小，支持动态添加删除
  • 缺点：计算开销较大
方法三：时间戳+周期性更新
  • 签名绑定时间段
  • 定期更新群公钥
  • 撤销成员只需使其旧私钥失效

动态群签名

动态群签名支持成员的动态加入和离开，主要方案：

  • 基于累积器的动态方案：用密码学累积器维护成员集合
  • 基于树的结构：将成员组织成树结构，支持高效撤销
  • 基于身份的群签名：结合标识密码简化密钥管理

国密适配路径

群签名在国密场景下具有重要应用价值，特别是在以下领域：

  • 电子投票系统：选民匿名但可追溯
  • 供应链溯源：匿名参与但责任可追溯
  • 隐私计算联盟：多方协作中的匿名证明
  • 企业权限管理：员工匿名操作可审计

算法替换策略

国际算法国密替代说明
RSASM2 签名基于椭圆曲线，更安全高效
BLS 短签名SM2 简化签名利用 SM2 的确定性签名特性
双线性对暂无直接对应需使用其他技术替代

SM2 群签名设计思路

由于 SM2 标准不包含双线性对，设计 SM2 群签名需要额外技术手段：

  • 使用 SM2 替代 RSA：
  • 成员私钥：随机整数 r_i ∈ [1, n-1]
  • 成员公钥：R_i = [r_i]G，其中 G 是 SM2 生成元
  • GM 私钥：d_GM，GM 公钥：P_GM = [d_GM]G
  • 签名构造：
  • 成员选择随机 k
  • 计算承诺 C = [k]G
  • 生成 ZKP 证明知道 (k, r_i) 使得 C = [k]G 且 R_i = [r_i]G
  • 由于 SM2 无双线性对，ZKP 使用 Fiat-Shamir 启发式
  • 可追溯性：
  • GM 拥有所有成员的 r_i（或通过安全通道分发）
  • 打开时，GM 匹配 C 对应的 r_i，恢复成员身份

国密标准现状

目前，国家标准委尚未发布专门的群签名标准。相关研究参考：

  • GM/T 0003.2-2012：SM2 数字签名算法（群签名的基础组件）
  • GM/T 0010-2012：SM2 密码算法加密签名消息语法规范（签名格式）
建议在实际应用中参考国际标准（ISO/IEC 20008-2:2013）并结合国密算法进行适配设计。

相关实践

群签名的工程实现面临以下挑战：

  • 密钥管理复杂度：GM 私钥是单点故障，需 HSM 保护
  • 性能瓶颈：大规模群体的签名/验证开销
  • 隐私边界：追溯权与被追溯权的平衡
  • 标准兼容性：不同系统间的互操作性
如需深入了解群签名的工程实现细节，请参阅相关实践文章：

总结

群签名是密码学中一个优雅且实用的原语，其核心价值在于平衡匿名性与可追溯性。从 Chaum-Van Heyst 的开创性工作和 Camenisch-Michels 的高效构造，到现代短签名和动态撤销机制，群签名理论已相当成熟。

在国密场景下，群签名具有广阔的应用前景，特别是在电子投票、供应链溯源、隐私计算联盟等领域。虽然目前尚无专门的国密群签名标准，但基于 SM2 的设计思路已较为清晰。未来，随着国密标准的完善和工程实践的发展，群签名将在更多场景中发挥重要作用。

群签名的核心设计哲学——在匿名与可追溯之间取得平衡——对理解其他隐私保护技术（如零知识证明、混币方案）也有重要启发意义。

参考文献

  • D. Chaum and E. Van Heyst, "Group Signatures," in Advances in Cryptology — EUROCRYPT '91, LNCS 547, Springer, 1991, pp. 257–265.
  • M. Bellare, D. Micciancio, and B. Warinschi, "Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions," in ACM CCS 2003.
  • J. Camenisch and M. Michels, "A Group Signature Scheme with Improved Efficiency," in Advances in Cryptology — ASIACRYPT '98, LNCS 1514, Springer, 1998, pp. 160–174.
  • D. Boneh, X. Boyen, and H. Shacham, "Short Group Signatures," in Advances in Cryptology — CRYPTO 2004, LNCS 3152, Springer, 2004, pp. 41–55.
  • ISO/IEC 20008-2:2013, "Information technology — Security techniques — Anonymous digital signatures — Part 2: Mechanisms using a group public key."
  • GM/T 0003.2-2012, 《SM2 椭圆曲线公钥密码算法 第 2 部分：数字签名算法》.
← 返回知识库