无配对公钥认证可搜索加密方案

云计算高速发展以及5G通信应用的推广下，云存储服务受到了人们的广泛关注.人们可以将自己的电子邮件、个人健康记录和财务信息等数据上传到云端，与他人共享或在任何地方使用.显然，云计算给人们带来了很多方便.但是，这存在着数据隐私性的安全问题.用户在上传数据到云端后，数据的所有权则由云端的服务器所管理，这可能存在云端服务器不完全可信的状态下导致数据泄露.用户不能完全地控制自己上传的数据安全性，这远远不能满足数据云端安全的实用性.

在过去的研究中，人们为了满足数据隐私性可以通过传统的数据加密来保证数据存储的安全性.然而，这仅适合数据存储并不适用于数据检索.针对这种存在的现象，不少学者提出可检索保护云端数据隐私性安全的方案.Song等人[1]是第1个提出一种有效解决云存储的隐私问题的可搜索加密办法，而公钥可搜索加密(PEKS)是可搜索加密方案提出后由Boneh等人[2]首先提出的一种方法.在Boneh等人提出的公钥可搜索加密方案中，有3个行为主体：数据发送者(或称为数据拥有者、Bob)、数据接收者(或称数据使用者、Alice)以及云服务提供者.Bob首先整理想要分享的一份文件以及对应的关键词w=urgent，并对文件和关键词通过加密算法生成文件密文Cf及关键词密文Cw上传至云服务提供者，关键词密文可供云服务提供者检索找到对应的文件.当Alice想要检索带关键词w′=urgent的文件时，只需针对关键词生成陷门Tw′，发送至云服务提供者.然后由云服务提供者检索并匹配关键词是否相等，即

最后把匹配结果返回给Alice，若匹配成功，则会返回文件密文Cf，否则返回空值.因此，Alice可以借助密钥解密文件密文获取明文文件file.在整个检索过程，云服务提供者不知道Bob上传文件与关键词的内容.

Boneh等人所提出的方案是需要在秘密通道下才可以安全传输数据到云服务器.但是，一旦攻击者截获秘密通道传输的数据，用户的隐私数据则会被窃取.Baek等人[3]对此研究并提出了公共通道的PEKS方案，解决了Boneh等人的方案中存在的隐私性问题.之后，Huang等人[4]提出的PAEKS方案满足了陷门不可区分性，但是该方案在文献[5]中被指出不满足密文不可区分性.攻击者可以公开地对关键词密文进行对等测试.因此，方案抵抗外部攻击者与内部攻击者的关键词猜测攻击，是实现方案的关键词安全性的充要条件.

目前多数的公钥可搜索加密方案是基于双线性对运算所设计的.这在资源能力有限的设备上执行会降低其运算效率，从而影响用户双方的交互体验.为了提高用户与云端服务器交互的效率以及满足关键词隐私安全性，提出一个非双线性对运算的带关键词的公钥认证加密方案.

本文主要贡献包括3个方面：

1) 提出一个基于非双线性对运算下的公共通道的公钥认证可搜索加密方案(NBP-SCF-PAEKS)，相对于双线性对运算的方案效率大大提高.该方案是基于用户双方密钥协商构造的，从而具备访问控制的功能，即具备一定的认证功能.

2) 通过无随机预言机模型下使用Game-Hopping方案证明该方案满足适应性选择关键词攻击下多关键词密文的不可区分性以及适应性选择关键词攻击下的陷门不可区分性，从而使该方案达到抵抗离线内部攻击者的关键词猜测攻击以及在线外部攻击者的关键词猜测攻击的安全性.

3) NBP-SCF-PAEKS方案与SCF-PEKS[3]，PAEKS[4]，SCF-PEPCKS[6]，Hwang等人方案[7]以及PAEKSR[8]方案的计算效率和存储大小进行仿真比较，实验结果是方案的计算效率相对于其他比较的方案要高，并且所需存储内存较小.

1 相关工作

文献[1]中Song等人是最先提出可搜索加密的方案，但是该方案需要遍历所有文件才可以返回搜索结果，因此需要花费较大计算代价；文献[2]中Boneh等人介绍了带关键词的公钥可搜索加密方案(PEKS)，但不久之后，研究者发现了PEKS方案明显的缺陷，关键字陷门需要秘密传输到云服务器；文献[3]中Baek等人针对PEKS方案提出了一个在公共通道下实现的公钥可搜索加密方案(SCF-PEKS)，解决PEKS[2]中存在的缺陷；Yau等人[9]研究离线关键词猜测攻击，并且表明容易遭受内部敌手攻击；文献[10]中Fang等人提出了在不使用随机预言机模型下证明SCF-PEKS方案的关键词安全性.但是PEKS和SCF-PEKS方案都存在着关键词的隐私性问题.当攻击者为指定服务器时，易遭受关键词猜测攻击.因此，公钥可搜索加密中关键词的隐私性成为研究者所需要解决的问题.文献[11]中Emura等人提出了自适应安全的无安全通道的公钥可搜索加密的通用构造方案；Rhee等人在文献[12]中引入了“陷门不可区分性”概念，并证明了这是抵抗关键词猜测攻击的一个充分条件.根据攻击模式可以分为关键词在线猜测攻击与关键词离线猜测攻击；文献[13]中Noroozi等人提出了新的PEKS方案来抵抗外部攻击者的离线与在线关键词攻击.

