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

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

q 1/a
a Q), 其目标是计算 e(P,Q) , C 与 A 的具体交互过程如下.
● 初始化阶段. C 随机选取 k ∈ [1,q],B k ∈ Z , 然后选取 q−1 个不同的随机数 t 1 ,t 2 ,...,t k−1 , t k+1 ,...,t q ∈ Z ∗ N 对于
∗

N
q q−1
∏ ∑
i
∀i ∈ [1,q]\{k}, 计算 B i = B k −t i , 同时生成如下多项式 f(x) = (x+t i ) = c i x , 随后根据困难问题实例设置 SM9-
i=1,i,k i=0
q−1 q
∑ ∑
i
i
PAEKS 方案中的系统参数, P 2 = f(a)Q = c i (a Q),P 1 = ψ(P 2 ) = f(a)P, 设置发送方的公钥为 pk S = c i−1 (a Q) = aP 2 ,
i=0 q−2 i=1 q−2
f(x) ∑ ∑
i
i
上述过程中的 a 是未知的, 并且 ψ(Q) = P. 对于任意 i ∈ [1,q]\{k}, 令 f i (x) = = d i x , 可计算 U i = d i (a Q) =
a+t i
i=0 i=0
f(a) P 2
f i (a)Q = Q = , 即对于任意的二元组 (t i ,U i ),i ∈ [1,q]\{k} 都是可计算的. 随后计算 pk R = −pk S − B k P 1 =
a+t i a+t i
−(a+ B k )P 1 , 上述过程中隐式地设置了 sk S = y = a, sk R = x = −(a+ B k ). 然后, 选取一字节表示的私钥生成函数标识
符 hid. 最后, 返回系统参数 params = (P 1 ,P 2 ,g,N,hid).
● 哈希询问阶段. 此阶段, A 可适应性地选取关键词 w i ∈ {0,1} 向 C 进行如下两类哈希询问.
∗
(1) H 1 询问: 为响应 A 的询问, C 维持列表 L 1 =< w i ,V i ,B i >, 如果询问项 < w i ,V i > 存在列表 L 1 中, 则按照列表
i
中记录的 B i 响应. 否则, 记 w i 是第 个新关键词的询问. 设 H 1 (w i ||hid||V i ,N) = B i , 最终返回 B 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 1 (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
生成关键词对应的表项, 由于是 C 生成的表项, 其无法计算出 V i = [xy]P 1 , 因此记 V i = ⋆. 如果 i = k, 输出失败. 否则
∗ , 随后按照 PAEKS = C 1 ||C 3 ||C 2 并返
C 选取随机数 r i ∈ Z , 计算 Q w i = [t i ]P 1 + pk R ,C 1 = r i Q w i 算法生成关键词密文 C w i
N
回给 A. 与 SM9-PAEKS 方案中的关键词密文相比可知, O C w 响应的关键词密文与真实方案中的关键词密文是不
可区分的.
(2) 关键词陷门询问 : 首先 C 查询 A 询问的关键词是否在列表 L 1 中, 如果不存在, 则按照 H 1 询问阶段生
O T w
成关键词对应的表项, 由于是 C 生成的表项, 因此其无法计算出 V i = [xy]P 2 , 故记 V i = ⋆. 如果 i = k, 输出失败. 否则
( ) ( )
1 B i
C 可 根 据 初 始 化 阶 段 的 B i = B k −t i , 计 算 B i , P 2 , 进 而 C 可 计 算 元 组 (B i ,P 2 − B i U i ) = B i ,P 2 − P 2 =

x+ B i x+ B i
( )
x x
B i , P 2 . 最终, C 返回关键词陷门 T w i = P 2 . 分析 SM9-PAEKS 方案中的关键词陷门形式和谕言机 O T w
x+ B i B i + x
响应的形式可知, 从 A 的角度而言, 是不可区分的.

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

∗
∗
0
1
1
0
t ∗
∗
,
∗ ∗ ∗ ∗ klen ∗ ∗ r = , 由于系统设置阶段隐
w , w k C 终止此次模拟, 否则选取随机数 t ∈ Z ,K ∈ {0,1} , 计算 C = −t P 1 , 若设
b N 1 a
∗
∗
∗
∗
式地设置了 x = −a− B k , 有 C = −t P 1 = −r aP 1 = r (B k P 1 + pk R ). 随后, 按照 SM9-PAEKS 方案中的 PAEKS 算法生

1
∗ ∗ ∗ ∗ ∗ A 的角度而言, 挑战密文和真实密文是不可区分的, 即上述模拟过程
成 C ,C . 最后返回关键词密文 C ||C ||C . 从
2 3 1 3 2
∗
和真正的方案攻击不可区分. 除非 A 询问过关于 u = e(pk R ,P 2 ) r∗ 的值.
● 询问阶段 2. 在此阶段, A 可继续进行同询问阶段 1 的询问, 但是此处限制 A 询问的关键词 w i < {w 0 ,w 1 }.
● 猜测阶段. A 输出对挑战关键词密文中关键词的猜测, 若猜测正确 A 赢得上述游戏, 否则失败. C 可忽略 A
∗
的猜测, 从 L 2 中选择元组 < C 1 ,u,K i >, 选择的元组包含 u 的概率为 1/q H 2 . 由于 A 不可区分上述模拟与真实方案,
∗
那么其将以不可忽略的优势询问 H 2 关于 u 的值.
根据上述分析, C 可通过如下方式解决困难问题实例:

∗ r ∗ t ∗
u =e(pk R ,P 2 ) = e(f(a)(−a− B k )P, f(a)Q) a
− f 2 (a)at ∗ − f 2 (a)t ∗ B k
=e(P,Q) a
f 2 (a)t ∗ B k
=e(P,Q) − f 2 (a)t ∗ − a (7)