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

陈颖 等: 具有用户自主链接及验证者条件撤销的格基群签名 4449

确实在 TAcc pp (R) 的累加中.
(4) 1/0 ← TVerify (u, d,w) : 输入累加值 u, 数据 d 以及对应的证据 w, 输出 1 说明 (d,w) 对于累加值 u 合法,
pp
否则, 输出 0.
(5) u ← TUpdate ( j, d ): 输入待修订叶子结点索引 以及更新后的值, 输出更新后累加值 .
u
′
′
j
′
pp
基于格的 (可更新) 默克尔树累加器依赖于格上抗碰撞哈希函数族, 这里给出定义.
定义 8 (格上抗碰撞哈希函数族 (family of lattice-based collision-resistant hash functions)). 哈希函数族
{ }
nk nk nk n×m n×nk
H : {0,1} ×{0,1} → {0,1} 可以被定义为 H = h A |A ∈ Z q , 其中, A = [A 0 |A 1 ], A 0 , A 1 ∈ Z q , 对于任意 (u 0 ,u 1 ) ∈
nk
nk
{0,1} ×{0,1}. 我们有: h A (u 0 ,u 1 ) = bin(A 0 u 0 +A 1 u 1 mod q) ∈ {0,1} . 这里, h A (u 0 ,u 1 ) = u ⇔ A 0 u 0 +A 1 u 1 = Gu mod q.
G ∈ Z n×nk 为“2 的幂次”工具矩阵:
q

 k−1 
 1,2,4,...,2 
 
 
 . 
  .  .

G =   . 
 
 
 k−1 
1,2,4,...,2
2.5 可验证随机函数
定义 9 (可验证随机函数 (verifiable random function, VRF) [16] ). 定义一个 VRF 函数输入长度为 n(λ), 输出长
度为 m(λ). 一个 VRF 函数由以下 3 个多项式时间算法构成.
(1) (sk,vk) ← Gen(λ) : 输入安全参数 λ, 输出公私钥对 (sk,vk).
(2) (y,π) ← Eval(sk, x) : 输入私钥 sk 以及数值 x ∈ {0,1} n(λ) , 返回输出值 y ∈ {0,1} m(λ) , 以及证明 π 说明该输出值 y
确实是在 pk 下以输入 x 生成的.
(3) 1/0 ← Verify(vk,π, x,y) : 输入公钥 vk, 证明 π, 以及输入输出 (x,y), 判断评估算法 Eval 的输出是否合法. 若
合法则返回 1, 否则返回 0.
VRF 函数需要满足可证明性、唯一性、自适应不可区分性. 具体定义如下.
● 可证明性 n(λ) , 我们有:
(provability). 对于任意的安全参数 λ 以及输入 x ∈ {0,1}
[ ]
(sk,vk) ← Gen(λ)
Pr : Verify(pk,π, x,y) = 1 = 1.
(y,π) ← Eval(sk, x)
● 唯一性 (uniqueness). 对于任意的安全参数 λ 以及输入 x ∈ {0,1} n(λ) , 任意公钥 pk, 存在至多一个单一的输出
m(λ)
,
′
′
′
y ∈ {0,1} 对于存在一个可被接受的证明 π. 若 Verify(pk,π, x,y) = Verify(pk,π , x,y ) = 1 y = y 一定成立.
● 自适应不可区分性 (adaptive indistinguishability). 对于任意多项式时间内的敌手 A, 至多以不可忽略的概率
negl(λ) 赢得下面的游戏.

Game A,VRF (λ)
Q := ∅
b ← {0,1} O 1 (sk, x)
(sk,vk) ← Gen(λ) (y,π) ← Eval(sk,x)
∗ O 1 (sk,·)
(st, x ) ← A (pk) Q := Q∪{x}
(y 0 ,π) ← Eval(sk,x ) return (y,π)
∗
m(λ)
y 1 ← {0,1}
′ O 1 (sk,·)
b ← A (st,y b )
return b = b ∧ x < Q
′
∗
3 具有用户自主链接及验证者条件撤销的群签名的语法及安全模型
本节介绍具有用户自主链接及验证者条件撤销的群签名的语法定义及安全模型.
3.1 具有用户自主链接及验证者条件撤销的群签名语法定义
定义 10 (具有用户自主链接及验证者条件撤销的群签名 (GS-UCL-VCR)). 一个 GS-UCL-VCR 方案包含: 系
统初始化 Setup, 群密钥生成 GKeyGen, 用户密钥生成 UKeyGen, 入群 Join, 群更新 GUpdate, 签名 Sign, 验签