根据攻击者的类型可分为外部攻击者和内部攻击者.内部攻击者一般指的是半可信云服务器，外部攻击者一般指的是除数据提供及使用的双方用户与服务器外的攻击者.由于半可信服务器被允许对关键词密文及关键词陷门做匹配测试，所以半可信的服务器比外部攻击者的权限更大.文献[4]中Huang等人介绍其方案(PAEKS)满足抵抗内部攻击者的关键词猜测攻击.其主要工作是对关键词加密时引入发送者的私钥，实现公钥认证加密功能，但是这个方案的陷门是固定的，且被指出不满足密文不可区分性[5].文献[7]中Hwang等人提出对ElGamal改进下的非双线性对下的公钥可搜索加密，能够抵御外部攻击者的关键词猜测攻击.文献[4,14-15]中徐海琳等人及陆阳等人采用借助双方的公私钥产生密钥协商的关键词密文与陷门，只有认证的用户才能实现密文与陷门的产生，并且能够抵御已知的3种关键词猜测攻击.文献[8]中Qin等人指出了Huang等人的PAEKS方案的关键词隐私性不足，在选择明文攻击不允许敌手公开质询消息密文，并且不能满足多关键词密文猜测攻击.在此基础上改进后提出可认证的带关键词的公钥加密方案(PAEKSR)，同时满足多关键词密文不可区分性安全.

文献[16]中Chen等人介绍了一种新型的抵抗内部攻击者离线关键词猜测攻击的公钥可搜索加密，即辅助服务器的公钥可搜索加密.该方案是借助服务器提供关键词的盲签名，并返回给用户再进行PEKS加密，服务器的盲签名的密钥具备密钥更新的功能，使得方案更具灵活性，并且引入限速机制来抵抗在线关键词猜测攻击.Zhang等人[17]在此工作基础上推广到区块链的公链上应用，并且能够抵抗已知的关键词猜测攻击.文献[18]中Dent提出的Game -Hopping方法是一种验证密码方案安全性的方法，攻击者在特定的攻击环境中运行一个未知的成功概率，随着调整攻击环境不断计算，直到计算出攻击者成功的概率，利用这个临界值来判断方案的安全性.

之后，研究者针对公钥可搜索加密方案设计具有不同功能的方案，其中有可验证的关键词可搜索加密[19-21]、模糊关键词的可搜索加密[22]、基于属性加密的带关键字搜索方案[23-24]以及基于代理重加密的带关键字搜索方案[25]等.

2 预备知识

本节主要介绍困难性假设，并对关键词猜测攻击类型进行分析.

2.1 困难性假设

定义1. DL困难问题假设[26].给定素数阶为q的循环群G，g为G的一个生成元，随机选取

离散对数困难问题是给定ga，对于每个敌手在概率多项式时间算法能够以可忽略的概率ε正确计算出a，即:

定义2. HDH困难问题假设[27].给定素数阶为q的循环群G，g为G的一个生成元，并且给定Hash函数H:G→{0,1}l.Hash Diffie-Hellman困难问题是随机选取

给定Hash函数和(g,ga,gb,Z)∈G3×{0,1}l，判断Z与H(ga b)是否相等.对于每个敌手在概率多项式时间算法以可忽略概率ε正确区分Z与H(ga b)，即:

2.2 关键词猜测攻击类型分析

本节主要对Baek等人提出的SCF-PEKS方案中存在在线模式下外部攻击者关键词猜测攻击和离线模式下内部攻击者关键词猜测攻击进行描述.

在线模式下外部攻击者关键字猜测攻击[6]是由外部攻击者执行攻击，攻击步骤为：

1) 在在线模式下，外部攻击者首先确定攻击对象(目标接收方).

2) 外部攻击者准备想要执行攻击的关键词集{w1,w2,…,wn}，借助被攻击对象的公钥执行SCF-PEKS的加密算法生成所有可能与文件密文对应的关键词密文，即 width=8,height=11,dpi=110

