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

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

应的私钥 x π .
伪造: A 选择 个消息 (M 0 , M 1 ), 使用 pk π 对应的私钥 sk π 签名, 输出两个有效的签名 σ 0 = (I,c 1 ,q 1 ,...,q n ) 和
2
( )
′
′ ′ ′ ′ I , I .
σ 1 = I ,c ,q ,...,q , 并且
1 1 n
′
sk x
若 I = g sk π , I = g , 则 A 在仅拥有私钥 sk π 的情况下伪造了由私钥 sk x , sk π 生成的签名 σ 1 . 由环签名方案的
′
不可伪造性可知, 在离散对数困难问题的假设条件下, 敌手伪造出有效签名 σ 1 的概率是可忽略的, 因此有 I = I ,
与假设矛盾. 定理得证, 即方案满足可链接性.
(4) 不可诽谤性证明
定理 7. 在随机预言机模型下, 若 G 中的离散对数问题是困难的, 则方案满足不可诽谤性.
证明: 假设 A 为可有效伪造环签名概率多项式时间敌手, 则仿真器 S 可利用 A 的能力, 构造解决离散对数困
x
难问题的算法 . (g,Q = g ) 交给算法 B. 敌手 A 与算法 B 定义之间的实验如下.
B S 将离散对数问题实例
( )
λ
初始化: B 运行初始化算法 pp ← TRS.SetUp 1 , 并将公开参数 pp = {G,q,g, pk a ,H} 交给敌手 A. B 随机选取 n
*
* * * * * P = Q , i ∈ {1,2,...,n} 作为每个环签名
x i
个不同的环签名成员 A = {A ,A ,...,A }, 随机生成 x i ∈ Z (1 ⩽ i ⩽ n), 计算 i
q
1
2
n
* * * * * * * * *
成员对应的公钥, 记为 S = {P ,P ,...,P }, S 设置 S 为 A 的目标公钥集合, 并将 S = {P ,P ,...,P } 发送给 A.
1
2
n
2
1
n
查询 1: B 控制随机预言机 H 和 O R O C O S , A 查询上述预言机, 查询与应答过程同定理 4 中的查询过程.
,
,
S
挑战: A 将元组 (S,m,σ, pk π ) 提交给 , 该元组包含消息 m, 含有 n 个环签名成员公钥的集合 , 签名者公钥
B
* B 按照定理 4 pk π 私钥的情况下模
pk π ∈ S , 其中 pk π 未被用于查询 O C 和 O S 预言机. 证明过程中 O S 预言机在没有
′ A.
拟生成环签名 σ = (I,c 1 ,q 1 ,...,q n ), 并将 σ 交给
查询 2: B 控制随机预言机 H 和 O R O C O S , A 查询上述预言机, pk π 不能被用于查询 O C 和 O S 预言机, 查询与
,
,
应答过程同定理 4 中的查询过程.
)
(
*
*
*
*
*
ϵ
*
伪造: 敌手 A 以 的概率输出 ( m ,σ , pk π , 其中伪造签名 σ = I ,c ,q ,...,q * ) 为有效的环签名且与 σ 可链接.
1 1 n
* * A 伪造了由私钥
假设 A 可以不可忽略的概率 ϵ A 赢得实验, 由于 σ 与 σ 可链接并且 σ 为有效的环签名, 即
*
sk π 生成的签名 σ . 由环签名方案的不可伪造性可知, 在离散对数困难性的假设条件下, 敌手在未知 sk π 的情况下,
* O S 预言机的假设矛盾. 故定理得证, 即方案满
伪造出有效签名 σ 的概率是可忽略的, 与 pk π 未被用于查询 O C 和
足不可诽谤性. 证毕.
(5) 可追踪性证明
定理 8. 在随机预言机模型下, 若 G 中的离散对数问题是困难的, 方案满足签名者可追踪性.
证明: 假设 A 为可有效打破方案可追踪性的概率多项式时间敌手, A 可赢得其与仿真器 S 之间的实验 Expt tra (λ),
TRS
则以下条件成立.
( )
*
1) pk T ← TRS.Trace pp,σ , sk a .
( )
*
*
2) TRS.Ver pp,σ , pk a ,m = 1, 并且 σ 不是 O S 预言机的输出.
3) 对于所有 pk i ∈ S, pk i 是 O R 预言机的输出.
4) pk T , pk π , pk T 未被用于查询 O C 预言机.
( * ) *
∗
S 运行追踪算法得到签名者公钥 pk T ← TRS.Trace pp,σ , sk a , 又由 σ 为有效环签名, 而 σ 可与私钥为 sk T
sk T 的情
的签名者签署的环签名相链接. 由方案的不可诽谤性定义, 在离散对数困难性的假设条件下, 敌手在未知
*
*
况下, 伪造出有效签名 σ 的概率是可忽略的. 由方案的不可诽谤性, σ 为私钥 sk T 签署的有效签名与 pk T 未被用
于查询 O C 预言机的条件矛盾, 因此, 定理得证, 即方案满足可追踪性. 证毕.
5.2 RSIPP 方案定义及描述
5.2.1 方案定义
RSIPP 方案由下述算法构成.
( )
λ
RSIPP.SetUp 1 → (pp)
(1) 初始化算法
初始化算法通常由监管者执行, 用于生成公开参数.