基于合数阶双线性对的可搜索加密方案分析与改进

邓志辉,王少辉,王 平

(1.南京邮电大学 计算机学院,南京 210003; 2.江苏省无线传感网高技术研究重点实验室,南京 210003)

0 概述

随着互联网技术的迅速发展,人们在日常工作和生活中产生及使用的数据量不断增大,数据规模已由PB级发展到EB级甚至ZB级,如何存储和处理大规模数据成为亟待解决的问题。云计算是通过互联网提供动态、易扩展和虚拟化资源的计算方式,而云存储是云计算的应用模式,其可远程高效存储数据,能节省大量存储空间,因此引起了人们的广泛关注,并成为存储大数据的有效手段。

在云存储应用初期,部分用户以明文形式上传数据,由于云存储具有开放性和分布性,数据脱离用户的物理控制存储在云端后,一旦被外部攻击者截获或被恶意云服务提供者泄露,将无法挽回损失。因此,为保证所传数据的隐私性和安全性,用户会将数据加密后再上传到云端。加密存储数据在一定程度上可以保证数据的隐私与安全,但却给数据检索带来困难。

由于基于明文关键字的传统检索模型无法在密文下进行检索,因此2000年SONG等人[1]在对称密码体制的基础上提出可搜索加密的概念,并设计出可在密文下进行检索的SWP方案。2004年BONEH等人[2]首次提出公钥关键字搜索加密(Public Key Encryption with Keyword Search,PEKS),并设计一种应用于邮件路由分发场景的方案,将不同邮件分发到不同设备中,公钥关键字搜索加密允许服务器根据接收到的陷门对不同关键字邮件选择分发路由,且不会泄露邮件内容,但是该方案在安全和效率方面存在不足。WATERS等人[3]随后提出用来构造可搜索加密审计日志的新PEKS方法。GOLLE等人[4]也提出基于连接关键词的可搜索加密方案,可实现对多个关键词的搜索功能。2006年BYUN等人[5]分析了文献[2]中PEKS方案,指出该方案容易遭受关键字猜测攻击[6-7],此后研究者们提出大量抗关键字猜测攻击的PEKS方案[8-10]。2016年XU等人[11]提出合数阶双线性群下的PEKS方案,该方案系统参数比其他方案更少,且其安全性是基于静态假设下合数阶子群的不可区分性。文献[12]提出双服务器模型,通过2个独立服务器分享秘密检索陷门执行搜索算法抵抗关键字猜测攻击。文献[13]通过加入发送者公私钥生成可搜索密文和陷门,使服务器无法自行生成关键词陷门测试密文。文献[14]提出一种通过采用非确定算法生成关键字密文和陷门的方案,可高效抵抗关键字猜测攻击。

然而PEKS框架本身存在一定不足,即多数PEKS方案都需在服务器与接收者之间建立安全信道以传送陷门,否则外部攻击者很容易截获关键字陷门进行搜索操作,进而得到加密数据信息,但是建立安全信道代价太高且很难实现。为解决该问题,文献[15]提出无安全信道的公钥关键字搜索加密(Secure-Channel Free Public Key Encryption with Keyword Search,SCF-PEKS)方案,由于关键字密文的生成需要云服务器公钥参与,因此只有云服务器能够使用自身私钥检查关键字密文和陷门是否包含相同关键字。通过该方式,用户可在无安全信道的情况下将关键字陷门发送到数据存储服务器。但是上述方案依赖于随机oracle模型,而随机oracle模型不能真正反映方案在现实世界中的安全性。2009年FANG等人[16]提出首个在标准模型下安全的SCF-PEKS方案,但该方案检测算法太复杂,不具备高效性。2011年EMURA等人[17]利用匿名IBE、标签加密方案和一次性签名提出SCF-PEKS方案的通用设计方法。近期LI等人[18]从静态假设出发提出在标准模型下安全高效的SCF-PEKS方案,该方案主要基于判定性子群假设和DBDH假设,与现有在标准模型下构造的相关方案相比,具有更简洁的结构。