Cf,Cw

i，并且维护列表{wi,Cwi,Cf}.

3) 外部攻击者将密文集合传输到云服务器.攻击者监视云服务器和目标接收方之间的通信.当目标接收方生成关键词陷门Tw发送至云服务器检索时，由于在公共信道传输，外部攻击者可以截获关键词陷门.一旦发现返回的搜索结果与之前注入的密文集合相关，对照维护的列表，外部攻击者就可以获取目标接收方正在搜索的关键字信息，从而获取用户搜索的关键词信息.

离线模式下内部攻击者关键词猜测攻击[6]是由内部攻击者(一般为恶意服务器)执行的.攻击步骤为：

1) 在离线模式下，内部攻击者首先确定攻击对象(目标接收方).

2) 内部攻击者接收到目标接收方的关键词陷门Tw后，准备想要执行猜测攻击的关键词w，借助目标接收方的公钥信息以及服务器公钥信息执行SCF-PEKS加密算法产生关键词密文Cw.

3) 内部攻击者拥有了关键词陷门Tw以及关键词密文Cw后，执行测试实验，直到攻击者猜测成功，否则返回步骤2)重新执行.

3 方案定义与安全模型

本节给出一个能够抵抗在线外部攻击者关键词猜测攻击以及离线内部攻击者关键词猜测攻击的安全性的方案定义，即非双线性对运算下公共通道带关键词搜索的公钥认证加密方案的定义(Non Bilinear Pairs SCF-PAEKS, NBP-SCF-PAEKS)，并且给出方案的安全模型.

3.1 方案定义

图1所示为NBP-SCF-PAEKS方案的系统框架.系统框架包括4个主体：授权中心(authorization center, AC)、数据拥有者(data owner, DO)、数据使用者(data user, DU)以及云服务提供者(cloud service provider, CSP).

授权中心AC主要职能是分发全局参数给系统框架内的其他主体.由于DO的本地存储能力有限，只能将带有关键词w索引的文件加密进行存储于CSP，即DO通过Encrypt算法加密产生关键词密文，与加密的文件一起存储于CSP中.当DU想要检索带关键词w的文件时，通过Trapdoor算法产生搜索陷门传至CSP，由CSP检索并通过Test算法验证是否存在匹配的关键词的文件.最后把搜索结果返回给DU.若匹配成功，则返回加密的文件给DU.DU解密即可获取明文文件.

NBP-SCF-PAEKS方案由5个多项式时间算法组成：

1) GlobalSetup(λ).该算法由授权中心AC执行，输入安全参数λ，输出全局公共参数GP.

2) KeyGen(GP).该算法由DO与DU分别执行完成，输入全局公共参数GP，DO输出公私钥对skS与pkS，而DU输出公私钥对skR与pkR.

3) Encrypt(GP,skS,pkR,w).该算法由DO执行，输入全局参数GP、关键词w、DO私钥skS、DU公钥pkR，输出关键词密文Cw，DO将关键词密文Cw与加密的文件Cf传至CSP中存储.

4) Trapdoor(GP,skR,pkS,w′).该算法由DU执行，输入全局参数GP、检索的关键词w′、DU私钥skR以及DO的公钥pkS，输出搜索陷门Tw′.

5) Test(GP,Cw,Tw′).CSP收到DU的搜索陷门Tw′，对关键词密文Cw与搜索陷门Tw′测试.若匹配成功，则输出1，并返回文件密文数据；否则输出0.

3.2 安全模型

Boneh等人首先引入了密文不可区分性的概念，它旨在防止外部攻击者在不知道关键字测试陷门的情况下获取加密文件中包含的任何关键字信息.而Qin等人[8]在此基础上延展提出多密文不可区分性.而陷门不可区分性保证了给定一个未知关键字的测试陷门，内部攻击者无法获得关于关键字的任何有用信息.

在2.2节所讨论的在线模式下外部攻击者关键词猜测攻击与离线模式下内部攻击者的关键词猜测攻击是目前公钥可搜索加密中需要解决的安全性问题.而本文所提出的公钥认证可搜索加密方案则可以抵抗这2类攻击，值得注意的是，由于方案的正确性，避免了外部攻击者的存在.假设NBP-SCF-PAEKS方案中存在一个外部攻击者，由该方案正确性定义可知，攻击者若生成了可被关键词陷门匹配的可搜索密文，则该攻击者是数据使用者(DU)所认可的数据拥有者(DO)，与它是外部攻击者相矛盾.这限制了外部攻击者攻击的可能，使得方案更具安全性.

