Page 351 - 《软件学报》2026年第4期

1792 软件学报 2026 年第 37 卷第 4 期

sk π
2) 计算 I = pk .
a
* k k
3) 选取 k ∈ Z , 计算 L π = g 和 R π = pk , 计算 c π+1 = H (M ∥ pk 1 ||pk 2 ||...||pk n ∥ pk a ∥ I ∥ L π ∥ R π ).
q a
* q i c i q i c i
4) 对于 i ∈ {π+1,...,n,1,...,π−1}, 依次随机选取 q i ∈ Z , 计算 L i = g pk , R i = pk a I , c i+1 = H(M ∥ pk 1 ||pk 2 ||...
q i
||pk n ∥ pk a ∥ I ∥ L i ∥ R i ), 令 c 1 = c n+1 .
5) 计算 q π = k −c π sk π mod q.
6) 生成环签名 σ = (S,I,c 1 ,q 1 ,...,q n ).
(4) 环签名验证算法 TRS.Ver
验证者获取环签名 σ, 消息 M 和追踪者公钥 pk a 后, 对 σ 进行验证, 验证过程如下.
∗
1) 检查 c 1 ,q 1 ,...,q n ∈ Z 是否成立.
q
( )
′
′
′
′
c i
q i c i
q i
2) 对于 i ∈ {1,...,n}, 依次计算 L = g pk , R = pk a I , c ′ = H M ∥ pk 1 ∥ pk 2 ∥ ... ∥ pk n ∥ pk a ∥ I ∥ L ∥ R .
i i i i+1 i i
3) 检查 c 1 = c ′ 是否成立, 若成立, 则验证通过, 算法输出 1; 否则, 验证失败, 算法输出 0.
n+1
(5) 可链接性判断算法 TRS.Link
I
I
验证者获取环签名 σ 中的 , 若 在历史密钥镜像列表 L 中出现过, 则算法输出 1, 拒绝此签名; 否则, 算法输
出 0, 并将 I 加入 L 中.
(6) 签名者身份追踪算法 TRS.Trace
sk a I = pk , 则输
sk a
追踪者获取环签名 σ, 对于环签名成员公钥 pk i ∈ S , 追踪者使用追踪者私钥 sk a , 计算 pk , 若 i
i
pk i .
出签名者公钥
5.1.2 安全性证明
(1) 不可伪造性证明
定理 4. 在随机预言机模型下, 若 G 中的离散对数问题是困难的, 则方案满足不可伪造性.
证明: 假设 A 为可有效伪造环签名的概率多项式时间敌手, 则仿真器 S 可利用 A 的能力, 构造解决离散对数
x
问题的算法 . (g,Q = g ) 交给算法 B. 敌手 A 与算法 B 之间的实验定义如下.
B S 将离散对数问题实例
( )
λ
初始化: B 运行初始化算法 pp ← TRS.SetUp 1 , 并将公开参数 pp = {G,q,g, pk a } 交给敌手 A. 算法 B 随机选
* * * * * P = Q (i ∈ {1,2,...,n}) 作为每个环
*
x i
取 n 个不同的环签名成员 A = {A ,A ,...,A }, 随机生成 x i ∈ Z (1 ⩽ i ⩽ n), 计算
1 2 n q i
* * * * * *
签名成员对应的公钥, 记为 S = {P ,P ,...,P }, 仿真器S 设置 S 为 A 的目标公钥集合, 并将 S 发送给 A.
1 2 n
查询: B 控制随机预言机 H, O R , O C 和 O S , A 查询上述预言机. 查询与应答过程如下.
1) H 查询: B 维护一个初始为空的列表 LIST H . 对于查询 δ, B 查询其之前是否被查询过, 若之前被查询过, 则在
*
LIST H 中找到对应的 τ = H(δ), 并返回 τ, 若之前未被查询过, 则 B 随机选取 τ ∈ Z , 在 LIST H 中添加 {δ,τ}, 并返回 τ.
q
*
2) O R 查询: B 维护一个初始为空的列表 LIST R . A查询预言机O R , 注册新用户 A i . B 查询 A i 是否属于 A , 若是,
则不响应查询; 否则, B 查询 A i 是否被查询过, 若被查询过, 在 LIST R 中找到对应的公钥 pk i 并返回 pk i ; 否则, B 选
* sk i
取 sk i ∈ Z , 计算公钥为 pk i = g , 在 LIST R 中添加 {A i , sk i , pk i }, 并返回 pk i .
q
3) O S 查询: B 维护一个初始为空的列表 LIST S . A 将环签名成员公钥集合 S = {pk 1 , pk 2 ,..., pk n }、签名者公钥
,
′
′ (S, pk π , M ) B 按照下述步骤模拟生成环签名.
pk π 以及消息 M 提交给 O S 查询环签名. 对于查询
sk a
a) 计算 I = pk .
π
i ∈ {1,2,...,n−1}, 依次执行下述操作.
b) 对于
* q i c i q i c i
i) 随机选取 q i , c i ∈ Z , 计算 L i = g pk 和 R i = pk a I .
q i
LIST H 中, 若在, 则重新执行 i); 否则, 将
ii) 令 δ i+1 = (M ∥ pk 1 ||pk 2 ||...||pk n ∥ pk a ∥ I ∥ L i ∥ R i ), 检查 δ i+1 是否在列表
(δ i ,c i ) 添加到 LIST H 中.
* q n c n q n c n δ n+1 = (M ∥ pk 1 ||pk 2 ||...||pk n ∥ pk a ∥ I ∥ L n ∥ R n ), 检查
c) 随机选取 q n , c n ∈ Z , 计算 L n = g pk n 和 R n = pk a I , 令
q
δ n+1 是否在列表 LIST H 中, 若在, 则重新执行 c); 否则, 将 (δ n+1 ,c 1 ) 添加到 LIST H 中.
′
d) B 返回 σ = (I,c 1 ,q 1 ,...,q n ) 作为应答.