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

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

证明: 下面分别证明验证正确性, 链接验证正确性及条件可提取性.

● 验证正确性: 非交互式零知识证明协议 Φ 的完备性及哈希函数 H 1 ,H 2 的抗碰撞性保证了我们方案的验证
′
′
正确性. 根据接收到的信息, 验证者总能正确地通过事件主题 scp 及消息 µ 重新计算 V = H 1 (scp), H = H 2 (scp||µ).
X = (A,u, scp,G 1 ,G 2 ,nym,τ,ct,z new , H ,V ) 总能使得验证算法输
′
′
′
根据非交互式零知识证明协议 Φ 的完备性, 输入
出 1.
● 链接验证正确性: 根据引理 1, 可验证随机函数构造 LaV 的正确性, 以及参数设置条件 Q ≪ p, GS-UCL-
VCR 满足链接验证正确性. 对于某用户 ( usk = x) 在一个 scp 下的部分签名 (假名 nym): nym = V · x p , 故存在误差
q q q q
向量 e = Vx− ·nym,||e|| ⩽ 成立, 对于 e i = V i · x− ·nym ,i ∈ [K], 存在误差向量 ||e i || ⩽ , 将上述 K 个等式累加
i
p p p p
q q
可得 E = hscp· x− ·snym,||E|| ⩽ · K. 故根据方案中相关参数的设定, 考虑四舍五入带来的误差, 容易得到:
p p

p p
snym = hscp· x· − E· ≈ nym− E p ∓1 ⇒ |snym−nym| ⩽ |K|+1,
q q
即对于诚实用户的 K 个历史签名, ∆ = |snym−nym|, ||∆|| ∞ ⩽ K +1 显然成立.
与此同时, 若用户企图在其中链接一个其他用户 ( usk = x ) 在 scp 下的签名, 类似于上述分析方法, 对于等式
′
t
q q q q
′
e i = V i · x− ·nym i , i ∈ [t −1], e t = V t · x − ·nym t , e i = V i · x− ·nym i , i ∈ [t +1,K], 进行累加可得 ||E|| ⩽ · K. 根据
p p p p

p p

′
′
′
′
方案中相关参数设定, 容易得到 ∆ = snym−nym = ·V t (x − x)− · E , 又因为 K ⩽ Q ≪ p, 故 ||V t (x − x)|| > ||E ||,
q q
||∆|| ∞ > K +1. 因此无法通过链接验证.
● 条件可提取性: 利用 HTDF 的“碰撞”, 得到陷门 s 的替代 u 1 −u 2 , 作为私钥运行解密算法得到该用户的撤销
′ ∗
令牌 grt [π ], 将其反馈给群管理员 GM 将其加入撤销列表 RL.
综上所述, GS-UCL-VCR 同时满足验证正确性, 链接验证正确性及条件可提取性, 因此满足正确性. 证毕.
4.2 安全性分析
定理 4. 在随机谕言机模型下, GS-UCL-VCR 满足无私匿名性, 当以下条件同时成立: (1) 基于格的非交互式零
知识证明协议 Φ,Π L 满足零知识性; (2) LWE 问题是困难的; (3) 对偶 Regev 方案满足 IND-CPA 安全; (4) LWR 问
题是困难的; (5) 可验证随机函数 LaV 满足自适应不可区分性.
证明: 在挑战者 C 和敌手 A 之间建立以下几个游戏.
Game 0 : 这一游戏过程与 Game selfano 一致. C 真实地运行系统初始化算法 Setup, 群密钥生成算法 GKeyGen, 用
(gsk,gpk), 用户 ( ID = i) 密钥对及撤销令牌
户密钥生成算法 UKeyGen, 入群算法 Join 得到公共参数 pp, 群密钥对
(usk[i],upk[i],grt[i]). 将 pp,gpk 发送给 A. 在此游戏中, 所选择的挑战比特 b = 0.
,
Game 1 : 在这一游戏中, A 与模拟器 S 1 交互. 不同于 Game 0 S 1 运行模拟协议 S p 生成非交互式零知识证明协
*
议 Φ 的证明 Π . 根据协议 Φ 的零知识性:

Adv selfano (λ) ≈ Adv selfano (λ).
Game 0 Game 1
Game 2 : 在这一游戏中, A 与模拟器 S 2 交互. S 2 与 S 1 几乎一致, 密文 c 2 及 u 的生成方式除外. 不同于 Game 1
q
′
mk
∗
∗
中 c 2 = f · r+ · s ,u ← SamPre(b,T b ,σ,V + H ·G 1 ) 计算得出, 这里 S 2 直接从均匀分布中选取 c ← R ,u ← R 1×n ,
2 2
根据判定性 LWE 的困难性及定理 4:

Adv selfano (λ) ≈ Adv selfano (λ).
Game 2 Game 1
Game 3 : 在这一游戏中, S 3 交互. S 2 几乎一致, nym =
A 与模拟器 S 3 与 nym,τ 的生成方式除外. 不同于 Game 2 中
m
n
∗
∗
V · x p ,τ = H · s p 计算得出, 这里 S 3 直接从均匀分布中随机选取 nym ← Z ,τ ← Z , 根据 LWR 问题的困难性及可
p p
验证随机函数 LaV 的自适应不可区分性:

Adv selfano (λ) ≈ Adv selfano (λ).
Game 3 Game 2
Game 4 : 这一游戏与 Game 3 一致, A 与模拟器 S 4 交互. S 4 与 S 3 几乎一致, Π L 的生成方式除外. 不同于 Game 3