因此，提出NBP-SCF-PAEKS方案需要同时满足2点：1)适应性选择关键词攻击下的多关键词密文不可区分性(multi-keyword ciphertext indisting-uishability under the adaptive chosen keyword attack, MKC-IND-CKA);2)适应性选择关键词攻击下的关键词陷门不可区分性(keyword trapdoor indisting-uishability under the adaptive chosen keyword attack, KT-IND-CKA).MKC-IND-CKA保证敌手不能区分其挑战的2个关键词集的密文，而KT-IND-CKA则保证敌手不能区分其挑战的2个关键词陷门.针对公钥认证可搜索加密方案，敌手可分为2类：外部攻击者与内部攻击者.这里定义外部攻击者为除DO,DU以及CSP之外的攻击者，内部攻击者为恶意的CSP.

结合这2类敌手，MKC-IND-CKA与KT-IND-CKA的安全性可以由挑战者

和敌手

(外部攻击者或者内部攻击者)之间的游戏模型Game MKC-IND-CKA和Game KT-IND-CKA来定义，游戏模型内容所述.

1) 系统初始化.

首先运行GlobalSetup(λ)和KeyGen(GP)算法，产生全局参数GP、DO的公私钥(skS,pkS)以及DU的公私钥(skR,pkR).并发送GP,pkS,pkR给

2) 询问阶段

对

发出以下一系列的适应性预言询问.

OCiphertext.给定任意关键词

运行Encrypt(GP,skS,pkR,w)算法并返回产生的关键词密文Cw给

OTrapdoor.给定任意关键词

运行Trapdoor(GP,skR,pkS,w′)算法并返回产生的关键词陷门Tw′给

OTest.

提交关键词密文Cw与关键词陷门

运行Test(GP,Cw,Tw′)算法并返回结果给

测试询问模拟敌手通过关键词测试询问作为预言机来验证单个关键词密文和单个关键词陷门是否匹配的攻击行为.

3) 挑战阶段.

提交2个不同的关键词集w0={w0,1,w0,2,…,w0,n}和w1={w1,1,w1,2,…,w1,n}进行挑战，并且限制未在第一阶段询问过的关键词w0,iw1,i(i∈[1,n])的密文和陷门.

对于i∈[1,n]随机选取b∈{0,1}，运行Encrypt(GP,skS,pkR,wb,i)并返回产生的关键词wb,i的挑战密文

给

4) 询问阶段2.与询问阶段1一样，并且限制

不能询问关键词w={w0,1,w0,2,…,w0,n,w1,1,w1,2,…,w1,n}的密文、陷门.

5) 猜测.

输出猜测结果b′∈{0,1}.如果b=b′，则

赢得游戏.所以，敌手

赢得游戏的优势为

定义3. 若不存在多项式时间敌手能够以不可忽略的优势赢得上述Game MKC-IND-CKA，则可认为本方案满足适应性选择关键词攻击下的多关键词密文不可区分性安全.

1) 系统初始化.与Game MKC-IND-CKA的初始化阶段一致.

2) 询问阶段1.与Game MKC-IND-CKA的第一阶段询问一致.

3) 挑战阶段.

提交2个不同的关键词w0，w1进行挑战，并且限制未在第一阶段询问过的关键词w0，w1的密文和陷门.

随机选取b∈{0,1}，运行Trapdoor(GP,skR,pkS,w′)并返回产生的关键词wb的挑战陷门Twb给

4) 询问阶段2.与询问阶段1一样，并且限制

不能询问关键词w0，w1的密文、陷门.

5) 猜测.

输出猜测结果b′∈{0,1}.如果b=b′，则

赢得游戏.所以，敌手

赢得游戏的优势为

定义4. 若不存在多项式时间敌手能够以不可忽略的优势赢得上述Game KT-IND-CKA，则可认为本方案满足适应性选择关键词攻击陷门不可区分性.

4 方案描述

在3.1节给出了NBP-SCF-PAEKS方案的定义，其5个时间算法具体描述为：

1) GlobalSetup(λ).输入安全参数λ，输出素数阶为q的循环群G，g是G的一个生成元，Hash函数H1:G →{0,1}l 和

表示二进制长度.因此，输出全局参数为GP=(G,q,g,H,H1,KSw)，其中KSw为关键词集.

2) KeyGen(GP).DO随机选取私钥skS=(skS1,skS2)且

计算出公钥pkS=(pkS1,pkS2)=(gskS1,gskS2)，DU随机选取私钥skR=(skR1,skR2)且

计算出公钥pkR=(pkR1,pkR2)=(gskR1,gskR2).

3) Encrypt(GP,skS,pkR,w).DO随机选取

且r>H(w‖ss)，计算关键词密文

其中ss=H1((pkR1)skS1).并将Cw与加密的文件上传至CSP.

