Page 270 - 《软件学报》2020年第10期

3246 Journal of Software 软件学报 Vol.31, No.10, October 2020

戏 G 2 与在游戏 G 1 中的优势差是可忽略的,即
| Adv A 2 ( ) − Adv 1 ( ) |≤A 2q exe ⋅ Adv CPA (t O+ (q send +q exe )) (4)
PKE′
其中,式(4)考虑到了 CPA 攻击者在模拟协议运行时,只有在模拟 Send 和 Execute 类预言时才需要进行额外
的计算,在模拟 Reveal 和 Corrupt 询问时只需要返回对应状态,从而其计算时间至多为 t+O(q send +q exe ).
游戏 G 3 :在模拟 Execute 询问时,我们将 tk U || mk U =Hash (hk L U ,c U ),U ∈ { , }A B 替换成随机选择的等长比特
,
U
串.由于游戏 G 2 已将 c US 替换成 P 0 的密文,从而有 c ∉ L A ,c ∉ L B , 根据平滑投射哈希函数的平滑性质,可知攻
US
US
击者在游戏 G 3 与在游戏 G 2 中的优势差可忽略,即记 ε SPHF (k)为平滑投射哈希函数在输入非语言元素时的输出
哈希值与均匀分布之间的统计距离的一个可忽略的上界,则有
| Adv A 3 ( ) − Adv 2 ( ) |≤A 2q exe ε ⋅ SPHF ( )k (5)
游戏 G 4 :在模拟 Execute 询问时,我们将 c = SA Enc (pk M A ; ;l tk A ),c SB = Enc (pk M B ; ;l tk B ) 中的 M A 和 M B 替换
,
,
B
A
成 M = A s A || H 0, A ,M = B s B || H 0,B , 其中, H 0,A = s π A 0 ,H 0,B = s π 0 是对应于不属于字典的一个虚拟口令 π ∉ . D 由于
B
0
tk A 和 tk B 在游戏 G 3 中已被替换成完全随机的比特串,因此根据加密体制 PKE = (KG Enc Dec 的 CCA 安全性,
,
,
)
可知攻击者在游戏 G 4 与在游戏 G 3 中的优势差是可忽略的,因此,
| Adv A ( ) − Adv ( ) |≤A 2q ⋅ Adv CCA (t O+ (q +q )) (6)
4 3 exe PKE send exe
需要说明的是,在游戏 G 4 中并没有询问加密体制 PKE 的解密预言,从而实际上只用到了 PKE 体制的 CPA
安全性.但是,在下面的游戏 G 10 中需要询问解密预言,因此需要 PKE 是 CCA 安全的.
游戏 G 5 :在模拟 Execute 询问时,我们直接将最终的会话密钥 sk AB =sk BA 替换成随机值.利用 DDH 自规约技
术,我们证明攻击者在实验 G 4 和 G 5 中的优势差至多为攻击者区分 DDH 三元组的优势.给定 DDH 三元组(X 0 ,Y 0 ,
a
Z 0 ),当用户 A 需要生成消息 X和 σ 时 ,我们选择随机的 ,ax∈Z , 并计算 X = Xg x , 当用户 B 需要生成消息
AS p 0
ya
xb
ab
b
Y和 σ 时 ,选择随机的 ,by ∈Z , 并计算 Y = Y g y , 当双方需要生成密钥时,计算 sk = sk = Z Y X g xy . 可以
BS p 0 AB BA 0
看出,当三元组(X 0 ,Y 0 ,Z 0 )满足 Z = DH (X , )Y 时,上述游戏和游戏 G 4 完全一样;当 Z ≠ DH (X , )Y 时,上述游戏
0 0 0 0 0 0
和游戏 G 5 是一样的.在 DDH 问题困难假设下,可知
| Adv A 5 ( ) − Adv 4 ( ) |≤A 2 Adv⋅ ddh (t O+ (q send +q exe )) (7)
G
至此,我们已将 Execute 模拟中的与口令相关的消息和会话密钥替换成为随机值,从而攻击者不能从中获得
i
用户口令的信息.下面将开始修改对敌手主动攻击类询问的模拟.为了表述简单,下面用 SendClient 0 (U )表示攻
i
i
,
),
击者激活用户的初始消息, SendClient (U m d ∈ { 2,4} 表示在第 d 轮通信中给用户会话 U 发送消息 m,
d
j
j
, ),
SendServer d (S m d ∈ {1,3}表示在第 d 轮通信中给服务器会话 S 发送消息 m.在公开参数产生阶段,我们还让模
拟者记录对应于公钥 pk′和 pk 的私钥 sk′和 sk.
游戏 G 6 :本游戏修改针对用户 A 的 SendClientA i , hp〈 1A ,hp 2A ,c SA ) 〉 的回答方式,对用户 B 按照类似的方式进
(
2
行处理(下同).先检查〈hp 1A ,hp 2A ,c SA 〉是否来源于某个诚实模拟的 SendServer (S j ,*) 的回复,如果答案是否定,则直
1
接解密 c SA 得到 s′ H′ 和 并检查与用户 A 的口令 π A 是否匹配.若成立 ()s′ F π ) = H , ′ 则直接认为攻击者 A 攻击成
( A
A A A A
i
功并结束模拟.如果验证不通过,则让 A 拒绝该消息并结束该会话的模拟.容易看出,上述修改增加了攻击者成
功的途径,因此有 Adv 5 ()≤A Adv 6 ().A
游戏 G 7 :本游戏继续修改针对用户 A 的询问 SendClientA i , hp〈 1A ,hp 2A ,c SA ) 〉 响应的模拟.若消息〈hp 1A ,hp 2A ,
(
2
i
c SA 〉确实来源于某个诚实模拟的 SendServer 1 (S j ,*) 的回复,则不再按照协议规范为 A 计算 tk A || mk ,而是直接将
A
i
j
i
j
A 中的 tk A || mk 设置成与 S 中一样的值.此时,由于会话 A 和 S 都是诚实模拟的,故上述修改并不改变攻击者的
A
优势,即 Adv 6 ()=AdvA 7 ().A
i
(
游戏 G 8 :本游戏修改针对用户的激活消息 SendClient A 响应的模拟方式.类似于游戏 G 2 ,我们将其中的
)
0
c AS = (u = A g A r ,e = A h ⋅ A r P A ) 替换成虚拟口令所对应的 P 0 的密文.由于加密体制 PKE′是 CPA 安全的,从而攻击者
在游戏 G 8 与在游戏 G 7 中的优势差是可忽略的,即