2009年RHEE等人[19]指出SCF-PEKS方案不能抵抗由外部攻击者发起的离线关键字猜测攻击,并在文献[20]中引入陷门不可区分性的概念,证明抵抗关键词猜测攻击的充分条件是陷门的不可区分性。本文对文献[11,18]提出的基于合数阶双线性对的可搜索加密方案进行分析,发现上述方案的关键字陷门生成算法无法满足搜索关键字陷门的不可区分性。针对该问题,本文在文献[11,18]方案的基础上,提出一种改进的无安全信道公钥可搜索加密方案,同时基于DBDH假设对其是否满足关键字陷门的不可区分性进行证明,并研究了该方案的计算复杂度和空间存储复杂度。

1 基本知识

1.1 合数阶双线性群

定义1(合数阶双线性映射) 设G和GT是2个阶为N=p1p2p3的乘法循环群,g是G的生成元。双线性映射e:G×G→GT满足以下性质:

1)可计算性:映射e:G×G→GT可以被有效计算。

3)非退化性:e(g,g)≠1。

e(h1,h2)=e(gp2p3α1,gp1p3α2)=e(gα1,gp3α2)p1p2p3=1

(1)

如果选取i≤j、hi∈Gpi、hj∈Gpj,则e(hi,hj)是群GT中的单位元,这说明合数阶双线性群中各子群Gp1、Gp2和Gp3相互正交。

1.2 判定性子群假设

假设1给定群生成器G(λ),定义其分布如下:

(2)

Pr[A(D,T1)=1]|关于λ是可忽略的。

(3)

1.3 DBDH假设

1.4 PEKS和SCF-PEKS

PEKS和SCF-PEKS方案都涉及发送者(数据拥有者)、接收者(用户)和云服务器三方参与者。发送者生成关键字的可搜索密文并将其连同密文数据发送给云服务器,接收者生成关键字陷门,云服务器根据关键字密文和陷门执行数据检索操作,并将匹配的密文数据发送给接收者。

1.4.1 PEKS方案

定义2公钥可搜索加密方案由以下4个算法组成:

1)Setup(λ)算法。输入安全参数λ,算法生成全局参数gp,用户公钥pk和私钥sk。

2)PEKS(gp,pk,ω)算法。由发送者执行,输入全局参数gp、用户公钥pk和关键字ω,输出关于关键字ω的可搜索密文C。

3)Trapdoor(gp,sk,ω)算法。由用户执行,输入全局参数gp、用户私钥sk和关键字ω,生成关键字陷门Tω。

4)Test(gp,C,Tω)算法。输入全局参数gp、可搜索密文C和关键字陷门Tω,服务器对关键字密文和陷门进行验证,如果验证匹配则输出1,否则输出0。

1.4.2 SCF-PEKS方案

SCF-PEKS方案与PEKS方案主要区别在于云服务器的公钥和私钥是否分别参与了可搜索密文生成算法和检测匹配算法。由于PEKS方案没有使用云服务器的公私钥对,因此其传送关键字陷门时需要使用安全信道才能避免受到攻击。而因为SCF-PEKS方案中云服务器的公钥参与了可搜索关键字密文生成过程,只有拥有对应私钥的云服务器才能进行检测匹配算法,所以传送关键字陷门时不需安全信道参与。

定义3无安全信道的公钥可搜索加密方案由以下4个算法组成:

1)Setup(λ)算法。输入安全参数λ,生成全局参数gp,并输出云服务器的公私钥对(pkS,skS),以及接收者的公私钥对(pkR,skR)。

2)SCF-PEKS(gp,pkS,pkR,ω)算法。输入gp、接收者的公钥pkR、云服务器的公钥pkS以及关键字ω,由发送者输出关键字ω的可搜索密文C。

3)Trapdoor(gp,skR,ω)算法。输入gp和接收者的私钥skR,由接收者输出关键字ω的陷门Tω。

