Page 53 - 《软件学报》2025年第10期

4450 软件学报 2025 年第 36 卷第 10 期

VLink 共 10 个多项式时间算法, 描述如下.
Verify, 提取撤销令牌 Extract, 用户自主链接 UCLink, 链接验证
( )
λ
(1) pp ← Setup 1 : 输入安全参数 λ, 输出系统公共参数 pp. 群管理员 GM 初始化 Merkle 树 TSetup(pp,gpk)
reg.
→ T crt , 将所有叶子结点置为 0, 初始化用户计数器 c = 0, 初始化撤销列表 RL = ∅, 初始化用户注册列表
(2) (gsk,gpk) ← GKeyGen(pp) : 输入公共参数 pp, 输出群密钥对 (gsk,gpk). 由群管理员 GM 执行.
(3) (usk,upk) ← UKeyGen(pp,gpk) : 输入公共参数 pp, 群公钥 gpk, 输出用户密钥对 (usk,upk). 由用户本地执行.
(4) ⟨(ID,grt),⊥⟩ ← Join⟨user(upk),GM(gsk)⟩ : 该算法由 GM 与用户交互式进行. 用户提交自己的公钥 upk 申
.
请入群, 若 GM 同意该入群请求, 用户将得到自己的群成员 ID 和撤销令牌 grt GM 更新树, 更新用户计数器
reg, 无输出.
c+ = 1, 更新用户注册列表
(5) info new ← GUpdate(gpk,gsk,info,RL,reg) : 输入群密钥对 (gsk,gpk), 当前群消息 info, 撤销列表 RL, 用户注册
列表 reg, 输出最新群消息 info . 由群管理员 GM 执行.
new
(6) Σ ← Sign(gpk,pp,usk[π], M ∈ {0,1} , scp,upk[π],grt[π]) : 输入群公钥 gpk, 系统公共参数 pp, 用户公私钥对
∗
Σ
(usk[π],upk[π]), 消息 M, 事件主题 scp, 撤销令牌 grt[π], 输出消息-签名对 . 由群成员 ID 为 π 的用户执行.
)
(
(7) 1/0 ← Verify gpk,pp,info new ,Σ,RL : 输入群公钥 gpk, 系统公共参数 pp, 最新群消息 info new , 消息-签名对 Σ,
RL. 输出 1 表示签名合法, 否则输出 GM 维护.
撤销列表 0. 由验证者执行. 其中输入的撤销列表 RL 由群管理员
(8) grt[π ]/ ⊥← Extract(Σ 1 ,Σ 2 ): 输入两个消息-签名对 Σ 1 ,Σ 2 , 若其是同一个事件主题 scp 下的不同签名, 则提
∗
∗ ⊥. 由验证者
取对应签名者的撤销令牌 grt[π ] 并输出, 反馈给群管理员 GM 将其添加在撤销列表 RL 中; 否则返回
执行.
(9) (Π L ,nym,Σ) ← UCLink(Σ,usk): 输入自己的历史消息-签名对集合 Σ = (Σ 1 ,Σ 2 ,...,Σ K ), 以及用户私钥 usk, 生
成链接证明 Π L 及聚合假名 nym 说明集合 Σ 中的签名均由自己所签. 由用户执行.
Σ
(10) 1/0 ← VLink(Σ,nym,Π L ): 输入某一用户的历史消息-签名对集合 , 聚合假名 nym, 以及对应的链接证明
Π L , 输出 1 表示证明合法, 否则输出 0. 任何人可以执行.
GS-UCL-VCR 方案满足正确性, 其同时满足签名验证正确性、链接验证正确性及条件可提取性.
● 签名验证正确性 (verification correctness). 一个 GS-UCL-VCR 方案满足签名验证正确性, 当且仅当对于所有
由系统初始化 Setup 产生的 pp, 群密钥生成算法 GKeyGen 产生的 gpk, 群更新算法 GUpdate 所产生的最新群消息
info new 及通过加入算法 Join 认证的持有密钥 (usk[i],upk[i]) 和撤销令牌 grt[i] 的群成员 ( ID = i) 所产生的签名均合
法, 除非该成员已被撤销. 正式地:

)
(
∗
Verify gpk,pp,GUpdate(gpk,gsk),Sign(gpk,pp,usk[i], M ∈ {0,1} , scp,upk[i],grt[i]),RL = 1 ⇔ grt[i] < RL.
● 链接正确性 (link correctness). 一个 GS-UCL-VCR 方案满足链接正确性, 当且仅当对于通过加入算法 Join 认
证的持有密钥 (usk[i],upk[i]) 和撤销令牌 grt[i] 的群成员 ( ID = i) 所产生合法消息-签名对集合 Σ = (Σ 1 ,Σ 2 ,...,Σ K ),
利用用户自主链接算法 UCLink 为其生成的链接证明 Π L 及聚合假名 nym, 一定可以通过链接验证算法的验证. 正
式地,

 ∗ 
 Σ j ← Sign(gpk,pp,usk[i], M ∈ {0,1} , scp,upk[i],grt[i]) 
 
 
 
   


Pr j = {1,2,...,K} : VLink(Σ,nym,Π L ) = 1 = 1.
   
 
 
 
Σ = (Σ 1 ,Σ 2 ,...,Σ K )
● 条件可提取性 (conditional extractability). 一个 GS-UCL-VCR 方案满足条件可提取性, 当且仅当对于所有由
系统初始化 Setup 产生的 pp, 群密钥生成算法 GKeyGen 产生的 gpk, 群更新算法 GUpdate 所产生的最新群消息
info 及通过加入算法 Join 认证的持有密钥 (usk[i],upk[i]) 和撤销令牌 grt[i] 的群成员 ( ID = i) 所产生的任意两
new
(
)
(
Σ 1 ← Sign gpk,pp,usk[i], M 1 ,scp ,upk[i],grt[i] Σ 2 ← Sign gpk,pp,usk[i], M 2 ,scp ,upk[i],grt[i] , 始
)
,
个消息-签名对 1 2
终满足:


 grt[i], if nym 1 = nym 2 ∧ M 1 , M 2


,
Extract(Σ 1 ,Σ 2 ) = 
⊥, otherwise