4) Trapdoor(GP,skR,pkS,w′).DU选定需要搜索的关键词w′，计算搜索陷门Tw′=g-skR2×H(w′‖ss1)，其中ss1=H1((pkS1)skR1).并将其上传至CSP检索.

5) Test(GP,Cw,Tw′).CSP收到DU的搜索陷门Tw′后，计算H1(C1×Tw′)=C2是否成立，若成立则输出1并返回文件密文数据，否则返回0.

若w′=w，则等式H1(C1×Tw′)=C2成立，故方案正确有效.

5 安全性证明

本节参考文献[6]以及Game-Hopping[18]方法给出NBP-SCF-PAEKS方案在无随机预言机模型下的安全性证明.下面需要使用差别引理[18]：

引理1[18]. 定义S1,S2,E为3个不同的事件且E为错误事件，使得事件S1| width=11,height=8,dpi=110

E发生当且仅当在事件S2| width=11,height=8,dpi=110

E发生时，有：

定理1. 若Hash函数H满足抗碰撞性、群G上DL假设是困难以及多项式时间内有限的n个关键词查询，则所提出方案满足适应性选择关键词攻击下多关键词密文不可区分性的安全.

证明. 假设

是针对本方案的适应性选择关键词攻击下多关键词密文不可区分性的安全的敌手，下面证明AdvMKC-IND-CKA是的优势是可忽略的.假设由5个子程序游戏Gamej(j=0,1,2,3,4)组成.假设

在子程序游戏中关键词猜测攻击正确(即b=b′)事件为Xj.

Game-Hopping方法的证明过程如下：

1) 游戏Game0.该游戏为原始敌手游戏Game MKC-IND-CKA.因此，

赢得游戏的优势为

2) 游戏Game1.该游戏与Game0相同，区别在于

随机选取

计算pkR=(pkR1,pkR2)=(gskR1,(ga)skR2)，其中g为G的生成元，其他参数与Game0等同.显然，Game1的参数与Game0的分布相同，即对

仍然是不可区分的.因此，

在这2个游戏中猜测的概率相同，即:

3) 游戏Game2.该游戏与Game1相同，区别在

改变对

对密文与陷门的询问的应答方式以及挑战密文的产生方式.

在2次询问阶段中，

应答

的有限次数内密文询问与陷门询问方式为：

OEncrypt.

提交关键词

运行Encrypt(GP,skS,pkR,w)算法并返回产生的关键词密文

给

其中:

OTrapdoor.

提交一个关键词

运行Trapdoor(GP,skR,pkS,w′)算法并返回产生的关键词陷门Tw′=g-skR2×H(w′‖ss1)给

其中:

OTest.

提交关键词密文Cw与关键词陷门

运行Test(GP,Cw,Tw′)算法判断H1(C1×Tw′)=C2是否成立，若成立返回1给

否则返回0.

在挑战阶段中，

提交2个不同的关键词元组w0={w0,1,w0,2,…,w0,n}和w1={w1,1,w1,2,…,w1,n}进行挑战，

随机选择

和b∈{0,1}，计算出:

因此，挑战密文

是关键词wb,i的有效密文.

在游戏Game2中，

能够正确应答各种预言询问及产生挑战密文.显然，Game1与Game2是不可区分的.因此，

在2个游戏中猜测正确的概率相同，即:

4) 游戏Game3.该游戏与Game2相同，区别在于若发生下列事件之一，

终止游戏.

事件

向

作关键词密文询问，其输入关键词w满足w≠ wb,i，但

事件

向

作关键词陷门询问，其输入关键词w满足w≠ wb,i，但H(w‖ss1)=H(wb,i‖ss1).

显然，若E1∨E2不发生，

在Game2和Game3中是不可区分的.由差别引理可得，Pr[E1∨E2]=|Pr[X2]-Pr[X3]|.此外，若事件E1发生，则必然存在针对Hash函数H的抗碰撞的敌手

其优势为n×AdvH≥Pr[E1].同理，若事件E2发生，也必然存在针对Hash函数H的抗碰撞的敌手

其优势为n×AdvH≥Pr[E2].因此：

5) 游戏Game4.该游戏与Game3相同，区别在于

使用群G的随机元素Z计算挑战密文

中的

显然，

无需知道a以及skR2的值，仅通过(g,gskR2,(ga)skR2)元组中(ga)skR2值即可应答

的所有询问以及挑战密文.显然，Game4和Game3是一致的，除非敌手可以通过不可忽略的概率优势区分Z和(ga)skR2(即解决DL困难假设).假设敌手

成功的优势为AdvDL，由差别引理可得，|Pr[X3]-Pr[X4]|≤n×AdvDL.并且Z为群G的一个随机元素，因此