4)Test(gp,skS,C,Tω)算法。输入gp、关键字密文C和关键字陷门Tω,云服务器利用自身私钥对密文和陷门进行匹配验证,如果匹配则输出1,否则输出0。

1.5 陷门不可区分性

为避免关键字猜测攻击,在设计方案时要保证关键字密文和陷门的不可区分性。本节只给出陷门不可区分性的安全性定义,其他可参考文献[18]。根据文献[20]提出的陷门不可区分性概念及安全模型,假设敌手A为外部攻击者(不是服务器和接收者),关键字陷门的不可区分性通过多项式时间的挑战者B与敌手A之间交互游戏来描述,具体过程如下:

1)Setup。给定安全参数λ,挑战者B生成全局参数gp、云服务器和接收者的公私钥对(pkS,skS)和(pkR,skR),并将gp、pkR和pkS发送给敌手A。

2)Queryphase1。敌手A可适应性的询问如下预言机OT,访问次数以多项式时间限定:

(1)搜索陷门预言机OT。输入接收者的私钥skR和选择的关键字ω∈KSω,OT预言机返回关键字陷门Tω←Trapdoor(gp,skR,ω)给敌手A。

(2)Challenge。一旦敌手A决定Queryphase1结束,A选择未询问过OT预言机的关键字(ω0,ω1),并将其发送给挑战者B。挑战者B随机选择b∈{0,1},计算关键字ωb对应的陷门Tωb←Trapdoor(gp,skR,ωb)并返回给敌手A。

3)Queryphase2。敌手A可以继续访问OT预言机,但要求不能就关键字(ω0,ω1)对预言机OT进行询问。

4)Guess。敌手A猜测b′,如果b′=b,则敌手A获胜,否则敌手A失败。

2 可搜索加密方案分析

本节主要对文献[11,18]分别提出的2个基于合数阶双线性对的公钥可搜索加密方案进行分析。上述方案对关键字陷门的设计均无法保证关键字陷门不可区分性,存在安全问题。

2.1 文献[11]方案分析

文献[11]方案的安全性主要基于合数阶双线性群的子群不可区分性,该方案具有IND-CKA安全性,方案具体设计可参考文献[11],下文对其中的Setup算法和Trapdoor算法进行阐述。

对文献[11]方案的安全性分析如下:

假设存在1个外部攻击者A,给定2个关键字(ω0,ω1),且A可获取包含目标关键字ωb∈{ω0,ω1}的陷门Tωb=[T1,T2]=[gα(uωbh)rR3′,grR3],外部攻击者A可通过以下攻击方式来区分该陷门中的关键字:

1)外部攻击者A通过系统参数gp={G,GT,e,N,u,g,h,e(g,g)α}获取u、g、h的值。

2)A随机选择ω′∈{ω0,ω1},并计算得到:

(4)

3)若ωb=ω′,则M=e(g,g)α,由于e(g,g)α已知,外部攻击者A可不通过验证测试算法就能区分并获取陷门中的关键字,因此该方案不满足陷门的不可区分性。

2.2 文献[18]方案分析

文献[18]提出在标准模型下利用合数阶双线性对的SCF-PEKS方案,该方案具有安全性和高效性,且主要基于判定性子群假设和DBDH假设,方案具体设计可参考文献[18],以下对其中的Setup算法、SCF-PEKS算法和Trapdoor算法进行阐述。

3)Trapdoor(gp,skR,ω)算法。接收者确认关键字后,随机选取R3∈Gp3,计算Tω=u1/(y+ω)R3,返回Tω。

对文献[18]方案的安全性分析如下:

由于该方案在无安全信道的环境下传送关键字陷门,因此陷门很容易被攻击者获取,且攻击者只需按如下攻击方式进行计算,便可轻易区分并获取陷门中的关键字,具体攻击过程为:

1)给定2个关键字(ω0,ω1),假设存在1个外部攻击者A,将包含目标关键字ωb∈{ω0,ω1}的陷门Tωb=u1/(y+ωb)R3发送给A。

