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

蒲浪 等: 基于国密 SM9 的公钥认证可搜索加密方案 4279

∗
由于其中 f(a),t ,B k 都是已知的, 则有:

  q−1 
 ∑ 
  
 2 ∗  i ∗
 f (a)t =   
 c i a  f(a)t
  


 i=0
 (8)
    
 q−2 q−2 q−2
 f (a)t ∑ c 0     c 0 t  
 2 ∗ ∑ ∑ 2 ∗


  i  ∗ ∗ i  ∗ i 
 c i+1 a +  f(a)t = f(a)t · c i+1 a +  t c i+1 a + 
 =    c 0 
    
 a a a
i=0 i=0 i=0
∗
因此, 上述 u 可进一步表示为:

q−2 q−2 c 2
∑
−B k ·( f(a)t ∗ · c i+1 a i +c 0 t ∗ ∑ c i+1 a i + 0 t ∗ )
∗
u =e(−t P 1 , f(a)Q)·e(P,Q) i=0 i=0 a
∗
q−2
∑ −B k c 2 t ∗
−1
−1
i
=e(t P 1 , f(a)Q) ·e(B k t (P 1 +c 0 P), c i+1 a Q) ·e(P,Q) a 0 (9)
∗
∗
i=0
可计算 q -BDHI 问题的解为:

q−2
∑ −1
1 i
∗
e(P,Q) a = (u ·e(t P 1 , f(a)Q)·e(B k t (P 1 +c 0 P), c i+1 a Q)) B k c 2 t ∗ (10)
∗
∗
0
i=0
∗ A 能以不可忽略的
概率分析: 根据上述证明过程有 w = w k , 即 A 选择 w k 作为挑战关键词的概率为 1/q H 1 . 若
b
优势 ϵ 1 攻破 SM9-PAEKS 方案的 CKA-CI 安全性, 则 C 解决 q -BDHI 困难问题的优势为:

1 1
q-BDHI ϵ 1
Adv ⩾ ϵ 1 · · = (11)
C
q H 1 q H 2 q H 1 q H 2
引理 1 证毕.
引理 2. 若 Gap-q-BCAA1 安全假设成立, 那么 SM9-PAEKS 具备 CKA-TI 安全性.
证明: 假设存在 PPT 敌手 A 能以不可忽略的优势攻破 SM9-PAEKS 方案的 CKA-TI 安全性. 则挑战者 C
(
A 交互, 以不可忽略的优势解决 q -BCAA1 困难问题实例. P 1 ,P 2 ,[x]P 1 ,t 0 ,
可通过与 Gap- C 输入困难问题实例
( [ ] ) ( [ ] ))
x x
x
t 1 , P 2 ,..., t q , P 2 , 其中 t i ∈ Z ,i ∈ [0,q] C 可查询 DBIDH 谕言机 O DBIDH , 其目标是计算 e(P 1 ,P 2 ) x+t 0 ,
.
∗
N
x+t 1 x+t q
C 与 A 的具体交互过程如下.
● 初始化阶段. C 根据 SM9-PAEKS 及困难问题实例设置系统参数 (G 1 ,G 2 ,G T ,e,P 1 ,P 2 ), 令接收方公钥为
∗ hid.
pk R = [x]P 1 , 随机选取 y ∈ Z , 计算发送方公钥为 pk S = [y]P 1 . 然后, 选取一字节表示的私钥生成函数标识符为
N
最后, 返回系统公开参数.
● 哈希询问阶段. 此阶段, A 可适应性地选取关键词 w i ∈ {0,1} 向 C 进行如下两类哈希询问.
∗
(1) H 1 询问. 为响应 A 的询问, C 维持列表 L 1 =< w i ,V i ,t i ,T i >, 如果询问项 < w i ,V i > 存在列表 L 1 中, 则按照列
k ∈ [1,q+1],
表中记录的 h i 响应. 否则, 记 w i 是第 i 个新关键词的询问. 设 H 1 (w i ||hid||V i ,N) = t i , 最终返回 t i 并更新 L 1 . 令
[ ]
x
若为 w k 则记录 T k = ⊥, 否则记录每次的 T i = P 2.
x+t i
(2) H 2 询问. 针对 A 发起的关于元组 < C i ,u i > 的询问, C 维持列表 L 2 =< C i ,u i ,K i >, 如果询问项 < C i ,u i > 存在
列表 L 2 中, 则按照列表中记录的 K i 响应. 否则, C 随机选取 K i , 并设 H 2 (C i ||u i , klen) = K i , 同时更新 L 2 .

● 询问阶段 1. 此阶段, A 可适应性地选取关键词 w i ∈ {0,1} 并向 C 进行如下两种询问.
∗
(1) 关键词密文询问 . 首先 C 查询 A 询问的关键词 w i 是否在列表 L 1 中, 如果不存在, 则按照 H 1 询问阶段
O C w
∗ , 并按照
生成关键词对应的表项. 如果 i = k, 终止游戏. 否则 C 选取随机数 r i ∈ Z , 计算 Q w i = [t i ]P 1 + pk R , C 1 = r i Q w i
N
PAEKS 算法生成关键词密文 C w i = C 1 ||C 3 ||C 2 并返回给 A. 与 SM9-PAEKS 方案中的关键词密文相比可知, O C w 响
应的关键词密文与真实方案中的关键词密文是不可区分的.
(2) 关键词陷门询问 O T w . 首先 C 查询 A 询问的关键词是否在列表 L 1 中, 如果不存在, 则按照 H 1 询问阶段生成
[ ]
x
关键词对应的表项. 如果 i = k, 输出失败 (记作事件 E 1 ). 否则, C 可将 L 1 中记录的 T i = P 2 作为关键词陷门返
x+t i