猜中正确的概率为

结束Game-Hopping游戏并分析

的优势.

AdvMKC-IND-CKA=|Pr[X0]-1 width=5,height=17,dpi=110

2|≤
|Pr[X0]-Pr[X1]|+|Pr[X1]-Pr[X2]|+
|Pr[X2]-Pr[X3]|+|Pr[X3]-Pr[X4]|+
|Pr[X4]-1 width=5,height=17,dpi=110

2|.

因此，综合上述的游戏方程，可以得出如下结论：

AdvMKC-IND-CKA=n×AdvDL+ 2n ×AdvH.

本文在多项式时间内n个(多)关键挑战密文查询且基于Hash函数H是抗碰撞的并且基于离散对数DL的困难假设下，AdvMKC-IND-CKA是可忽略的，即本方案满足适应性选择关键词攻击下的多关键词密文不可区分性.

定理2. 若Hash函数H满足抗碰撞性且群G上HDH假设是困难的，则所提出方案满足适应性选择关键词攻击的陷门不可区分性的安全性.

证明. 假设

是针对本方案的适应性选择关键词攻击的陷门不可区分性的安全性的敌手，下面证明AdvKT-IND-CKA是的优势是可忽略的.假设由5个子程序游戏Gamej(j=0,1,2,3,4)组成.假设

在子程序游戏中关键词猜测攻击正确(即b=b′)事件为Xj.

Game-Hopping方法的证明过程为：

1) 游戏Game0.该游戏为原始敌手游戏Game KT-IND-CKA.因此，

赢得游戏的优势为

2) 游戏Game1.该游戏与Game0相同，区别在于

随机选取

计算pkS1=gb，pkR=(pkR1,pkR2)=(ga,gskR2)，其中g为G的生成元，其他参数与Game0等同.显然，Game1的新参数与Game0的分布相同，即对

仍然是不可区分的.因此，

在这2个游戏中猜测的概率相同，即:

3) 游戏Game2.该游戏与Game1相同，区别在

改变对

对关键词密文询问以及关键词陷门询问的应答方式以及挑战陷门的产生方式.

在2次询问阶段中，

应答

的密文询问、陷门方式为：

OEncrypt.

提交一个关键词

运行Encrypt(GP,skS,pkR,w)算法并返回产生的关键词密文

给

其中，

OTrapdoor.

提交一个关键词

运行Trapdoor(GP,skR,pkS,w′)算法并返回产生的关键词陷门Tw′=g-skR2×H(w′‖ss1)给

其中，

OTest.

提交关键词密文Cw与关键词陷门

运行Test(GP,Cw,Tw′)算法判断H1(C1×Tw′)=C2是否成立，若成立返回1给

否则返回0.

在挑战阶段中，

提交2个不同的关键词w0和w1进行挑战，

随机选择b∈{0,1}，计算出Twb=g-skR2×H(wb‖ss1)返回给

其中:

因此，挑战陷门Twb为有效陷门.

在游戏Game2中，

能够正确应答各种预言询问及产生挑战陷门.显然，Game1与Game2是不可区分的.因此，

在2个游戏中猜测正确的概率相同，即：

4) 游戏Game3.该游戏定义与定理1证明中Game3相同.

因此，存在抗碰撞的敌手

的优势为

5) 游戏Game4.该游戏与Game3相同，区别在于

使用群G的随机元素Z代替H1(ga b)来计算挑战陷门Twb.显然，

无需知道a和b的值，仅通过HDH元组下的(H1,g,ga,gb,Z) 即可应答

的所有询问以及挑战陷门.显然，Game4和Game3是一致的，除非敌手可以通过不可忽略的概率优势区分Z和H1(ga b)(即解决HDH困难假设).假设敌手

成功的优势为AdvKT-IND-CKA，由差别引理可得：

并且Z为群G的一个随机元素，因此

猜中正确的概率为

结束Game-Hopping游戏并分析

的优势，有：

AdvKT-IND-CKA=|Pr[X0]-1 width=5,height=17,dpi=110

2|≤
|Pr[X0]-Pr[X1]|+|Pr[X1]-Pr[X2]|+
|Pr[X2]-Pr[X3]|+|Pr[X3]-Pr[X4]|+
|Pr[X4]-1 width=5,height=17,dpi=110

2|.

综合上述的游戏方程，可以得出结论：

由于Hash函数H是抗碰撞的并且基于HDH的困难假设下，AdvKT-IND-CKA是可忽略的，即本方案满足适应性选择关键词攻击陷门不可区分性.

6 性能分析

