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

杨宁滨 周 权 许舒美

(广州大学数学与信息科学学院 广州 510006)

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

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 困难性假设

|Pr[A(g,ga)=a]|<ε.

|Pr[A(G,q,g,ga,gb,Z)=1]-
Pr[A(G,q,g,ga,gb,H(ga b))=1]|<ε.

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

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

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

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

2) 外部攻击者准备想要执行攻击的关键词集{w1,w2,…,wn}，借助被攻击对象的公钥执行SCF-PEKS的加密算法生成所有可能与文件密文对应的关键词密文，即Cf,Cwi，并且维护列表{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).

Fig. 1 The scheme system framework图1 方案系统框架

授权中心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.

Game MKC-IND-CKA：

Adv(λ)MKC-IND=|Pr[b=b′]-12|.

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

Game KT-IND-CKA：

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

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

Adv(λ)KT-IND-CKA=|Pr[b=b′]-12|

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

4 方案描述

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

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.

方案正确性：

ss=H1((pkR1)skS1)=H1((pkS1)skR1)=ss1；

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

5 安全性证明

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

引理1[18].定义S1,S2,E为3个不同的事件且E为错误事件，使得事件S1|E发生当且仅当在事件S2|E发生时，有：

|Pr[S1]-Pr[S2]|≤Pr[E].

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

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

AdvMKC-IND-CKA=|Pr[X0]-12|.

Pr[X1]=Pr[X0].

ss=H1((pkR1)skS1).

ss1=H1((pkS1)skR1).

ss1=H1((pkR1)skS1).

Pr[X2]=Pr[X1].

|Pr[X2]-Pr[X3]|≤2n×AdvH.

AdvMKC-IND-CKA=|Pr[X4]-12|.

AdvMKC-IND-CKA=|Pr[X0]-12|≤
|Pr[X0]-Pr[X1]|+|Pr[X1]-Pr[X2]|+
|Pr[X2]-Pr[X3]|+|Pr[X3]-Pr[X4]|+
|Pr[X4]-12|.

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

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

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

证毕.

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

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

AdvKT-IND-CKA=|Pr[X0]-12|.

Pr[X1]=Pr[X0].

ss1=H1(ga b).

ss1=H1(ga b).

ss1=H1(ga b).

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

Pr[X2]=Pr[X1].

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

|Pr[X2]-Pr[X3]|≤2AdvH.

|Pr[X3]-Pr[X4]|≤AdvHDH.

AdvKT-IND-CKA=|Pr[X4]-12|.

AdvKT-IND-CKA=|Pr[X0]-12|≤
|Pr[X0]-Pr[X1]|+|Pr[X1]-Pr[X2]|+
|Pr[X2]-Pr[X3]|+|Pr[X3]-Pr[X4]|+
|Pr[X4]-12|.

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

AdvKT-IND-CKA=AdvHDH+ 2AdvH.

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

证毕.

6 性能分析

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

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

Table 1 Security Properties Comparison表1 安全性能比较

Table 2 Efficiency Comparison of Different Schemes表2 不同方案的效率比较

Fig. 2 Computation cost of keyword encryption and testing图2 关键词加密与验证的计算消耗比较

Fig. 3 Communication size of keyword ciphertext and trapdoor图3 关键词密文与关键词陷门通信存储大小比较

为了直观展示NBP-SCF-PAEKS方案与其他方案关键词的运算时间消耗对比，进行了仿真实验.实验环境是在操作系统为Ubuntu 16.04 LTS，处理器为Intel®CoreTMi5-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方案具有非双线性对的高效运算，能够满足抵抗离线模式下内部攻击者的关键词猜测攻击和在线模式下外部攻击者的关键词猜测攻击的安全性并且具有认证的功能，使得本文方案更具有应用意义，更适合于计算能力有限的设备上使用.

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