Page 369 - 《软件学报》2025年第9期

4280 软件学报 2025 年第 36 卷第 9 期

回给 A. 分析真实方案中的陷门和 O T w 响应的陷门, 从敌手的角度这是不可区分的.

● 挑战阶段. A 决定结束上述询问后, 选取挑战关键词 w ,w ∈ {0,1} ,w = w , 挑战者 C 随机选取 b ∈ {0,1},

∗
∗
∗
∗
∗
0 1 0 1
∗ T i , ⊥ C 终止此次模拟 ∗ ∗ T w ∗ = r P 2 . 从
∗
如果 w 未曾被询问过谕言机且 , (记作事件 E 2 ). 否则选取随机数 r ∈ Z , 计算
b N b
A 的角度而言, 挑战关键词密文和真实密文是不可区分的, 即上述模拟过程和真正的方案攻击不可区分的.
● 询问阶段 2. 在此阶段, A 可继续进行同询问阶段 1 的询问, 但是此处限制 w i < {w 0 ,w 1 }.
● 猜测阶段. A 输出对挑战关键词密文中关键词的猜测. 若猜测正确, 则 A 赢得上述游戏, 否则失败. 若对于
,
∗
L 2 中的每个元组 < C i ,u i ,K i > C 可向谕言机 O DBIDH 查询 < [x]P 1 ,P 2 ,[t 0 + x]P 1 ,r P 1 ,u i >. 如果 O DBIDH 返回 1, 那么 C 输
1/r ∗ 作为 困难问题实例的解. 如果不存在这样的元组 G T 中的随机元
出 u i Gap-q-BCAA1 (记作事件 E 3 ), 那么 C 输出
素作为解.
1
概率分析: 令 A 赢得上述游戏为事件 E 4 , 根据上述分析有 Pr[E 4 |E 3 ] = , 公式 (12) 成立:
2

Pr[E 4 ] =Pr[E 4 |E 3 ]Pr[E 3 ]+Pr[E 4 |E 3 ]Pr[E 3 ]





 1


 ⩽ (1−Pr[E 3 ])+Pr[E 3 ]


 2




 1 1


 = + Pr[E 3 ]


 2 2
 (12)

Pr[E 4 ] ⩾Pr[E 4 |E 3 ]Pr[E 3 ]





 1


 = Pr[E 3 ]


 2




 1 1


 = − Pr[E 3 ]

2 2

1 1

若 A 能以不可忽略的优势 ϵ 2 攻破 SM9-PAEKS 方案的 CKA-TI 安全性, 有 ϵ 2 ⩽ Pr[E 4 − ⩽ Pr[E 3 ], 且根据
2 2
E 1 C 解决 Gap-q-BCAA1 困难问题实例的优势为:
.
上述游戏, 若 E 2 则有

1
Adv Gap-q-BCAA1 ⩾ ϵ 2 · (13)
C
q+1
引理 2 证毕.
综上, 通过引理 1 与引理 2 完成了对定理 1 的证明. SM9-PAEKS 具备 CI-CKA 和 TI-CKA 安全性.

4 性能分析
本节从理论分析和实验仿真测试两个角度对 SM9-PAEKS 与同类型经典方案进行比较, 所有方案均仅支持单
关键词检索. 统计各方案时仅考虑耗时较高的运算. 为便于后文清晰地描述各方案性能, 令 |C w | 和 |T w | 分别表示关
键词密文长度和关键词陷门长度, |G i | (i ∈ {1,2,T}) 表示群 G i 中单个元素的长度, |Z | 表示单个 Z ∗ N 元素的长度, |PK|
∗
N
表示用户公钥长度. T m1 表示 G 1 中的单次标量乘运算, T m2 表示 G 2 中的单次标量乘运算, T b 表示单次双线性对运
算, T e 表示 G T 上的单次模幂运算, T h2p 表示哈希至椭圆曲线上的一点.

4.1 理论分析
各方案的计算开销 (如表 1 所示), 关键词密文生成阶段 SM9-PAEKS 仅需 3 次 T m1 和 1 次 T e , Huang 等人 [15]
的方案需要 1 次 T h2p 和 3 次 T m1 , 而 Qin 等人 [17] 的方案需要 2 次 T b 、2 次 T m1 及 2 次 T h2p ; 关键词陷门生成阶段
SM9-PAEKS 仅需 1 次 T m1 和 1 次 T m2 , 避免了高耗时的 T b 运算, 而 Huang 等人 [15] 和 Qin 等人 [17] 的方案不仅需要
T m1 还需 1 次 T b ; 对于匹配测试算法, SM9-PAEKS 仅需 1 次 T b 运算, Huang 等人 [15] 的方案在此基础上增加 1 次
T h2p 运算, 而 Qin 等人 [17] 的方案需要 2 次 T b 运算.
在通信代价方面 (如表 1 所示), SM9-PAEKS 的关键词陷门长度为 |G 1 |+2|Z |, Huang 等人 [15] 和 Qin 等人 [17] 的
∗
N
∗
方案中的关键词陷门长度分别为 2|G 1 | 和 |G 1 |+|Z |. SM9-PAEKS 中关键词陷门长度为 |G 2 |, Qin 等人 [17] 的方案为
N
|G 1 |, 而 Huang 等人 [15] 的方案为 |G T |. 此外, 表 1 还列出了各个方案安全性所依赖的安全假设.