Page 447 - 《软件学报》2026年第2期

926 软件学报 2026 年第 37 卷第 2 期

3) 挑战阶段: A 向 B 发送两个先前未请求过的关键词 w 0 ,w 1 , B 随机选取 b ∈ {0,1} 并生成 sd w b ,C sd w b ,td w b , B 发
给 A.
送 C sd w b ,td w b
4) 问答阶段 2: A 可以继续适应性地向 B 请求除 w 0 ,w 1 以外任意关键词 w 的陷门或强化关键词密文.
5) 输出阶段: A 输出猜测结果 b ∈ {0,1}, 若 b = b 则 A 获胜; 否则, A 失败.
′
′
A 赢得 SS-CKGA 挑战的优势定义为: Adv SS-CKGA (ℓ) = |Pr[b = b]−1/2|.
′
A
根据以下两个定理, CADC 可以被证明是 SS-CKGA 安全的.
定理 1. 如果 PPT 敌手 A 可以破坏 CADC 的 SS-CKGA 安全, 那么一定存在一个 PPT 敌手 B 可以破坏底层签
名 (BLS 签名 [55] ) 的安全性.
证明: 定理 2 的证明同服务器协助的 PEKS 方案 [53] 对 SS-CKGA 安全的证明. 由于 B 破坏底层签名安全性的
概率是可忽略的, 故 A 在 SS-CKGA Adv SS-CKGA (ℓ) = negl(ℓ).
中获胜的优势是可忽略的, 即
A
定理 2. 假设 Shamir 秘密共享方案 [56] 是安全的, 那么 CADC 中以分布式的方式生成给定关键词的签名的过程
就不会破坏 CADC 的 SS-CKGA 安全.
证明: 在 CADC 中, w 的签名 σ w 由多个作为密钥服务器的 App 参与生成, 其中各 App 使用 Shamir 秘密共享
w 进行签名. 但对于敌手 A 来说, 分布式方式 (即多个密钥服务器的情况) 和集中式方
方案共享私钥 s, 并使用 s 对
式 (即单个密钥服务器的情况) 并没有区别. 因为在问答阶段 1 和问答阶段 2 中, 当 A 向 B 请求强化关键词密文或
陷门时, B 与签名预言机交互, 接下来的挑战都基于该预言机的输出. 在挑战阶段, B 不能与签名预言机交互, 而是
w b 的签名以生成挑战关键词密文和陷门. 实际上, 上述所有过程对敌手 A 都是透明的, 不
随机选择一个元素作为
会影响 A 在 SS-CKGA 挑战中获胜的优势.
定义 3. 针对选择关键词攻击的不可区分性 (IND-CKA) 挑战定义如下.
ℓ, 挑战者 B 产生 App 端秘密共享, 其中一个 App (不失一般性地, A 1 ) 的公共参数
1) 初始化: 根据安全参数
sk 1 ,PSK 1 并发送给敌手 A.
2) 挑战阶段: A 向 B 发送两个关键词 w 0 ,w 1 , B 随机选取 b ∈ {0,1},r ∈ Z p , 计算签名 σ 1 并发送给 A.
3) 输出阶段: A 输出猜测结果 b ∈ {0,1}, 若 b = b, A 获胜.
′
′
′
A 赢得 IND-CKA 挑战的优势被定义为 Adv IND-CKA (ℓ) = |Pr[b = b]−1/2|.
A
根据以下定理, 方案是 IND-CKA 安全的.
定理 3. 如果存在一个 PPT 敌手 A 可以破坏 CADC 的 IND-CKA 安全, 那么就存在一个 PPT 敌手 B 可以破坏
门限盲签名方案 [57] 的盲性.
证明: 为了证明定理 4, 不失一般性地, 假设敌手 A 为 A 1 , B 将 A 作为子程序运行, 且对于挑战者来说是透明的.
在初始化时, B 收到来自挑战者的 sk 1 ,PSK 1 并发送给 A. 在挑战阶段, B 收到来自 A 的 w 0 ,w 1 并发送给挑战
w = rH (w b ) 并发送给 B, B σ 1 = sk 1 w 并发送给 A. 在输出阶
′
′
者, 挑战者随机选取 b ∈ {0,1},r ∈ Z p , 计算 计算签名
b b
′
′
段, A 向 B 发送猜测 b , B 也输出 b 作为其对 b 的猜测.
在上述过程中, 对于挑战者, B 是破坏了门限盲签名方案 [57] 的盲性的敌手; 对于 A, B 是 CADC 的 IND-CKA
挑战中的挑战者. 因此, B 破坏门限盲签名方案 [57] 的盲性的优势大于等于 A 在 CADC 挑战中获胜的优势
Adv IND-CKA (ℓ). 若 Adv IND-CKA (ℓ) > negl(ℓ), 则 B 一定能够以不可忽略的优势破坏门限盲签名方案 [57] 的盲性.
A A
此外, 在方案中即使部分 App 的子密钥泄露, 方案的安全性仍旧可以得到保证.
密钥具有如下形式:

 
   
 
t ∑ t ∑ ∏  n 
 η  ∑ 
sk = w i sk i =      f j (i)   (22)
 
 
 
     
  η−i  

i=1 i=1  1⩽η⩽t  j=1
η,i
,
由于敌手无法获取对于 j = 1,2,...,n i = 1,...,t 的全部 f j (i) 值, 因此敌手无法恢复出密钥 sk.
假设敌手 A 可以破坏任意 t (t < t) 个作为身份服务器的 App 并获取其秘密共享. A 的目标是获取受害用户
′
′