3)A随机选择ω′∈{ω0,ω1},并计算得到:

(5)

4)若ωb=ω′,则M=e(u,g1),由于e(u,g1)在pkR中已知,攻击者A可区分陷门中的关键字,因此该方案不满足陷门的不可区分性。

3 SCF-PEKS改进方案

针对文献[11]和文献[18]方案存在的安全问题,本文提出一种改进的基于合数阶双线性对的无安全信道可搜索公钥加密方案,该方案可保证关键字陷门的不可区分性,且能抵抗外部关键字猜测攻击。

3.1 本文方案设计

本文方案由4个算法组成,其中Setup(λ)算法、SCF-PEKS(gp,pkS,pkR,ω)算法与文献[18]方案中算法一致,另外改进的2个算法具体如下:

2)Test(gp,Tω,C,skS,ω)算法。服务器先使用自身私钥计算t=H(e(U,h)x)和n=H(e(T1,h)x),再检验e(Vt,T2)=Wn是否成立。若等式成立,则输出1,否则输出0。

对本文方案的正确性证明如下:

(6)

(7)

(8)

由式(6)～式(7)可知,服务器通过自身私钥可计算出正确的t和n,将其代入式(8)计算得知,陷门和可搜索密文能够正确匹配,从而证明了本文方案具有正确性。

本文方案主要在生成陷门的Trapdoor算法基础上进行重新设计。根据上述分析,改进方案在生成陷门时增加1个n次幂,其中n=H(e(X,h)z),z为随机值。从而保证陷门即使在被攻击者获取的情况下,也无法通过计算区分出关键字,且必须计算出n值才能进行验证操作,虽然增加了计算量,但是可保证关键字陷门的不可区分性。采用对文献[18]方案相同的攻击方式对本文方案进行攻击,可以得到:

(9)

若ω′=ωb,则M=e(u,g1)n,此时对于外部攻击者而言,虽然e(u,g1)已知,但n值需要通过云服务器或接收者的私钥计算得到,攻击者无法通过M值判断ω′是否等于ωb,不能对陷门中的关键字进行区分,因此,本文方案能抵抗外部关键字猜测攻击。

3.2 安全性证明

本文主要证明改进方案关键字陷门的不可区分性,而由于可搜索密文的不可区分性等其他安全性基于判定性子群假设和DBDH假设,因此本文安全性证明过程与文献[18]中的安全性证明过程基本一致,具体可参考文献[18]。

定理1如果DBDH假设是困难的,那么对于任意概率多项式时间算法的敌手A,能区分关键字陷门的概率优势可忽略。

敌手A和挑战者B进行游戏如下:

4)Guess。敌手A输出猜测b′。在验证过程中,当b′=b时,n=H(e(T1,h)a)=H(e(g1,g1)abc),T=e(g1,g1)abc,则Tω*为合法输出,返回1;当b′≠b时,T≠e(g1,g1)abc,则T是GT中随机元素,返回0。

如果敌手A能区分陷门中的关键字,那么挑战者B便可攻破DBDH假设。因此,本文方案的关键字陷门具有不可区分性,可抵抗外部攻击者的关键字猜测攻击。

3.3 性能比较

表1 本文方案与其他方案的性能对比

4 结束语

本文对传统基于合数阶双线性对的可搜索公钥加密方案进行研究,指出其中陷门算法不具有关键字不可区分的安全属性,并提出一种改进的基于合数阶双线性对的可搜索加密方案。该方案在陷门、密文尺寸及计算复杂度与原方案接近的情况下,可保证关键字陷门的不可区分性,从而抵抗外部关键字猜测攻击。关键字猜测攻击较多由外部攻击者发起,如果由内部攻击者(恶意服务器)发起猜测攻击,则更容易造成数据泄露。后续将在本文对外部关键字猜测攻击研究的基础上,继续对合数阶双线性对进行改进,以抵抗内部关键字猜测攻击并提高计算效率。