本文的NBP-SCF-PAEKS方案是设计非双线性对下且在公共通道能够抵抗在线外部攻击者关键词猜测攻击和离线内部攻击者关键词猜测攻击的公钥认证可搜索加密方案，该方案高效安全可行.

表1给出本文方案与其他方案的功能比较.其中MKC-IND-CKA表示适应性选择关键词攻击的多关键词密文不可区分性安全，Out-online-KGA表示在线模式下外部攻击者关键词猜测攻击 In-offline-KGA表示离线模式下内部攻击者的关键词猜测攻击.

表2给出了本文方案与其他方案的的效率比较.其中符号p，e和h分别表示双线性对运算、群G中的模幂运算以及Hash运算，其系数表示运算次数.符号

和λ分别表示群G中元素的长度、群 GT(双线性表示G×G→GT)中元素的长度、群

元素的长度以及Hash值的长度.

为了直观展示NBP-SCF-PAEKS方案与其他方案关键词的运算时间消耗对比，进行了仿真实验.实验环境是在操作系统为Ubuntu 16.04 LTS，处理器为Intel® CoreTM i5-4210U CPU @2.40 GHz，运行内存为12 GB以及GMP库[28]、PBC库[29]下进行的.我们采用与文献[6]相同的实验条件下的512 b循环群以及SHA-256的Hash函数进行仿真.借助文献[6]与文献[8]仿真的SCF-PEKS,SCF-PEPCKS,PAEKS以及PAEKSR方案的关键词加密与测试的数据结果进行对比.仿真对比结果如图2所示.对于单个关键词下，NBP-SCF-PAEKS方案关键词加密所需的时间消耗为0.522 ms，陷门产生所需的时间消耗为0.4 ms，测试所需的时间消耗为0.02 ms.因此，该方案的3个多项式时间算法的运行时耗均在0.1毫秒级上，相对于包含双线性运算下的SCF-PEKS[3],PAEKS[4],SCF-PEPCKS[6],PAEKSR[8]以及Hwang等人[7]方案的计算效率要高.此外，该方案在关键词密文与关键词陷门的存储所需容量与SCF-PEKS[3],SCF-PEPCKS[6]以及PAEKSR[8]相等，相对于PAEKS[4]以及Hwang等人[7]方案要低，如图3所示:

7 总结与展望

本文提出一个基于非双线性对运算、公共通道的带关键词搜索的公钥认证可搜索加密方案.与过去的其他方案进行功能与效率的比较，NBP-SCF-PAEKS方案具有非双线性对的高效运算，能够满足抵抗离线模式下内部攻击者的关键词猜测攻击和在线模式下外部攻击者的关键词猜测攻击的安全性并且具有认证的功能，使得本文方案更具有应用意义，更适合于计算能力有限的设备上使用.

随着设备的更新换代以及量子计算机的研发促使计算机的计算能力提高，导致离散对数的密码体制下的云数据存在潜在的泄露风险.因此，构造可行性高的抗量子计算的公钥可搜索加密是下一步工作重心.

[1]Song D X, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C] //Proc of 2000 IEEE Symp on Security and Privacy (S&P 2000). Piscataway, NJ: IEEE, 2000: 44-55

[2]Boneh D, Di C G, Ostrovsky R, et al. Public key encryption with keyword search[C] //Proc of Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2004: 506-522

[3]Baek J, Safavi-Naini R, Susilo W. Public key encryption with keyword search revisited[C] //Proc of Int Conf on Computational Science and Its Applications. Berlin: Springer, 2008: 1249-1259

[4]Huang Qiong, Li Hongbo. An efficient public-key searchable encryption scheme secure against inside keyword guessing attacks[J]. Information Sciences, 2017, 403: 1-14

[5]Wu T Y, Chen C M, Wang K H, 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

[6]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

[7]Hwang M S, Lee C C, Hsu S T. An ElGamal-like secure channel free public key encryption with keyword search scheme[J]. International Journal of Foundations of Computer Science, 2019, 30(2): 255-273

[8]Qin Baodong, Chen Yu, Huang Qiong, et al. Public-key authenticated encryption with keyword search revisited: Security model and constructions[J]. Information Sciences, 2020, 516: 515-528

[9]Yau W C, Heng S H, Goi B M. Off-line keyword guessing attacks on recent public key encryption with keyword search schemes[C] //Proc of Int Conf on Autonomic and Trusted Computing. Berlin: Springer, 2008: 100-105

[10]Fang L, Susilo W, Ge C, et al. A secure channel free public key encryption with keyword search scheme without random oracle[C] //Proc of Int Conf on Cryptology and Network Security. Berlin: Springer, 2009: 248-258

