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

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

 
 pp,gsk,gpk,info new ← Setup, GKeyGen,GUpdate 
 
 
 
 
 
 SO,LO (gpk) 
 (Π L ,nym,Σ) ← A 
 
    ⩽ negl(λ).

2 = Pr 
 
Adv Game trace  

 VLink(Σ,nym,Π L ) = 1  
 
 
 
 
 
 
∃Σ ∈ Σ s.t. ∀ ID ∈ reg∨RL : Identity(gpk,ID,Σ i ) = 0
定义 13 (不可诽谤性 (non-frameability)). 定义不可诽谤性游戏 Game noframe , 敌手 A 的目标是使得诚实用户的
签名与其从未产生过的签名相链接. 由于在本签名语法设定中, 由同一个 usk 在同一个 scp 下对不同消息产生的两
个签名可导致条件撤销, 故这里我们仅考虑 A 以不同的事件主题企图与诚实用户链接的情况. A 诽谤诚实用户可
以通过以下两种途径: (1) 伪造签名使其与诚实用户产生的签名相链接 (签名诽谤); (2) 为诚实用户产生一个链接
证明, 所涉及的签名均由该用户生成, 但该用户没有产生过该证明, 即证明本身是伪造的 (链接诽谤). 假设 ID = i
的诚实用户所产生的历史签名集合为 , Game ) 游戏的概率:
Σ i A 赢得不可诽谤 noframe
 
 pp,gsk,gpk,info new ← Setup,GKeyGen,GUpdate 
 
 
 
 
 
 SO,LO (gsk,gpk) 
 (Π L ,nym,Σ) ← A 
 
 
 
    ⩽ negl(λ).

Adv Game noframe = Pr  ′ ′ 
 
 (1) VLink(Σ,nym,Π L ) = 1 s.t. ∃Σ,Σ ∈ Σ : Σ ∈ Σ i ∧Σ ∈ Σ i 
 
 
 
 
 
 
 
 (2) VLink(Σ,nym,Π L ) = 1 s.t. ∀Σ ∈ Σ,Σ ∈ Σ i ∧(nym,Π L ) < LO (ID = i) 
4 基于格的具有用户自主链接及验证者条件撤销的群签名设计
本节描述基于格的具有用户自主链接及验证者条件撤销的群签名的具体构造. 在群签名的构造上, 借助格上
可更新的默克尔树累加器 [15] 及基于 SIS 和 LWE 的 Stern 类协议 [25] 实现对数级群签名尺寸同时保证匿名性. 在条
件撤销环节, 逆用同态陷门函数使其在既定条件下输出碰撞得到替代陷门求解撤销令牌. 在用户自主链接环节, 受
到 LaV 格上可验证随机函数的启发设计批量链接证明方法 [16] . 同时, 我们将第 2.3 节中所描述的对偶 Regev 公钥
( )
加密方案 Π PKE PKE.keyGen,PKE,Enc,PKE.Dec 作为黑盒使用. 具体方案描述如下.
⌈
⌉
( )
λ
(1) Setup 1 : 输入安全参数 λ, 正整数 n,m,q, p,σ,k,ι,κ,ω,ζ, 其中, k = log q ,m = 2nk, 设定群成员数量上限
2
ι ∗ ∗ n×m ∗ m×n
Q
为 N = 2 = poly(λ), scp ∈ {0,1} 数量上限为 , 满足 Q ≪ p; 选取哈希函数 H 1 : {0,1} → R q ,H 2 : {0,1} → R q ,
)
H 3 : {0,1} → {1,2,3} ,κ = ω logλ , 形如定义 8 中的工具矩阵 G 1 ,G 2 , 定义二进制转换函数 bin : R → {0,1} , 定义 VRF
(
nk
κ
∗
n
0, 初
函数 LaV : f x (B) = ⌊Bx⌋ p mod p. 群管理员 GM 初始化默克尔树 TSetup(pp,gpk) → T crt , 将所有叶子结点置为
( )
{ [ ][ ]} { [ ]}
m
始化用户计数器 c = 0, 初始化撤销列表 RL = ∅, 初始化用户注册列表为 reg [i] grt[i] upk[i] i∈[N] = [i][0 ] 0 nk .
输出系统公共参数集合 pp = {λ,n,m,q, p,κ,ω,ζ,σ,k,N,Q,H 1 ,H 2 , f,G 1 ,G 2 ,ι}.
(2) GKeyGen(pp,gpk) : 由群管理员 GM 执行. 运行 (A,T A ) ← TrapGen(1 ,1 ,q), 输出群密钥对 (gsk,gpk) =
n
m
n×m n×nk
(T A , A), A = (A 0 ||A 1 ) ∈ R , A 0 , A 1 ∈ R 以适配于格上哈希函数族.
m
n
m
(3) UKeyGen(pp,gpk) : 由用户本地执行. 运行 (b,T b ) ← GenTrap(1 ,1 ,q), 选择 x ← {0,1} (x , 0), 计算 d =
( )
bin Ax p , 输出自己的密钥对 (usk,upk) = ((T b , x),(b, d)).
(4) ⟨(ID,grt),⊥⟩ ← Join⟨user(upk),GM(gsk)⟩: 由用户与群管理员交互式进行.
a) user : 发送 upk = (b, d) 请求加入群.
√ [ ]
b) GM : 若同意请求, 则发布用户 ID 为 j = bin(c), 运行 s ← SamPre(A,T A ,σ, b), s ⩽ σ m, 将 usk j = (T b , x, s, j),
grt[i] = s 发送给用户; 更新树 T crt 计算新累加值 TUpdate ( j, d) → z new ; 更新用户计数器 c+ = 1; 更新用户注册列表
A
({[ ] })
reg = j [s][d] .
(5) GUpdate(gpk,gsk,info,RL,reg): 由群管理员 GM 执行.
∗
∗
∗
a) 若 RL = ∅, 则跳转到步骤 b). 否则, 解析 RL = {s 1 ,..., s ,...}, 对于撤销令牌为 s 作为本次撤销对象, 以 s 为
{ [ ]}
∗
索引在注册列表 reg 中找到 grt[I] = s 的用户元组 [I][s] upk[I] , 设置对应的 upk[I] = 0. 更新用户计数器 c− = 1.