云存储由于其低成本、具有无限数据存储空间的特点，已受到广泛重视和应用.用户可以将大量数据存储在云服务器上.但是云服务器并不完全可信，为了保证用户数据的安全，用户的敏感数据通常需要加密后再存储在云服务器上.但是在传统的密文存储和查询服务中，由于云服务器没有检索功能，不能根据用户需求查找数据.带关键词搜索的公钥加密体制解决了在云服务器不可信的条件下加密数据检索的问题.其主要思想是：发送者首先分别加密数据和关键词上传至云服务器；然后接收者发送一个由关键词生成的陷门给云服务器；最后云服务器执行关键词密文和陷门的匹配算法.云服务器判断密文和陷门是否包含相同的关键字，若是则将密文数据发送给接收方，此过程云服务器不能获得关键词和明文数据的任何信息.
Boneh等人[1]在2004年首次提出了带关键词搜索的公钥加密方案(public key encryption with keyword search， PEKS)(下文中的公钥加密算法记为PEKS)，该方案是通过基于身份的加密方案(identity-based encryption， IBE)[2]所构造，其基本思想是：将PEKS中的关键词w替代IBE中用户的身份ID，将PEKS中接收者给服务器的陷门替代IBE用户的私钥，所以要求基于身份的加密方案必须具有匿名性才能转换成带关键词搜索的公钥加密方案.文献[1]在接收者给云服务器传输陷门时，需要安全信道，导致昂贵的开销，而且方案的安全性是在随机预言模型(random oracle model， RO)下进行证明的.Baek等人[3]提出了无安全信道的可搜索加密方案(secure channel free PEKS， SCF-PEKS)，其方法是通过引入云服务器的公私钥对来消除安全信道，只有指定的服务器才能够对关键词密文与陷门进行匹配.但是其方案也是在随机预言模型下进行的安全性证明，而且在安全性证明中当云服务器为攻击者时，云服务器的公私钥对却由模拟器来产生，这样不符合实际要求，因为在公钥加密体制中，公私钥对应该由自己产生，而不应该由第三方产生.此后Rhee等人[4-5]加强了Baek等人的安全模型，即攻击者的公私钥对由其自己产生，这样符合实际情况，并提出了一系列指定检验者的关键词搜索方案(designated tester PEKS， dPEKS)，但是这些方案也是在随机预言模型下可证明安全且不能抵制选择密文攻击.Fang等人[6]利用Gentry[7]的基于身份加密方案构造了标准模型下的带关键词搜索方案.随后在文献[8]中，通过引入一次性强签名方案，能够抵制选择关键词和密文攻击.但文献[8]在安全性证明中，敌手的公私钥对也是由模拟器来产生.
2006年Byun等人[9]首次提出外部的离线关键词猜测攻击(resist external keyword guessing attack, REKGA)的概念，并对文献[1，10]的PEKS方案进行了离线关键词猜测攻击;Jeong等人[11]指出:满足一致性的PEKS方案一定不能够抵制关键词猜测攻击;在文献[12]的安全性证明中，指出仅当敌手能得到陷门且自己能进行验证的前提下，该结论才成立，所以得出满足一致性的PEKS方案一定不能够抵制内部关键词猜测攻击，因为对于服务器来说，既能得到陷门又能自己进行陷门和关键词密文的匹配验证;Rhee等人[4]提出了陷门不可区分性的概念，并证明陷门不可区分性是抵抗外部关键词猜测攻击的充分条件，并提出了一个具体的方案抵制外部离线关键词猜测攻击;Guo等人[13]和Fang等人[8]构造出一个可抵抗外部敌手进行关键词猜测攻击的方案，并在标准模型下证明方案的安全性，但文献[8，13]都不能抵制内部服务器进行离线关键词猜测攻击.
2013年Yau等人[14]提出文献[12]不能抵制内部离线关键词猜测攻击，即当服务器是攻击者的情况下的攻击，其基本思路是服务器自己猜测一些关键词，然后进行加密，由于服务器能够得到陷门并且通过陷门进行检验，从而得出陷门包含了哪个关键词;文献[14]指出:相似于文献[12]的PEKS方案构造都不能抵制上述攻击,文献[14]还提出了一种在线关键字猜测攻击类型(online keyword guessing attack， OKGA)，这种类型的敌手是一个外部攻击者，敌手可以对所有可能的关键词w都配对一个虚假的明文数据m′，并将它们加密上传至云服务器，并对服务器和目标接收者的通信进行监听.一旦服务器将包含明文数据m′的加密文档发送给接收者，攻击者会知道接收者的陷门包含哪个关键词.
为了抵制内部(即服务器)离线关键词猜测攻击，Shao等人[15]在Fang等人[8]的基础上引入了发送者的身份，通过确定性RSA算法对发送者身份进行签名，当服务器自己产生关键词密文时，却不能进行匹配测试.文献[15]声称其方案能够抵抗内部关键词猜测攻击，但文献[16]指出，该方案中的服务器必须诚实地进行测试，但事实上，服务器可以是恶意的，同时Lu等人[16]指出文献[8]不能抵制外部离线关键词猜测攻击，但服务器必须提供在线服务.文献[16]在文献[8]的基础上提出一个能抵制内部离线关键词猜测攻击的PEKS方案，而且该方案在标准模型下可抵制选择密文攻击.2017年Huang等人[17]在对关键词加密时引入发送者的私钥，实现公钥认证加密功能，从而抵制内部离线关键词猜测攻击，但是这个方案的陷门是固定的，且被指出不满足密文不可区分性[18].Li等人[19]引入了权威机构对用户进行授权认证，并产生对应的身份私钥，随后用户用其私钥对关键词密文进行认证加密，但该方案仍旧是在随机预言模型下进行的安全性证明.Lu等人[20]采用签密的思想来抵制内部离线关键词猜测攻击，即在产生关键词密文的过程中，使用发送者的私钥，由于除了发送者，任何人不知道发送者的私钥，敌手不能产生合法的关键词密文来匹配任何关键词陷门.这种构造方式的局限性是，当接收者产生关键词陷门时，必须要涉及到发送者的公钥或身份，所以相当于接收者事先委派了发送者，这样会影响实际使用效果.使用这种技巧使得方案抵制内部关键词猜测攻击有文献[17-22].文献[23]通过将密文随机化来抵制外部在线和离线关键词猜测攻击.文献[20]指出构造具有任何搜索功能，而不受接收者委派，但是还能够抵制各种关键词猜测攻击的PEKS方案是一个公开问题.
最近文献[24]阐述了基于对称密码学和基于公钥密码学而构造的可搜索加密机制的不同特点，分析了可搜索加密机制在支持单词搜索、连接关键词搜索和复杂逻辑结构搜索语句的研究进展;文献[25]首先介绍了关于可搜索加密的理论研究进展情况，最后指出了关于可搜索加密应用的公开问题和未来发展趋势;文献[26-28]都对可搜索加密进行了综述性的总结，文献[27]提出一种多用户的可搜索方案，用户按照自己的意愿设置访问权限，不需要1个可信的用户搜索中心，弱化了可信第三方的功能.
综上所述，从6个方面对PEKS的安全模型进行总结：
1) 陷门是否通过公开信道传输.通过引入服务器的公私钥对，使得在检验中必须使用服务器的私钥才能检验，从而使得陷门可以在公开信道传输.
2) 是否在标准模型下进行安全性证明.因为随机预言模型下进行的安全性证明只是一种启发式证明，所以在标准模型下可证明方案的安全性是加密方案证明的终极目标.
3) 是否抵制适应性选择关键词攻击.从2方面考虑：敌手为恶意的服务器或恶意的接收者.
4) 是否抵制关键字猜测攻击.从3种情况考虑：外部离线关键词猜测攻击、外部在线关键词猜测攻击、内部离线关键词猜测攻击.
5) 在安全性证明中，敌手的私钥是否必须由挑战者来产生.实际情况是敌手自己产生私钥，但在很多方案中，由于模拟器要利用敌手的私钥，所以敌手的私钥由模拟器来产生，不符合实际情况.
6) 是否抵制适应性选择密文攻击.已有的方案通过引入一次性强不可伪造签名方案抵制适应性选择关键词攻击.这样使得所构造的方案效率较低.通过直接构造来抵制适应性选择关键词攻击成为公开问题.
表1进行了总结，指出目前构造的一些PEKS方案满足哪些安全性要求，其中一些安全性要求缩写为：抵抗选择关键词攻击(resist chosen keyword attack， RCKA)，分2种情况，攻击者为服务器(server)或接收者(receiver)，抵制选择密文攻击(resist chosen ciphertext attack， RCCA)、抵制外部关键词猜测攻击(resist external keyword guessing attack， REKGA)、抵制内部关键词猜测攻击(resist internal keyword guessing attack， RIKGA)、认证功能(authentication Function， AF)、抵制在线关键字猜测攻击(resist online keyword guessing attack，ROKGA).
Table 1 Performance Comparison of Security Model of PEKS
表1 PEKS安全模型的性能对比
SchemePublicChannelStandardModelRCKAServerReceiverRCCAREKGARIKGAAdverary Generate Its Secret KeyWithoutAFROKGARef [1]×××××√×Ref [3]√×√√××××√×Ref [4-5,12]√×√√×√×√√×Ref [6]√√√√×××√√×Ref [8]√√√√√√××√×Ref [10]×××××√×Ref [13]√√√√√√×√√×Ref [15]√√√√√√×√××Ref [16]√√√√√√√√×√Ref [17]××√×√√××√Ref [22]√√√√√√√×√Ref [23]×√√√√√××√Ref [24]√√√√√
Note: √ means that the requirement is met; × means that the requirement is not met.
针对上述问题，本文的主要贡献有3个方面：
1) 提出一种能够抵制内部关键词猜测攻击的带关键搜索的公钥加密方案.目前使用的技巧是通过发送者在加密的同时使用了数字签名，这样使得内部攻击者即服务器不能够产生关键词密文，从而抵制了内部关键词猜测攻击，相当于接收者事先需要指定密文的发送者.但是在很多实际情况下，接收者不知道发送者是谁.本文通过引入发送者和服务器的身份，并将其放在方案中算式的分母上，使得服务器无法自己产生关键词密文，从而抵制内部关键词猜测攻击.
2) 由于关键词密文能够进行公开验证其正确性，本文构造的方案能够抵制适应性选择密文攻击，而且所构造的方案没有使用额外的一次性强不可伪造签名，从而方案的效率很高.
3) 本文的陷门是在公开信道传输，而且能够抵制适应性选择关键词攻击，且方案是在标准模型下可证明安全.
1 基础知识
1.1 双线性对
记G1=
g
表示由生成元g生成的有限群G1.输入安全参数k，输出双线性映射的参数(p,g,G1,G2,e)，其中G1和G2是阶为素数p的循环群，g是G1的生成元，映射e:G1×G1→G2具有3个性质：
1) 双线性.对于任意的g∈G1和a,b∈Z
有e(ga,gb)=e(g,g)ab.
2) 非退化性.对G1的生成元g，有e(g,g)≠1.
3) 可计算性.对于任意的g,h∈G1，存在多项式时间算法计算e(g,h).
1.2 相关的困难问题
1) 商判定双线性Diffie-Hellman(QDBDH)假设.
设e:G1×G1→G2是一个双线性映射，我们定义敌手
的优势函数：
其中,a,b∈Z
如果对于所有多项式时间敌手
可忽略，我们称商判定双线性QDBDH假设成立.
2) 判定双线性Diffie-Hellman(DBDH)假设.
设e:G1×G1→G2是一个双线性映射，我们定义敌手的优势函数：
其中,a,b,c∈Z如果对于所有多项式时间敌手
可忽略，我们称判定双线性DBDH假设成立.
3) Hash Diffie-Hellman(HDH)假设.
设hLen是一个整数且H:{0,1}*→{0,1}hLen是一个Hash函数.G1中HDH问题定义为：
作为输入，若ab=c，输出“yes”；否则，输出“no”.若:
b←Z
η←{0,1}hLen,a,b←Z
没有多项式时间算法至少以优势ε在G1中解决HDH问题，我们称HDH假设在G1中成立.
2 SCF-PEKS模型
2.1 SCF-PEKS系统模型
本节我们介绍SCF-PEKS模型，它是一个不需要接收者与服务器建立安全信道的带关键词搜索加密模型，系统中包含4个实体，即系统参数生成中心(system parameter generation center， SPGC)、数据发送者(data sender， DS)、数据接收者(data receiver， DR)、云服务器(cloud server， CS)，系统模型如图1所示：
Fig. 1 System model of PEKS
图1 PEKS系统模型
1) 系统参数生成中心
系统参数生成中心是系统中唯一的可信第三方，运行Setup算法产生系统的公开参数，并把公开参数发送给系统中的其他实体.
2) 数据发送者
数据发送者收到公开参数之后，运行PEKS算法，对明文数据和关键词加密并上传至云服务器.
3) 数据接收者
数据接收者运行KeyGenR算法产生自己的公私钥，运行dTrapdoor算法生成关键词对应的陷门，并上传至云服务器.
4) 云服务器
云服务器是一个诚实且好奇的实体，运行KeyGenS算法产生自己的公私钥，运行是dTest算法为接收者提供搜索服务.
5) 云服务器
云服务器最后把搜索的结果返回给数据接收者.
2.2 SCF-PEKS算法定义
我们的算法只关注关键词加密部分，具体为：
1) Setup(1k).该算法由系统参数生成中心执行，输入安全参数1k，输出公开参数params.
2) KeyGenR(params).该算法由数据接收者执行，输入公开参数params，输出他的公私钥对(pkR,skR).
3) KeyGenS(params).该算法由云服务器执行，输入公开参数params，输出他的公私钥对((pkS,skS)).
4) PEKS(params,pkR,pkS,IDsender,w).该算法由数据发送者执行，输入公开参数params、接收者的公钥pkR、服务器的公钥pkS、发送者的身份IDsender、关键词w，输出关键词的密文CT.
5) dTrapdoor(params,pkS,skR,IDserver,w).算法由数据接收者执行，输入公开参数params、接收者的私钥skR、服务器的公钥pkS、服务器的身份IDserver、关键词w，输出关键词的陷门Tw.
6) dTest(params,CT,Tw,skS,pkR,IDsender,IDserver).该算法由云服务器执行，输入关键词的密文CT和陷门Tw、接收者的公钥pkR、服务器的私钥skS、发送者的身份IDsender、服务器的身份IDserver，输出是否匹配成功.
2.3 SCF-PEKS安全模型
游戏1. 假设敌手
是一个诚实且好奇的云服务器，所谓诚实且好奇为，按正常步骤执行算法，但还想通过一些手段得到关键词.
1) 系统建立.模拟者
产生公开参数params并将(params,pkR,pkS,skS)发送给敌手
2) 询问阶段1.敌手进行以下一系列询问.
① 陷门预言询问
可以适应性地询问模拟者任何关键词对应的陷门，回应陷门dTrapdoor(params,pkS,skR,IDserver,w)给
② 测试预言询问
对任意的关键词w和SCF-PEKS密文CT进行测试询问.模拟者首先询问关键词w的陷门Tw，然后回复dTest(params,CT,Tw,skS,pkR,IDsender,IDserver)给
3) 挑战阶段.敌手输出2个想要挑战的关键词(w0,w1)，且这2个关键词不能在询问阶段1中被询问过.模拟者回复如下：随机选择δ∈{0,1}，然后回复PEKS(params,pkR,pkS,IDsender,wδ)给
4) 询问阶段2.敌手继续像询问阶段1一样进行询问.
5) 猜测.最终敌手
输出他的猜测δ′∈{0,1}.
游戏2. 假设敌手
是一个外部敌手(包括接收者).
1) 系统建立.模拟者产生公开参数params并将(params,pkS,pkR,skR)发送给敌手
2) 询问阶段1.敌手进行测试预言询问.
测试预言询问
对任意的关键词w和SCF-PEKS密文CT进行测试询问.模拟者首先询问关键词w的陷门Tw，然后回复dTest(params,CT,Tw,skS,pkR,IDsender,IDserver)给
3) 挑战阶段.敌手输出2个想要挑战的关键词(w0,w1)，且这2个关键词不能在询问阶段1中被询问过.模拟者回复如下：随机选择δ∈{0,1}，然后回复
4) 询问阶段2.敌手继续像询问阶段1一样进行询问.
5) 猜测.最终敌手
输出他的猜测δ′∈{0,1}.
游戏3. 假设敌手
是一个外部敌手.
1) 系统建立.模拟者产生公开参数params并将(params,pkS,pkR)发送给敌手
2) 询问阶段1.敌手进行测试预言询问.
陷门预言询问
可以适应性地询问模拟者任何关键词w对应的陷门，回应陷门dTrapdoor(params,pkS,skR,IDserver,w)给
3) 挑战阶段.敌手输出2个想要挑战的关键词(w0,w1)，且这2个关键词不能在询问阶段1中被询问过.模拟者回复如下：随机选择δ∈{0,1}，然后回复PEKS(params,pkR,pkS,IDsender,wδ)给
4) 询问阶段2.敌手继续像询问阶段1一样进行询问.
5) 猜测.最终敌手
输出他的猜测δ′∈{0,1}.
3 SCF-PEKS方案
3.1 SCF-PEKS方案的构造
本节提出了一个不仅可以抵抗内部关键词猜测攻击而且能够抵抗适应性选择关键词密文攻击的方案，具体算法为：
1) Setup(1k).输入安全参数1k和双线性映射参数(p,g,G1,G2,e,)，g1,u,v,d,h是G1中随机的生成元，H:G1→G1,H1:G2→{0,1}k,H2:G1×G2×{0,1}k→Z
是3个碰撞稳定的Hash函数.输出公开参数params=(p,g,G1,G2,e,g1,u,v,d,h,H,H1,H2).
2) KeyGenR(params).输入公开参数params，接收者随机选择xR∈Z作为私钥skR，且设置公钥pkR=gxR.
3) KeyGenS(params).输入公开参数params，服务器随机选择xS∈Z作为私钥skS，且设置公钥pkS=gxS.
4) PEKS(params,pkR,pkS,IDsender,w).输入公开参数params，接收者的公钥pkR，服务器的公钥pkS，发送者的身份IDsender，关键字w，发送者计算关键词的密文为：
① 随机选取r∈Z计算
② 随机选取s′∈Z计算h′=H2(C1,C2,C3)和C4=(uh′vs′d)r，其中s′是一个Z的一个随机值.
③ 输出关键词密文CT=(s′,C1,C2,C3,C4)并发送给服务器.
5) dTrapdoor(params,pkS,skR,IDserver,w).输入公开参数params，接收者的私钥skR=xR，服务器的公钥pkS，服务器的身份IDserver，关键字w，接收者随机选取r′∈Z并计算
输出关键词的陷门Tw=(T1,T2)并发送给服务器.
6)dTest(params,CT,Tw,skS,pkR,IDsender,IDserver).该算法由云服务器执行，输入关键词的密文CT和陷门Tw，接收者的公钥pkR，服务器的私钥skS=xS，发送者的身份IDsender，服务器的身份IDserver.服务器首先计算h′=H2(C1,C2,C3)，判断e(C1,(uh′vs′d))=e(pkR,C4)是否相等.若不相等则匹配失败，终止该算法.
否则继续计算
判断H1[(e(C1,TxS)
C2)1(IDserver-IDsender)]=C3是否相等，如果相等则匹配成功，否则匹配失败.此时，发送者和服务器一定不能是同一个身份，如果是则无法通过验证.
3.2 计算正确性与一致性分析
1) 正确性.正确的关键词密文CT必须与正确关键词陷门Tw匹配，服务器才能测试成功.在dTest算法中，有：
因此:
dTest(params,CT,Tw,skS,pkR,
IDsender,IDserver)=“yes”.
2) 一致性.一致性保证了由关键词w生成的密文CT和由关键词w′生成的陷门Tw′，以很高的概率不能匹配成功.令r,r′是SCF-PEKS方案中正确的随机数，C1,C2,C3是由关键词w生成的正确的部分密文，
是由关键词w′生成的正确的陷门,则有：
H1[(e(C1,T′xS)C2)1(IDserver-IDsender)]=C3⟺
因为
且H1是一个碰撞稳定的Hash函数，所以有很高的概率，使得:
H1[(e(C1,T′xS)C2)1(IDserver-IDsender)]≠C3.
4 SCF-PEKS安全性分析
定理1. 假设QDBDH和DBDH问题是困难问题，我们的方案在标准模型下是可证明安全的.
引理1. 假设QDBDH问题是困难问题，我们的方案在标准模型下能够抵抗选择关键词和密文攻击(chosen keyword and ciphertext attack， CKCA).
证明. 假设敌手是一个诚实且好奇的云服务器，他最多进行qTw次陷门询问，且以ε的优势攻击所提出的SCF-PEKS方案. H,H1,H2是碰撞稳定的Hash函数.构造模拟者能以ε′的优势解决QDBDH问题，其中：
是H1碰撞的优势).模拟者输入一个QDBDH实例(g,A=ga,B=gb,Q)，其中a,b∈Z
，目的是判断e(g,g)ba=Q是否相等.
1) 系统建立.模拟者选取xu,xv,α0,β,α1,α2,α3∈Z设置g1=Bα0,h=Bβ,u=gxuAα1,v=gxvAα2,d=Aα3.接着使用Corons技巧[29]，随机选取xR∈Z掷币ci∈{0,1}，使得Pr[ci=1]=θ，Pr[ci=0]=1-θ(这里的θ是一个与询问查询OTw次数有关的值，其最优值见下面定义).如果ci=1，令pkR=gxR，否则令pkR=AxR，再将三元组(pkR,xR,ci)加入LList列表(该列表最初设置为空).产生服务器的公私钥对(pkS,skS)，最后将(pkR,pkS,skS)发送给敌手
2) 询问阶段1.敌手进行以下一系列询问.
① 陷门预言询问对关键词wi进行陷门询问，模拟者随机选择r∈Z
如果wi对应的LList列表中，ci=1，此时skR=xR，模拟者计算
并将Twi=(T1,T2)作为结果输出.如果ci=0，算法终止操作并随机输出它的猜测.
② 测试预言询问OT(CT,w)：敌手对任意的关键字w和SCF-PEKS密文CT进行测试询问.模拟者首先判断h′=H2(C1,C2,C3)和e(C1,(uh′vs′d))=e(pkR,C4)是否相等.随后做一个陷门查询OTw得到对应的Tw，如果
运行dTest(params,CT,Tw,skS,pkR,IDsender,IDserver)算法并将结果发送给如果ci=0，此时已知pkR=AxR,部分关键词密文
通过C1和
可以推测出：
随后判断等式
是否成立，因为等式
成立.最后运行dTest(params,CT,Tw,skS,pkR,IDsender,IDserver)算法并将结果发送者
3) 挑战阶段.敌手输出一个想要挑战的三元组(pkR*,w0,w1)，模拟者回复为：
① 从列表中恢复三元组(pkR*,xR*,ci*)，如果对应的
终止操作且随机输出它的猜测.
② 否则当ci*=0，意味着
随机选择δ∈{0,1}，计算C*1=gxR*,C*2=QxS(wδ×α0×IDsender+β),C*3=H1(QxS×wδ×α0).随后设置h′*=H2(C*1,C*2,C*3),s′*=-xuh′*xv,C*4=gα1h′*+α2s′*+α3.最后返回挑战密文CT*=(s′*,C*1,C*2,C*3)给敌手此时如果Q=(g,g)ba，则CT*是一个合法的挑战密文，设r*=1a，我们有：
C*1=gx*R=(ga)x*R(1a)=(Ax*R)r*=p
，
C2=QxS(wδ×α0×IDsender+β)=
e(pkS,B)(wδ×α0×IDsender+β)a=
e(pkS,Bwδ×α0×IDsenderBβ)1a=
C*3=H1(QxS(wδ×α0))=H1(e(pkS,g(wδ×α0))ba)=
H1(e(pkS,B(wδ×α0))r*)，
C*4=g(α1h′*+α2s′*+α3)=(Aα1h′*+α2s′*+α3)r*=
(gxuh′*+xvs′*×Aα1h′*×Aα2s′*×Aα3)r*=
((gxu×Aα1)h′*(gxv×Aα2)s′*Aα3)r*=(uh′*vs′*d)r*，
因为Q在G2是独立且均匀分布的，所以挑战密文CT*也独立于δ.
4) 询问阶段2.敌手继续像询问阶段1一样进行询问.限制条件是挑战关键字(w0,w1)不能在陷门预言询问OTw中被询问，且在测试预言询问OT(CT,w)阶段CT*,w0和CT*,w1不能被询问.
5) 猜测.最终敌手输出他的猜测δ′∈{0,1}.如果δ′=δ，则输出1，意味着Q=e(g,g)ba，否则意味着Q=e(g,g)r.
概率分析.我们定义Abort为模拟者在模拟过程中终止的事件，我们有Pr[
Abort]≥θqTw(1-θ)，其中θ的最大值为
Pr[Abort]至少为
因此
证毕.
引理2. 假设DBDH问题是困难问题，我们的方案在标准模型下能够抵抗选择关键词攻击(chosen keyword attack， CKA).
证明. 假设敌手是一个外部敌手(包括一个接收者)，以ε的优势攻击所提出的SCF-PEKS方案.H,H1,H2是碰撞稳定的Hash函数.构造模拟者能以ε′的优势解决DBDH问题.其中
模拟者输入一个DBDH实例(g,A=ga,B=gb,C=gc,Q)，其中a,b,c∈Z目的是判断e(g,g)abc=Q是否相等.
1) 系统建立.模拟者首先随机选取α1,α2,α3,β∈Z设置g1=B=gb,h=Bβ,u=Aα1,v=Aα2,d=gα3.随后设置服务器的公钥pkS=A=ga，再随机选取xR∈Z设置pkR=gxR,skR=xR.最后将pkR,skR,pkS发送给
2) 询问阶段1.敌手进行测试预言询问.
测试预言询问对任意的关键字w和SCF-PEKS密文CT进行测试询问.模拟者首先判断h′=H2(C1,C2,C3)和e(C1,(uh′vs′d))=e(pkR,C4)是否相等.因为
我们有:
接着判断是否有
成立，因为
成立.随后随机选取r′∈Z
并计算Tw=(T1,T2)，其中
然后运行dTest(params,CT,Tw,skS,pkR,IDsender,IDserver)算法并将结果发送给
3) 挑战阶段.敌手输出一个想要挑战的三元组(pkR*,w0,w1)，模拟者回复如下：首先选取δ∈{0,1}，挑战关键词为w*=wδ，接着计算C*1=(gc)x*R,C*2=Q(w*×IDsender+β),C*3=H1(Qw*),h′*=H2(C*1,C*2,C*3),s′*=-α1h′*α2,C*4=Cα3.在最后把挑战的关键词密文CT*=(s′*,C*1,C*2,C*3,C*4)发送给如果此时Q=e(g,g)abc，则CT*是一个合法的挑战密文，设r*=c，我们有：
C*2=Q(w*×IDsender+β)=e(g,g)abc(w*×IDsender+β)=
e(ga,gb(w*×IDsender+β))c=e(pkS,gw*×IDsenderh)r，
C*3=H1(Qw*)=H1(e(g,g)abc×w*)=
C*4=(gc)α3=(gα3)c=
(Aα1×h′*×Aα2×s′*×gα3)c=(uh′*vs′*d)r*.
4) 询问阶段2.敌手继续像询问阶段1一样进行询问.限制条件是在测试预言询问OT(CT,w)阶段中CT*,w0和CT*,w1不能被询问.
5) 猜测.最终敌手输出他的猜测δ′∈{0,1}.如果δ′=δ，则输出1，意味着Q=e(g,g)abc，否则意味着Q=e(g,g)r.
证毕.
定理2. 假设HDH问题是困难问题，我们的方案在标准模型下能够抵抗离线关键词猜测攻击(off-line keyword guessing attack， KGA).
证明. 我们假设敌手是一个外部的敌手，他最多进行qTw次陷门询问，且以ε的优势攻击所提出的SCF-PEKS方案.构造模拟者能以ε′的优势解决HDH问题.其中ε′=ε.输入一个HDH实例(g,A=ga,B=gb,η)，其中a,b∈Z目的是输出H(gab)=η是否相等.
1) 系统建立.模拟者首先随机选择xR,l∈Zg1∈G1，设置接收者的私钥skR=xR，公钥pkR=gxR，接着设置服务器的公钥pkS=Al=(ga)l，这里暗示着skS=a×l.最后将pkR,skR发送给
2) 询问阶段1.敌手进行测试预言询问.
① 陷门预言询问对关键字wi进行陷门询问，模拟者随机选择r′∈Z计算T1=gr′,
并将Twi=(T1,T2)作为结果输出.
3) 挑战阶段.输出2个想要挑战的关键词(w0,w1)，首先模拟者随机选择δ∈{0,1}，挑战关键词为
计算挑战陷门如下：设置
这里l在系统建立阶段被定义.把挑战的关键词陷门Tw*=(T*1,T*2)发送给敌手如果H(gab)=η,Tw*=(T*1,T*2)是一个合法的陷门，这里r′*=bl，
T*1=B1l=gr′*,
4) 询问阶段2.敌手继续像询问阶段1一样进行询问，限制条件是挑战关键词w0,w1不能在陷门预言询问OTw中被询问.
5) 猜测.最终敌手输出他的猜测δ′∈{0,1}.如果δ′=δ，则输出1，意味着H(gab)=η，否则意味着η∈G1.
证毕.
5 SCF-PEKS性能对比
在计算
时，e(pkS,g1)和e(pkS,h1)可以被提前计算，所以我们方案的效率可以进一步提高.表2为我们同其他方案进行效率对比的情况，我们使用tp,te,th,ts,tv分别表示双线性运算、指数运算、Hash运算、一次签名的签名和验证运算的代价，我们同时和文献[8，19]进行了实验对比.实验通过使用具有处理器(Intel® CoreTM i7-7700CPU@3.60 GHz)，8 GB的内存和Window 10操作系统的计算机，利用eclipse工具，采用Java语言进行对比，结果如图2～4.其他方案的安全模型在表1中已出现，最后在表3中，我们对文献[8，19]和本方案进行了安全模型的对比.综合来看，文献[8]加密关键字的计算代价比较高，在我们方案中，虽然陷门的计算代价略高，但是相比文献[19]，我们的方案是在标准模型下进行的证明安全，且不需要授权认证.
Table 2 Efficiency Comparisons of Different Schemes
表2不同方案的效率对比
SchemePEKSdTrapdoordTestRef[8]3tp+8te+th+ts2te4tp+4te+th+tvRef[17]3tp+thtp+te+thtpRef[19]2tp+4te+3thtp+3te+3th3tp+6te+2thRef[22]2tp+2te+3th3te+2thtp+teRef[23]tp+4te+2th5te+2th2tpOurs2tp+7te+2th4te+th3tp+5te+2th
Fig. 2 Computation cost of PEKS
图2 加密关键字的计算代价
Fig. 3 Computation cost of trapdoor
图3 陷门产生的计算代价
Fig. 4 Computation cost of test
图4 匹配的计算代价
Table 3 Performance Comparison of Security Model Between Ours Scheme and Other Two Schemes
表3 本文方案和其他2种方案安全模型的性能对比
SchemePublicChannelStandardModelRCKAServerReceiverRCCAREKGARIKGAWithout AFRef[8]√√√√√√×√Ref[19]√×√√√√√×Ours√√√√√√√√
Note: √ means that the requirement is met; × means that the requirement is not met.
6 总结与展望
本文构造了一个高效率的带关键词搜索公钥加密方案，该方案能够抵制内部、外部离线关键词猜测攻击，而且在不使用安全信道的前提下可抵制适应性选择密文攻击.但本文的不足是，在安全性证明中敌手的私钥由模拟器来产生.下一步的工作是构造一个更符合实际应用的带关键词搜索的公钥加密方案.
[1]Boneh D, Di C G, Ostrovsky R, et al. Public key encryption with keyword search[G] 
LNCS 3027: Proc of the 23rd Int Conf on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 2004: 506-522
[2]Boneh D, Franklin M. Identity-based encryption from the weil pairing[G] LNCS 2139: Proc of the CRYPTO 2001. Berlin: Springer, 2001: 213-229
[3]Baek J, Safavinaini R, Susilo W. Public key encryption with keyword search revisited[G] LNCS 5072: Proc of 2008 Int Conf on Computation Science and Its Aplications.Berlin: Springer, 2008: 1249-1259
[4]Rhee H S, Park J H, Susilo W, et al. Trapdoor security in a searchable public-key encryption scheme with a designated tester[J]. Journal of Systems and Software, 2010, 6(5): 237-243
[5]Rhee H S, Park J H, Susilo W, et al. Improved searchable public key encryption with designated tester[C] Proc of the 4th International Symposium on Information, Computer, and Communications Security. New York: ACM, 2009: 376-379
[6]Fang Liming, Susilo W, Ge Chunpeng, et al. A secure channel free public key encryption with keyword search scheme without random oracle[G] LNCS 5888: Proc of CANS 2009. Berlin: Springer, 2009: 248-258
[7]Gentry C. Practical identity-based encryption without random oracles[C] Proc of the 25th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 445-464
[8]Fang Liming, Susilo W, Ge Chunpeng, et al. Public key encryption with keyword search secure against keyword guessing attacks without random oracle[J]. Information Sciences, 2013, 238(7): 221-241
[9]Byun J W, Rhee H S, Park H A, et al. Off-line keyword guessing attacks on recent keyword search schemes over encrypted data[C] Proc of the 3rd VLDB Workshop on Secure Data Management(SDM 2006). Berlin: Springer, 2006: 75-83
[10]Park D, Kim K, Lee P J. Public key encryption with conjunctive field keyword search[C] Proc of Int Conf on Information Security Applications. Berlin: Springer, 2004: 73-86
[11]Jeong I R, Kwon J O, Hong D, et al. Constructing PEKS schemes secure against keyword guessing attacks is possible[J]. Computer Communications, 2009, 32(2): 394-396
[12]Rhee H S, Susilo W, Kim H J. Secure searchable public key encryption scheme against keyword guessing attacks[J]. IEICEE Lectronics Express, 2009, 6(5): 237-243
[13]Guo Lifeng, Yau W C. Efficient secure-channel free public key encryption with keyword search for EMRs in cloud storage[J]. Journal of Medical Systems, 2015, 39(2): 1-11
[14]Yau W C, Phan C W, Heng S H, et al. Keyword guessing attacks on secure searchable public key encryption schemes with a designated tester[J]. International Journal of Computer Mathematics, 2013, 90(12): 2581-2587
[15]Shao Zhiyi, Yang Bo. On security against the server in designated tester public key encryption with keyword search[J]. Information Processing Letters, 2015, 115(12): 957-961
[16]Lu Yang, Wang Gang, Li Jiguo. Keyword guessing attacks on a public key encryption with keyword search scheme without random oracle and its improvement[J]. Information Sciences, 2019, 479: 270-276
[17]Huang Qiong, Li Hongbo. An efficient public-key searchable encryption scheme secure against inside keyword guessing attacks[J]. Information Sciences, 2017, 403-404: 1-14
[18]Wu Tsuyang, Chen Chienming, Wang Kinghang, et al. Security analysis of a public key authenticated encryption with keyword search scheme[C] Proc of Int Conf on Intelligent Information Hiding and Multimedia Signal Processing. Berlin: Springer, 2018: 178-183
[19]Li Hongbo, Huang Qiong, Shen Ji, et al. Designated-server identity-based authenticated encryption with keyword search for encrypted emails[J]. Information Sciences, 2019, 481: 330-343
[20]Lu Yang, Li Jiguo. Constructing designated server public key encryption with keyword search schemes withstanding keyword guessing attacks[J]. International Journal of Communication Systems, 2019, 32(3): e3862.1-e3862.18
[21]Lu Yang, Li Jiguo J. Efficient searchable public key encryption against keyword guessing attacks for cloud-based EMR systems[J]. Cluster Computing, 2019, 22: 285-299
[22]Lu Yang, Li Jiguo, Zhang Yichen. SCF-PEPCKS: Secure channel free public key encryption with privacy-conserving keyword search[J]. IEEE Access, 2019, 7: 40878-40892
[23]Wu Libing, Chen Biwen, Zeadally S, et al. An efficient and secure searchable public key encryption scheme with privacy protection for cloud storage[J]. Soft Computing, 2018(22): 7685-7696
[24]Noroozi M, Eslami Z. Public key encryption with keyword search, a genetic construction secure against online and offline keyword guessing attacks[J]. Journal of Ambient Intelligence and Humanized Computing, 2020(11): 879-890
[25]Shen Zhirong, Xue Wei, Shu Jiweu. Survey on the research and development of searchable encryption schemes[J]. Journal of Software, 2014, 25(4): 880-895 (in Chinese)(沈志荣, 薛巍, 舒继武. 可搜索加密机制研究与进展[J]. 软件学报, 2014, 25(4): 880-895)
[26]Dong Xiaolei, Zhou Jun, Cao Zhenfu. Research advances on secure searchable encrytion[J]. Journal of Computer Research and Development, 2017, 54(10): 2107-2120 (in Chinese)(董晓蕾, 周俊, 曹珍富. 可搜索加密研究进展[J]. 计算机研究与发展, 2017, 54(10): 2107-2120)
[27]Li Zhen, Jiang Han, Zhao Minghao. A discretionary searchable encrytion scheme in multi-user settings[J]. Journal of Computer Research and Development, 2015, 52(10): 2313-2322 (in Chinese)(李真, 蒋瀚, 赵明昊. 一个自助授权的多用户可搜索加密方案[J]. 计算机研究与发展, 2015, 52(10): 2313-2322)
[28]Wang Yunling, Wang Jianfeng, Chen Xiaofeng. Secure searchable encryption: A survey[J]. Journal of Communications & Information Networks, 2016, 1(4): 52-65
[29]Coron J S. On the exact security of full domain Hash[G] LNCS 1880: Proc of Crypto. Berlin: Springer, 2000: 229-235