[11]Emura K, Miyaji A, Rahman M S, et al. Generic constructions of secure-channel free searchable encryption with adaptive security[J]. Security and Communication Networks, 2015, 8(8): 1547-1560

[12]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, 83(5): 763-771

[13]Noroozi M, Eslami Z. Public-key encryption with keyword search: A generic construction secure against online and offline keyword guessing attacks[J]. Journal of Ambient Intelligence and Humanized Computing, 2020, 11(2): 879-890

[14]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

[15]Xu Hailin, Lu Yang, Searchable public key encryption secure against keyword guessing attacks[J] Computer Engineering and Applications, 2018, 54(24): 108-115 (in Chinese)(徐海琳, 陆阳. 抗关键词猜测攻击的可搜索公钥加密方案[J]. 计算机工程与应用, 2018,54 (24): 108-115)

[16]Chen Rongmao, Mu Yi, Yang Guomin, et al. Server-Aided public key encryption with keyword search[J]. IEEE Transactions on Information Forensics and Security, 2016, 11(12): 2833-2842

[17]Zhang Yuan, Xu Chunxiang, Ni Jianbing, et al. Blockchain-assisted public-key encryption with keyword search against keyword guessing attacks for cloud storage[J]. IEEE Transactions on Cloud Computing, 2019 [2020-05-01]. https://ieeexplore.ieee.org/abstract/document/8737775

[18]Dent A W. A note on game-hopping proofs[EB/OL]. Nevada, USA: International Association for Cryptologic Research, 2006[2019-12-01]. https://eprint.iacr.org/2006/260.pdf

[19]Miao Yinbin, Weng Jian, Liu Ximeng, et al. Enabling verifiable multiple keywords search over encrypted cloud data[J]. Information Sciences, 2018, 465: 21-37

[20]Zhou Quan, Yang Ningbin, Xu Shumei. Fault-tolerant and verifiable public key searchable encryption scheme based on FBDH algorithm[J]. Netinfo Security, 2020, 20(3): 29-35 (in Chinese)(周权, 杨宁滨, 许舒美. 基于FBDH算法的容错可验证公钥可搜索加密方案[J]. 信息网络安全, 2020, 20(3): 29-35)

[21]Guo Lifeng, Li Zhihao, Hu Lei. Efficient public encryption scheme with keyword search for cloud storage[J]. Journal of Computer Research and Development, 2020, 57(7): 1404-1414 (in Chinese)(郭丽峰, 李智豪, 胡磊. 面向云存储的带关键词搜索的公钥加密方案[J]. 计算机研究与发展, 2020, 57(7): 1404-1414)

[22]Xu Peng, Jin Hai, Wu Qianhong, et al. Public-key encryption with fuzzy keyword search: A provably secure scheme under keyword guessing attack[J]. IEEE Transactions on Computers, 2012, 62(11): 2266-2277

[23]Li Jiguo, Lin Xiaonan, Zhang Yichen, et al. KSF-OABE: Outsourced attribute-based encryption with keyword search function for cloud storage[J]. IEEE Transactions on Services Computing, 2016, 10(5): 715-725

[24]Gao Jiaxin, Sun Jiameng, Qin Jing. Traceable outsourcing attribute-based encryption with attribute revocation[J]. Journal of Computer Research and Development, 2019, 56(10): 2160-2169 (in Chinese)(高嘉昕, 孙加萌, 秦静. 支持属性撤销的可追踪外包属性加密方案[J]. 计算机研究与发展, 2019, 56(10): 2160-2169)

[25]Dong C, Russello G, Dulay N. Shared and searchable encrypted data for untrusted servers[J]. Journal of Computer Security, 2011, 19(3): 367-397

[26]Sadeghi A R, Steiner M. Assumptions related to discrete logarithms: Why subtleties make a real difference[C] //Proc of Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2001: 244-261

[27]Abdalla M, Bellare M, Rogaway P. The oracle Diffie-Hellman assumptions and an analysis of DHIES[C] //Proc of Cryptographers’ Track at the RSA Conf. Berlin: Springer, 2001: 143-158

[28]The GNU Multiple Precision Arithmetic Library[EB/OL]. [2020-02-15]. https://gmplib.org/

[29]Lynn B. PBC Library: The pairing-based cryptography library[EB/OL]. [2020-06-01]. https://crypto.standford.edu/pbc/

无配对公钥认证可搜索加密方案

1 相关工作

2 预备知识

2.1 困难性假设

2.2 关键词猜测攻击类型分析

3 方案定义与安全模型

3.1 方案定义

3.2 安全模型

4 方案描述

5 安全性证明

6 性能分析

7 总结与展望

Public-Key Authenticated Encryption with Keyword Search Without Pairings