2015, Vol. 26
2 广州大学 计算机科学与教育软件学院, 广东 广州 510006;
3 中国民航大学 信息安全评测中心, 天津 300300
2 School of Computer Science and Educational Software, Guangzhou University, Guangzhou 510006, China;
3 Information Security Evaluation Cener of Civil Aviation, Civil Aviation University of China, Tianjin 300300, China
可搜索加密问题源于文献[1]:假设用户Alice试图将个人文件存放在一个诚实但具有好奇心的外部服务器,以降低本地资源开销.为保护文件隐私,须采用某种加密方式将文件加密后存储.使用传统分组密码,只有密钥拥有者才具备解密能力,意味着Alice在执行基于关键词的查询操作时,需要下载所有已上传的文件,完全解密后再检索,会带来两个问题:① 如果Alice在服务器上已存有大量文件,一一下载会占用大量网络带宽,可能造成服务器堵塞;② 对已下载的所有文件完全解密会占用大量本地计算资源,效率极低.
解决此类问题的加密技术称为可搜索加密(searchable encryption,简称SE),该技术要求只有合法用户才具备基于关键词检索的能力.随着研究的推进,其应用并不仅限于此:2004年,Boneh提出使用非对称可搜索加密(asymmetric searchable encryption,简称ASE)解决“不可信赖服务器路由”问题[2];最近兴起的云计算[3]将是SE的最佳应用平台,由于服务提供商的不可控性,用户必须应对存储到云端的个人数据可能泄密的威胁,SE提供的加密和密文直接检索功能使服务器无法窃听用户个人数据,但可以根据查询请求返回目标密文文件,这样既保证了用户数据的安全和隐私,又不会过分降低查询效率.
本文关注近年来可搜索加密的研究进展,描述了可搜索加密基本问题的研究历史,并围绕定义、典型构造和扩展研究,分别对对称和非对称密码体制下的可搜索加密研究成果进行综述,最后展望了可搜索加密未来的研究方向,以期对其在国内的研究起到一定的推动作用.
1 可搜索加密 1.1 可搜索加密过程如图 1所示,可搜索加密可分为4个子过程:
 | Fig. 1 Steps in searchable encryption图 1 可搜索加密过程 |
Step 1. 加密过程.用户使用密钥在本地对明文文件进行加密,并将其上传至服务器.
Step 2. 陷门生成过程.具备检索能力的用户,使用密钥生成待查询关键词的陷门,要求陷门不能泄露关键词的任何信息.
Step 3. 检索过程.服务器以关键词陷门为输入,执行检索算法,返回所有包含该陷门对应关键词的密文文件,要求服务器除了能知道密文文件是否包含某个特定关键词外,无法获得更多信息.
Step 4. 解密过程.用户使用密钥解密服务器返回的密文文件,获得查询结果.
1.2 研究历史可搜索加密问题的提出,源于解决两类可搜索加密的基本问题:① 不可信赖服务器的存储问题;② 不可信赖服务器的路由问题.
1.2.1 不可信赖服务器存储问题的相关研究不可信赖服务器的存储问题最早提出于2000年[1],Song等人[1]提出了基于密文扫描思想的SWP方案,将明文文件划分为“单词”并对其分别加密,通过对整个密文文件扫描和密文单词进行比对,就可确认关键词是否存在,甚至统计其出现的次数.Goh[4]提出了基于索引的Z-IDX方案,使用布隆过滤器(Bloom filter)作为单个文件的索引结构,将文件包含的关键词映射为码字存储于该文件的索引中,通过布隆过滤器的运算,就能判定密文文件是否包含某个特定关键词.Chang和Mitzenmacher[5]考虑了该可搜索加密基本问题的一个应用场景:用户通过个人电脑以密文形式存储文件至服务器,然后使用移动设备(例如手机等)检索服务器上的密文文件,并针对此应用提出PPSED(privacy preserving keyword searches on remoted encrypted data)方案.Curtmola[6]规范化了对称可搜索加密(symmetric searchable encryption,简称SSE)及其安全目标,提出能够在非自适应和自适应攻击模型下达到不可区分性安全的SSE-1和SSE-2方案.这里,SSE-1和SSE-2都基于“关键词-文件”索引构建思想,服务器只需O(1)时间即可完成检索操作.然而,执行文件的添加或删除操作需要重新构建索引,时间开销较大.
近年来,围绕基本SSE方案中仍然存在的一些需要解决的问题,学者们进行了广泛的研究,包括:(1) 如何对服务器存放的密文文件进行动态添加、更新或删除[7, 8, 9];(2) 如何对基本方案中“单个关键词精确匹配”查询方式进行扩展,以适应更广泛的查询需求[10, 11, 12, 13, 14, 15];(3) 如何对基本方案中“包含与不包含”查询模式进行优化,以进一步降低用户端筛选目标文件的计算量[16, 17, 18];(4) 如何应对在半可信且具有好奇心的威胁模型下,服务器并不总是诚实地计算并返回检索结果的情况[19,20].
1.2.2 不可信赖服务器路由问题的相关研究不可信赖服务器的路由问题源于文献[2]:Bob通过不可信赖邮件服务器向Alice发送包含某些关键词的邮件,要求服务器不能获取邮件内容和相关关键词信息,但需根据关键词将邮件路由至Alice的某个终端设备.例如,如果邮件的关键词为“urgent”,则服务器将邮件分配至Alice的手机,如果邮件的关键词为“lunch”,则服务器将邮件分配至Alice的电脑.Boneh等人[2]最早提出PEKS(public key encryption with keyword search)概念,并基于BF-IBE[21]构造了第一个PEKS方案BDOP-PEKS,安全性可归结为BDH(bilinear Diffie-Hellman)数学假设. Khader[22]基于K-resilient IBE构造KR-PEKS方案,在标准模型下达到IND-CKA安全.Crescenzo等人[23]提出基于二次剩余中二次不可区分性问题(quadratic indistinguishability problem,简称QIP)的PEKS方案.Abdalla等人[24]针对PEKS算法一致性定义缺陷,提出统计一致性(statistically consistency)和计算一致性(computationally consistency),并描述了从基于身份加密(identity-based encryption,简称IBE)到PEKS的一般变换算法IBE2PEKS.
文献[25, 26, 27]指出了当前PEKS的一个较为严重的安全隐患:由于关键词空间远小于密钥空间,而且用户通常仅检索一些常用关键词,攻击者可借此实施关键词猜测攻击(keyword guessing attack,简称KGA),进而证明了不存在满足算法一致性并且在KGA下是安全的PEKS方案.因此,抵御KGA意味着需对PEKS机制本身加以修改.鉴于此,Tang等人[28]提出PERKS(public-key encryption with registered keyword search)方案,要求接收者在初始化阶段注册关键词,并将产生的预标签(pre-tag)通过安全信道传递给发送者;Xu等人[29]提出PEFKS(public key encryption with fuzzy keyword search)方案,向不可信赖服务器提供模糊陷门以进行初次检索,对返回结果再在本地进行基于精确陷门的二次检索.这些方案都能抵御KGA.
近年来,关于PEKS的研究集中于:(1) 对基本PEKS方案的安全性加以完善,提高PEKS密文与邮件密文的耦合度[30, 31, 32, 33, 34, 35];(2) 扩展查询方式,适应更广泛的查询需求[36, 37, 38, 39];(3) 以实际背景为依托,探索满足高级应用需求的方案[40, 41, 42, 43].
2 可搜索加密的分类 2.1 应用模型分类如图 2所示,从当前的应用角度可将可搜索加密问题模型分为4类.
 | Fig. 2 Usage models classification in searchable encryption图 2 可搜索加密应用模型分类 |
1) 单用户(单服务器)模型.
用户加密个人文件并将其存储于不可信赖外部服务器,要求:① 只有该用户具备基于关键词检索的能力;② 服务器无法获取明文文件和待检索关键词的信息.文献[1]中的应用问题以及单用户模式的云存储服务都是单用户模型的实例.
2) 多对一(单服务器)模型.
多个发送者加密文件后,将其上传至不可信赖外部服务器,以期达到与单个接收者传送数据的目的.要求:① 只有接收者具备基于关键词检索的能力;② 服务器无法获取明文文件信息.需要指出的是,不同于单用户模型,多对一模型要求发送者和接收者不能是同一用户.文献[2]中的应用问题和具备简单共享机制的云存储服务都是多对一模型的实例.
3) 一对多(单服务器)模型.
与多对一(单服务器)模型类似,但为单个发送者将加密文件上传至不可信赖外部服务器,借此与多个接收者共享数据.该模型遵循着一种广播共享的模式,文献[7]中的研究问题是一对多模型的实例.
4) 多对多(单服务器)模型.
在多对一模型的基础上,任意用户都可成为接收者,其通过访问控制和认证策略以后,具备基于关键词的密文检索方式提取共享文件的能力.要求:① 只有合法用户(例如能够满足发送者预先指定的属性或身份要求)具备基于关键词检索的能力;② 服务器无法获取明文文件信息.该模型既是多对一模型的扩展,同时也是云计算中复杂共享机制的抽象,具备广阔的应用前景.
2.2 解决策略从密码构造角度可将SE问题模型的解决策略分为3类.
1) 对称可搜索加密,适用于单用户模型.
对称可搜索加密的构造通常基于伪随机函数,具有计算开销小、算法简单、速度快的特点,除了加解密过程采用相同的密钥外,其陷门生成也需密钥的参与.单用户模型的单用户特点使得对称可搜索加密非常适用于该类问题的解决:用户使用密钥加密个人文件并上传至服务器,检索时,用户通过密钥生成待检索关键词陷门,服务器根据陷门执行检索过程后返回目标密文.
2) 非对称可搜索加密,适用于多对一模型.
非对称可搜索加密使用两种密钥:公钥用于明文信息的加密和目标密文的检索,私钥用于解密密文信息和生成关键词陷门.非对称可搜索加密算法通常较为复杂,加解密速度较慢,然而,其公私钥相互分离的特点,非常适用于多用户体制下可搜索加密问题的解决:发送者使用接收者的公钥加密文件和相关关键词,检索时,接收者使用私钥生成待检索关键词陷门,服务器根据陷门执行检索算法后返回目标密文.该处理过程避免了在发送者与接收者之间建立安全通道,具有较高的实用性.
3) 对称可搜索加密或非对称可搜索加密,可解决一对多和多对多模型中的可搜索加密问题.
非对称可搜索加密本身即能有效地支持最基本形式的隐私数据的共享,通过共享密钥,其可被拓展到多对多的应用场景.对称可搜索加密虽然通常适用于单用户模型,但其由于计算开销小、速度快,更适合于大型文件数据的加密和共享,通过混合加密与基于属性加密技术相结合,或与代理重加密结合,也可用于构造共享方案.
鉴于对称和非对称可搜索加密作为基本工具,在解决实际可搜索加密问题时的重要性,本文接下来将围绕定义、构造和扩展研究,分别对对称和非对称可搜索加密的研究成果进行综述.
3 对称可搜索加密 3.1 定 义 3.1.1 算法描述定义1(对称可搜索加密). 定义在字典D={W1,W2,…,Wd}上的对称可搜索加密算法可描述为五元组:
SSE=(KeyGen,Encrypt,Trapdoor,Search,Decrypt),
其中,
1) K=KeyGen(l):输入安全参数l,输出随机产生的密钥K;
2) (I,C)=Encrypt(K,D):输入对称密钥K和明文文件集D=(D1,D2,…,Dn),DiÎ2D,输出索引I和密文文件集C=(C1,C2,…,Cn).对于无需构造索引的SSE方案(例如SWP方案[1]),I=Æ;
3) TW=Trapdoor(K,W):输入对称密钥K和关键词W,输出关键词陷门TW;
4) D(W)=Search(I,TW):输入索引I和陷门TW,输出包含W的文件的标识符构成的集合D(W);
5) Di=Decrypt(K,Ci):输入对称密钥K和密文文件Ci,输出相应明文文件Di.
如果对称可搜索加密方案SSE是正确的,那么对于"lÎ¥,n΢,WÎD,D=(D1,D2,…,Dn)以及KeyGen(l)和
Encrypt(K,D)输出的K和(I,C),都有Search(I,Trapdoor(K,W))=D(W)和Decrypt(K,Ci)=Di成立.
这里,CiÎC,i=1,2,…,n.
基于定义1,对称可搜索加密流程如下:加密过程中,用户执行KeyGen算法生成对称密钥K,使用K加密明文文件集D,并将加密结果上传至服务器.检索过程中,用户执行Trapdoor算法,生成待查询关键词W的陷门TW;服务器使用TW检索到文件标识符集合D(W),并根据D(W)中文件标识符提取密文文件以返回用户;用户最终使用K解密所有返回文件,得到目标文件.
3.1.2 安全目标在设计密码方案时,主要考虑可能面临攻击模型下需达到的安全目标,通常使用安全目标与攻击模型相结合的方式定义方案的安全性.早在2000年,Song等人[1]将可证安全理论的不可区分性安全目标引入可搜索加密机制,要求密文不会泄漏任何原始文件信息.然而,Song的原始定义并不足以描述攻击者在现实场景中所具备的可搜索攻击能力.针对此问题,Goh[4]提出了选择关键词攻击下的不可区分性安全目标IND-CKA,要求攻击者即使能够任意询问(或以黑盒方式产生)密文文件和关键词陷门,也无法获得比通过陷门检索方式更多的原始文件信息.进一步地,Chang等人[5]考虑攻击者在实施攻击时能够获得之前所有轮次服务器端的查询结果的情况,描述了可搜索加密机制基于模拟的安全性定义,以限制服务器除每一轮查询结果外,无法获得任何信息.
2006年,Curtmola等人[6]指出:① 文献[4]未明确考虑关键词陷门在可搜索加密机制中的安全性;② 文献[5]中的安全性定义无法描述具备自适应攻击能力的攻击者,且能够被任何可搜索加密方案平凡地(trivially)满足.Curtmola等人[6]进而在自适应(adaptive)和非自适应(nonadaptive)模型下形式化地定义了SSE的语义安全(semantic security,简称SS)和不可区分性安全(indistingsuishability,简称IND).描述安全目标之前,引入几个概念:
定义2. 假设D={W1,W2,…,Wd}表示关键词字典,D=(D1,D2,…,Dn)表示明文文件集合,W=(W(1),W(2),…,W(q))表示一组已查询关键词,这里,DiÎ2D,WiÎD.可定义如下概念:
1) q-查询历史H=(D,W),这里,|W|=q;
2) H的查询格式¶(H)=(D(W(1)),D(W(2)),…,D(W(q)));
3) H的检索格式s(H)为qxq矩阵,对于1≤i,j≤q,如果W(i)=W(j),那么第i行j列元素s(H)ij=1;否则,s(H)ij=0;
4) 攻击者关于H的视图定义为VK(H)=(I,C,T1,T2,…,Tq,id(D1),id(D2),…,id(Dn)),包括密钥K作用下产生的密文文件及其索引、历史查询关键词的陷门和一些额外信息,例如各文件标识符等;
5) H的轨迹t(H)=(|D1|,|D2|,…,|Dn|,¶(H),s(H)),包括H的查询格式、检索格式和D中各文件长度信息.
SSE安全目标的定义源于攻击者和挑战者的博弈过程:挑战者首先执行KeyGen算法产生对称密钥K,并按
照如图 3所示的某种方式(在图 3(b)和图 3(d)中,S(×)为模拟算法,可根据历史的轨迹模拟产生密文文件集及其索
 | Fig. 3 Games in SSE security notions图 3 SSE安全目标中的博弈过程 |
引),根据秘密产生的随机参数b响应攻击者的询问,最后,由攻击者通过计算输出一个判定值b¢作为对b的猜测:
如果b¢=b,判定成功;否则失败.因此,可定义攻击者A在相应安全目标下的攻击优势为AdvSSE(A)=|2×Pr[b¢=b]-1|.如果对任意A和e>0,都有AdvSSE(A)<e,那么对称可搜索加密算法SSE达到了相应的安全目标.
自适应和非自适应模型下的安全目标之间的关系如图 4所示.
 | Fig. 4 Relation of security goals under adaptive and nonadaptive attack model图 4 自适应和非自适应模型下安全目标间的关系 |
图 4中,箭头表示能推导出.通过图 4可以看出:
· 非自适应攻击模型下,SS-Nonadaptive和IND-Nonadaptive相互等价,即,达到SS-Nonadaptive安全的SSE同时也达到IND-Nonadaptive安全;反之亦然;
· 自适应攻击模型下,SS-Adaptive安全能够推导出IND-Adaptive安全,因此,SS-Adpative比IND- Adaptive具备更高的安全度.
3.2 典型构造SSE典型构造方式包括SWP方案[1]、Z-IDX方案[4]和SSE-1方案[6].本节从构造角度对3种典型方案的加密过程进行综述.由于Z-IDX和SSE-1采用基于索引的加密,对数据文件本身采用传统分组密码直接加密即可,因此,这里只详细介绍这两种方法的索引构建过程.
3.2.1 SWP方案SWP方案[1]在预处理过程中根据文件长度产生伪随机流S1,S2,…,Sn(n为待加密文件中“单词”个数),然后采用两个层次加密:在第1层,使用分组密码E逐个加密明文文件单词;在第2层,对分组密码输出E(K¢,Wi)进行处理:① 将密文等分为Li和Ri两部分;② 基于Li生成二进制字符串Si||F(Ki,Si),这里,Ki=f(K²,Li),||为符号串连接,F和f为伪随机函数;③ 异或E(K¢,Wi)和Si||F(Ki,Si)以形成Wi的密文单词.
查询文件D中是否包含关键词W,只需发送陷门TW=(E(K¢,W),K=f(K²,L))至服务器(L为E(K¢,W)的左部),服务器顺序遍历密文文件的所有单词C,计算C XOR E(K¢,W)=S||T,判断F(K,S)是否等于T:如果相等,C即为W在D中的密文;否则,继续计算下一个密文单词.
SWP方案[1]通过植入“单词”位置信息,能够支持受控检索(检索关键词的同时,识别其在文件中出现的位置).例如,将所有“单词”以W||a形式表示,a为W在文件中出现的位置,仍按图 5所示加密,但查询时可增加对关键词出现位置的约束.SWP方案[1]存在一些缺陷:① 效率较低,单个单词的查询需要扫描整个文件,占用大量服务器计算资源;② 在安全性方面存在统计攻击的威胁.例如,攻击者可通过统计关键词在文件中出现的次数来猜测该关键词是否为某些常用词汇.
 | Fig. 5 SWP scheme图 5 SWP方案 |
Z-IDX[4]方案使用布隆过滤器作为文件索引,以高效跟踪文件中的关键词.布隆过滤器由二进制向量Mem(假设为m位)和哈希函数族{h1(×),h2(×),…,hr(×)}(hi:{0,1}®{1,2,…,m},i=1,2,…,r)组成,用于判断某元素是否存在于某集合中.例如,对集合S,初始时刻,Mem所有比特位置0.以后,对每个元素sÎS,置Mem[h1(s)],Mem[h2(s)],…,Mem[hr(s)]为1.因此,为确定待判断元素a是否属于S,只需检查比特位Mem[h1(a)],Mem[h2(a)],…,Mem[hr(a)],如果所有比特位都为1,则a属于S;否则a不属于S.
Z-IDX[4]构建索引的过程如图 6所示,关键词通过两次伪随机函数作用形成码字存储于索引中,第1次伪随机函数以关键词Wi为输入,分别在子密钥K1,K2,…,Kr作用下生成xi1,xi2,…,xir;第2次伪随机函数分别以xi1,xi2,…,xir为输入,在当前文件标识符id作用下生成码字yi1,yi2,…,yir,确保了相同关键词在不同文件中形成不同码字.另外,在布隆过滤器中加入混淆措施(随机添加若干个1)预防了针对关键词数目的攻击.
 | Fig. 6 Z-IDX scheme图 6 Z-IDX方案 |
判断文件Did(id为该文件的标识符)中是否包含关键词Wi:① 用户使用密钥K=(K1,K2,…,Kr)生成Wi的陷门Ti=(xi1,xi2,…,xir),这里,xij=f(Kj,Wi),j=1,2,…,r;② 服务器基于Ti生成Wi的码字(yi1,yi2,…,yir),这里,yij=f(id,xij),j=1,2,…,r;③ 服务器判断Did的索引Memid的yi1,yi2,…,yir位是否全为1:若是,则WiÎDid;否则,Did不包含Wi.
Z-IDX[4]存在一些不足:
(1) 空间代价上,服务器除存储密文文件本身外,还需记录文件索引,当文件较短时,其索引可能是文件长度的数倍,空间利用率较低.文献[4]给出一个例子,只包含一个单词且长度为9字节的文件,加密后的索引却为90字节;
(2) 时间代价上,服务器检索需逐个文件地计算和判断,整个关键词查询操作时间消耗为O(n)(n为服务器上存储文件数目),效率较低.
3.2.3 SSE-1方案SSE-1[6]为支持高效检索,引入额外数据结构:对任意关键词WÎD:① 数组A存储D(W)的加密结果;② 速查表T存储W的相关信息,以高效定位相应关键词信息在A中的位置.
SSE-1[6]构建索引过程如下所示(图 7描述了一个采用SSE-1方案构建仅包含一个关键词索引的实例,其中,SKE为使用的底层对称加密算法):
 | Fig. 7 SSE-1 scheme图 7 SSE-1方案 |
1) 构建数组A
初始化全局计数器ctr=1,并扫描明文文件集D,对于WiÎD,生成文件标识符集合D(Wi),记id(Dij)为D(Wi)中字典序下第j个文件标识符,随机选取SKE的密钥Ki0Î{0,1}l(这里,l为安全参数),然后按照如下方式构建并加密由D(Wi)中各文件标识符形成的链表:
,随机选取SKE密钥KijÎ{0,1}l,并按照“文件标识符||下一个节点解密密钥||下一个节点在数组A的存放位置”这一形式创建链表LWi的第j个节点.
Nij=id(Dij)||Kij||y(K1,ctr+1).
这里,K1为SSE-1的一个子密钥,y(×)为伪随机函数.使用对称密钥Ki(j-1)加密Nij并存储至数组A的相应位置,即
A[y(K1,ctr)]=SKE.Encrypt(Ki(j-1),Nij);而对于j=|D(Wi)|,创建其链表节点
并加密存储至数组
;最后,置ctr=ctr+1.
2) 构建速查表T
对于所有关键词WiÎD,构建速查表T以加密存储关键词链表LWi的首节点的位置及密钥信息,即:
T[p(K3,Wi)]=(addrA(Ni1)||Ki0) XOR f(K2,Wi).
这里,K2和K3为SSE-1的子密钥,f(×)为伪随机函数,p(×)为伪随机置换,addrA(×)表示链表节点在数组A中的地址.
检索所有包含W的文件,只需提交陷门
至服务器,服务器使用
在T中找到W相关链表首节点的间接地址
,执行
,a为LW首节点在A中的地址,K¢为首节点加密使用的对称密钥.由于在LW中,除尾节点外所有节点都存储下一节点的对称密钥及其在A中的地址,服务器获得首节点的地址和密钥后,即可遍历链表所有节点,以获得包含W的文件的标识符.
SSE-1[6]避免了关键词查询过程中逐个文件进行检索的缺陷,具备较高的效率.然而,由于SSE-1需构建关键词相关链表,并将其节点加密后存储至数组A,意味着现有文件的更新删除或新文件的添加需重新构建索引,造成较大开销.因此,SSE-1更适用于文件集合稳定,具有较少文件添加、更新和删除操作的情况.
3.3 构造特点 3.3.1 方案构建策略分析以上3种典型构造代表两类SSE构建策略.
1) 基于顺序扫描的SSE构建策略
SWP方案[1]采用顺序扫描的构建策略,其特点是将明文文件划分为若干个“单词”,对“单词”逐词加密,检索时顺序扫描整个密文文件,寻找与待检索单词匹配的密文单词.逐词加密和全文扫描的特点,使该策略具备如下优点:① 支持对文件中任意单词的检索;② 支持受控检索.然而,该策略要求服务器检索需遍历整个文件,时间复杂度为O(ns)(n为服务器上存储的文件数目,s为文件平均长度),效率极低.目前,效率是阻碍顺序扫描构建策略在SSE方案中广泛应用的关键问题.
2) 基于索引的SSE构建策略
Z-IDX[4]和SSE-1[6]采用基于索引的构建策略,其特点是将SSE方案的构造直接划分为两个子过程:构建索引和加密文件.加密文件用于保护不可信赖服务器上用户数据的隐私,通常采用AES直接加密即可;构建索引用于实现对密文文件的高效关键词查询.然而,由于索引存储在服务器端,可能作为服务器窃听用户数据的工具,传统的文件索引并不适用,这里的索引通常为加密索引.构建索引的特点,使该策略能够以较高效率支持关键词查询操作.目前,几乎所有SSE方案都采用基于索引的构建策略.
3.3.2 索引构建思想分析设计基于索引的SSE方案的关键在于索引的构建,Z-IDX[4]和SSE-1[6]采用了两种截然不同的索引构建思想:① Z-IDX[4]采取的是“文件-关键词”索引构建思想,构造以文件为基本单位的数据结构(Z-IDX[4]中为布隆过滤器),检索时,通过该数据结构的操作判断待检索关键词是否存在于某个文件中;② SSE-1[6]采取的是“关键词-文件”索引构建思想,构造以关键词为基本单位的数据结构(这里为链表),检索时,通过该数据结构找到包含待检索关键词的所有文件.
这两种构建思想已被广泛应用于SSE方案构造中,目前,几种主要基于索引的SSE方案及其采用的索引构建思想见表 1.
由表 1可知:在这两种索引构建思想下,操作处理基本单位的不同,决定了方案在完成操作时效率上的差异.
|
Table 1 Index-Based SSE scheme 表 1 基于索引的SSE方案 |
1) 采用“文件-关键词”构建思想的SSE方案以文件为基本单位,使其在文件更新(该操作以文件为基本单位)时,只需更新当前使用的数据结构,具有较高的效率.由于检索是以关键词为基本单位进行,要求服务器遍历所有文件的数据结构,花费O(n)时间(事实上,这里的时间还包含查询每个文件的数据结构,例如Z-IDX[4]对每个文件的判断还需r次伪随机函数作用),效率较低.
2) 采用“关键词-文件”构建思想的SSE方案处理以关键词为基本操作单位的检索操作时,只需O(1)时间(若将所有文件读出,还需执行若干次索引解密操作,这里,次数与查找到的文件数目相关),具备较高的效率.由于文件更新的基本操作单位为文件,而该思想的基本构建单位为关键词,使得文件更新时,服务器需重新构建适应更新后状态以关键词为基本单位的索引,造成较大开销.
3.4 扩展研究近年来,SSE的研究集中于对基本方案的功能扩展和安全性优化上,本节将总结SSE在这些方面的相关研究进展情况.
3.4.1 密文文件动态更新基于“关键词-文件”思想的构建方案具有较高的查询效率,但在处理文件更新时,需重建索引;基于“文件-关键词”思想的构建方案具有较高的文件更新效率,但查询速度较慢.如何将这两者的优势结合起来,以同时支持高效的查询和文件更新,是研究者长期关注的一个问题.
最早关于密文文件动态更新的尝试始于文献[7],Van Liesdonk等人[7]提出了两个新型SSE方案:方案1具有较低的计算复杂度,但关键词检索和文件更新过程要求服务器与客户端两次交互,占用了较大的网络带宽;方案2只需一次交互即可完成检索等操作,但由于使用了哈希函数链,文件更新时的计算复杂度与总更新次数呈线性关系.
直到2012年,Kamara等人[8]才首次提出了支持子线性时间内的关键词检索和密文文件的高效动态更新的动态SSE方案.Kamara等人[8]的方案基于了SSE-1[7](重定义了SSE-1中的数组和速查表为检索数组As和检索速查表Ts),并结合“文件-关键词”的索引构建思想,引入额外的删除数组Ad和相应的速查表Td以记录和追踪每个文件中包含的关键词.当需要进行远端文件的添加或删除时,用户发送相应的标记(token)至服务器,服务器利用这些标记更新相关数据结构和密文文件.最近,Kamara等人[9]引入红黑树作为索引结构,使动态SSE能够支持多处理器并行处理.
3.4.2 查询方式扩展SSE查询方式扩展包括对以逻辑连接词连接的多个关键词的检索和模糊关键词检索.
3.4.2.1 多关键词检索如何对以逻辑连接词连接的多个关键词进行检索,是一个有趣的问题.早期的SSE方案[1]大多采用:① 分别检索关键词组中的每个关键词,再根据逻辑连接词对各自检索结果进行后处理;② 为所有可能的多关键词检索组合设置元关键词(meta-keyword),并与相关文件关联(例如对于关键词Bob,urgent和finance,可设置元关键词Bob:urgent:finance,并与所有包含Bob,urgent和finace的文件关联).然而,方法①使服务器获得比检索结果更多的额外信息,例如,服务器能够知道某些单个关键词包含于哪些密文文件;方法②造成服务器存储量的指数级增长,例如,具有m个不同关键词的文件集合D,可能需要为其设置2m个元关键词以适应不同查询组合.
因此,迫切需要探索一种多关键词检索的直接实现方案,文献[10]最早研究了此类问题.目前,关于多关键词检索的研究大多集中于对“逻辑与”连接词的支持上,表 2列出了当前主要多关键词检索方案.
|
|
Table 2 Multi-Keywords search scheme 表 2 多关键词检索方案 |
效率方面,GSW-1[10]和SCKS-SS[11]具有明显优势,无需双线性对运算,只通过简单的指数运算和伪随机函数作用即可完成多关键词检索的过程.然而传送陷门时,这两种方案都需O(n)通信量,造成网络负载过重;
安全性方面,这些多关键词检索方案的安全性通常依赖于某种数学难题,所依赖的数学难题的强弱也反映了方案安全性的高低.
3.4.2.2 模糊关键词检索原有的SSE方案由于缺乏对细微文字以及格式错误的容忍,使其无法适用于云计算.鉴于此,文献[13]提出了模糊关键词检索的方案.该方案中,采用编辑距离来定义和度量关键词间的相似度,并使用了基于通配符和基于克(gram)的两种模糊关键词集构造方法.关键词查询时,用户计算待查询关键词在编辑距离门限下的模糊陷门集合并交给服务器,服务器使用陷门集与存储的模糊关键词集进行一一匹配,返回可能包含W的密文文件集合.2012年,Wang等人[14]进一步研究模糊关键词检索方案,并给出了形式化的安全性证明.
文献[15]提出包含通配符的关键词检索方法,类似于Z-IDX[4],也将文件包含的关键词插入布隆过滤器.所不同的是,为避免关联攻击,该方法产生基于文件标识符的伪随机数,用以对布隆过滤器的二进制向量进行遮蔽.最后,在包含通配符的关键词检索功能的实现上,该方法通过预先为关键词生成所有通配检索形式(例如,关键词flower的所有通配检索形式包括flower,*flower,flower*,*lower,…,flowe*,*ower,…,flow*,*wer,f*er,fl*r,flo*,*er,f*r,fl*,*r,f*等),插入索引,从而将包含通配符的关键词检索转化为精确匹配检索.
3.4.3 查询结果优化原有的SSE方案仅支持布尔检索(即,判断某个关键词是否存在于文件中)而不能追踪关键词与文件的相关度.对于查询返回结果,用户必须进行后处理:解密所有返回文件,以获取目标文件.然而,相对于返回结果,目标文件可能只是其中单个或极少一部分,这就导致大量不必要的解密操作.因此,迫切需要优化查询结果,降低用户端后处理工作开销.
一种可能的优化办法是:在返回结果中,按照关键词与文件的相关度对加密文件进行排序,并将排序结果返回给用户.这样,用户只需根据相关度解密少量密文即可获得目标文件.目前,关于此方面的研究包括:
1) 文献[16]提出保护隐私的排序检索算法,采用保序加密算法加密文件中关键词词频.关键词查询时,首先检索出包含关键词的密文文件;然后,对用保序算法加密的词频对应的密文信息进行排序处理;最后,将相关度高的密文文件返回给用户.
2) 文献[17]提出云计算环境下的排序检索方案,对于每个关键词W,计算其与被包含文件D的相关度,并使用一对多保序映射加密后,作为文件D节点的部分信息插入倒排链接索引表.关键词检索时,服务器通过陷门找到包含W的密文文件及其与W的相关度顺序,返回给用户.
3) 文献[18]提出支持多关键词查询的排序检索算法MRSE.该方案为每个文件Di分配|D|二进制向量Ai,并以Ai[j]描述关键词Wj是否存在于文件Di中,这里,D为由所有关键词构成的字典;然后,采用增维、分割的方法生
成|D|+1维向量
和
,最后形成Di的索引
.这里,M1,M2均为(|D|+1)x(|D|+1)维矩阵密钥.关键词查询时,生成|D|维查询向量Q,并类似地对Q进行增维、分割处理,形成陷门
.服务器遍历所有文件,计算Ii×T后对结果排序返回.
Chai考虑半可信且好奇(semi-honest-but-curious)模型下,服务器可能为了节省其计算量或者下载带宽而返回错误的搜索结果或者部分搜索结果.为抵抗这种攻击,Chai[19]提出了可验证的对称可搜索加密方案(verifiable symmetric searchable encryption,简称VSSE),其中引入了基于哈希的检索树,要求服务器将检索路径的哈希序列作为证据一并返还给用户,用户可根据证据对服务器的检索结果进行完整性和正确性验证.Kurosawa等人[19]进一步形式化地定义了SSE的隐私性和可靠性,证明了其与UC(universal composability)安全性的等价性,并提出了满足检索结果可验证性的SSE构造方案.
4 非对称可搜索加密本节将围绕定义、典型构造思想和应用扩展,对非对称可搜索加密研究成果进行综述,并分析总结其特点.
4.1 定 义 4.1.1 算法描述Boneh等人[2]在非对称密码体制中引入可搜索加密,提出PEKS(public key encryption with keyword search)概念,算法描述如下.
定义3(PEKS). 非对称密码体制下可搜索加密算法可描述为PEKS=(KeyGen,Encrypt,Trapdoor,Test):
1) (pk,sk)=KeyGen(l):输入安全参数l,输出公钥pk和私钥sk;
2) CW=Encrypt(pk,W):输入公钥pk和关键词W,输出关键词密文CW;
3) TW=Trapdoor(sk,W):输入私钥sk和关键词W,输出陷门TW;
4) b=Test(pk,CW,TW¢):输入公钥pk、陷门TW¢和关键词密文CW,根据W与W¢的匹配结果,输出判定值bÎ{0,1}.
基于定义2,Boneh等人[2]提出不可信赖服务器路由问题的解决思路:Bob使用Alice的公钥pk加密邮件和相关关键词,并将形如(PKE.Encrypt(pk,MSG),PEKS.Encrypt(pk,W1),…,PEKS.Encrypt(pk,Wn))的密文发送至邮件服务器.这里,PKE.Encrypt为公钥密码加密算法,MSG为邮件内容,W1,…,Wn为与MSG关联的关键词.Alice将T“urgent”或T“lunch”长驻服务器,新邮件到来时,服务器自动对其关联的关键词执行与T“urgent”或T“lunch”相关的Test算法,如果输出1,便将该邮件转发至Alice的手机或个人电脑.
4.1.2 算法一致性加密算法的一致性是指解密与加密互为逆过程,即,对任意明文M,使用公钥pk加密后得到密文C,如果再使用pk对应的私钥sk解密,必能得到M.PEKS的一致性应满足:① 对任意关键词W,Pr[Test(pk,PEKS(pk,W),Trapdoor(sk,W))=1]=1;② 对任意关键词W1,W2且W1¹W2,Pr[Test(pk,PEKS(pk,W1),Trapdoor(sk,W2))]=1]=0.文献[2]中的方法无法满足上述要求[24],鉴于此,Abdalla等人[24]对如上所述的完美一致性进行扩展,定义针对PEKS的计算一致性和统计一致性.
计算一致性和统计一致性的定义都基于实验Expconsist.攻击者A已知公钥pk,其目标是通过一定次数访问随机预言机OH(×)后(OH(×)以PEKS中使用的哈希函数H(×)响应A的查询),输出关键词对(W1,W2),满足W1¹W2且Test(pk,PEKS(pk,W1),Trapdoor(sk,W2))=1.A具有攻击优势
:
(1) 如果A为任意攻击者且
则该PEKS方案达到统计一致性;
(2) 如果A为任意多项式时间攻击者且,则该PEKS方案达到计算一致性.
PEKS需要满足:① 没有陷门的服务器除文件长度外,无法获取任何文件信息;② 拥有陷门TW的服务器能够检索到所有包含W的密文文件.基于此,文献[2]定义了PEKS在选择关键词攻击下的不可区分性安全:IND- CKA(indistinguishability under chosen keyword attack).如图 8所示,IND-CKA的定义基于实验ExpIND-CKA,挑战者C执行KeyGen算法生成公钥pk和私钥sk,将pk交给攻击者A.A在自适应查询若干次陷门预言机OTrapdoor(×)后,输出关键词对(W0,W1).C随机选取bÎ{0,1},生成挑战密文C*=Encrypt(pk,Wb).A的目标是:在再次查询若干次陷门预言机OTrapdoor(×)后,输出判定值b¢,如果b¢=b攻击成功,否则失败.A的攻击优势为
 | Fig. 8 Games in PEKS security notions 图 8 PEKS安全目标中的博弈过程 |
PEKS和IBE(完整定义可参考文献[21])都具有“判定”的共性:
· PEKS使用Test算法判定陷门是否与某个关键词密文匹配;
· IBE通过Decrypt算法进行判定:解密的私钥与加密的身份匹配时才能成功解密.
鉴于此种内在共性,探索PEKS与IBE的联系,并从中挖掘构建思想,成为众多研究者关注的热点.
Boneh等人[2]使用IND-CKA安全的PEKS方案构造出明文空间M={0,1},并达到IND-ID-CCA(idistinguishability under identity-chosen ciphertext attack)安全的IBE方案.
假设采用的PEKS方案为PEKS=(KeyGen,Encrypt,Trapdoor,Test),则构造的IBE方案IBE=(Setup,Extract,Encrypt,Decrypt)可描述如下:
1) (param,mk)=IBE.Setup(1l):输入安全参数1l,输出系统参数和主密钥(param,mk)=PEKS.KeyGen(1l);
2) skid=IBE.Extract(param,mk,id):输入系统参数param、主密钥mk和身份idÎ{0,1},输出私钥:
skid=(Tid||0,Tid||1)=(PEKS.Trapdoor(mk,id||0),PEKS.Trapdoor(mk,id||1));
3) Y=IBE.Encrypt(param,id,X):输入系统参数param、身份idÎ{0,1}和明文XÎ{0,1},输出密文:
Y=PEKS.Encrypt(param,id||X);
4) X=IBE.Decrypt(param,skid,Y):输入系统参数param、私钥skid=(Tid||0,Tid||1)和密文Y:
Ø 如果Test(param,Tid||0,Y)=1,输出0;
Ø 如果Test(param,Tid||1,Y)=1,输出1.
相反地,Abdalla等人[24]描述了从IBE到PEKS的一般变换算法,能够将IND-CPA(indistinguishability under chosen plain attack)和ANO-CPA(anonymity under chosen plain attack)安全的IBE方案变换为IND-CKA安全,并满足计算一致性的PEKS方案.
假设采用的IBE方案为IBE=(Setup,Extract,Encrypt,Decrypt),则构造的PEKS方案PEKS=(KeyGen,Encrypt,
Trapdoor,Test)可描述如下:
1) (pk,sk)=PEKS.KeyGen(1l):输入安全参数1l,输出公钥和私钥(pk,sk)=IBE.Setup(1l);
2) CW=PEKS.Encrypt(pk,W):输入公钥pk和关键词W,随机选择明文MÎ{0,1}l,执行IBE加密算法产生C=IBE.Encrypt(pk,W,M),输出关键词密文CW=(C,M);
3) TW=Trapdoor(sk,W):输入私钥sk和关键词W,输出陷门TW=IBE.Extract(pk,sk,W);
4) b=PEKS.Test(pk,TW¢,CW):输入公钥pk、陷门TW¢和关键词密文CW=(C,M):
Ø 如果IBE.Decrypt(param,TW¢,C)=M,输出1;
Ø 否则,输出0.
4.2.2 典型构造目前的PEKS方案包括BDOP-PEKS[2],KR-PEKS[22]和DS-PEKS[23],都基于某种IBE,它遵循一类最基本的PEKS构建策略,即:通过已有IBE方案由IBE到PEKS的变换算法,以构造安全的PEKS.表 3从通信量、运算效率以及所基于的数学假设等方面对3种典型构造进行了对比.
|
|
Table 3 Typical PEKS schemes comparison 表 3 PEKS典型方案对比 |
由表 3可知:① BDOP-PEKS[2]拥有较低用户服务器通信量,但是,加密和检索时都需一次对运算,效率较低;② KR-PEKS[22]拥有较高服务器检索效率,然而由于该方案只能抵御至多k次恶意陷门查询,通常需将k设置为较大数值,这会导致服务器端存储量增长;③ DS-PEKS[23]拥有较短关键词密文长度,检索和加密效率也较高,但要求服务器和用户间的交互需要占用较大带宽.
事实上,由于PEKS方案都是基于某种已有IBE方案构造而成,因此,PEKS的性质也一定程度地反映了其源于IBE方案的性质.
4.3 关键词猜测攻击及其防御措施文献[2]定义了关于PEKS的IND-CKA安全目标,并认为达到该目标的PEKS方案都是安全的.但是PEKS本身定义存在严重的安全隐患:文献[25,26]构造了针对PEKS方案[2,30,32,36]的关键词猜测攻击,关键词猜测攻击是由于关键词空间远小于密钥空间,而且用户通常使用常用关键词进行检索,这就给攻击者提供了只需采用字典攻击就能达到目的的“捷径”.
导致关键词猜测攻击的原因可归结为:
(1) 关键词空间较小,且用户集中于使用常用词汇,给攻击者提供了遍历关键词空间的可能;
(2) PEKS算法一致性约束,使攻击者拥有对本次攻击是否成功的预先判定:执行Test算法,返回1说明本次攻击成功;否则,可以再继续猜测(该预先判定针对了实验ExpIND-CKA).
鉴于此:
1) 文献[28]提出了PERKS方案,要求接收者在预处理过程中执行关键词注册算法,将输出的预标签通过安全信道传送给发送者,发送者才能为注册后的关键词W生成密文CW.该方案实际上是对情形①的弥补,通过引入关键词注册过程,限制攻击者遍历关键词空间的能力.
2) 文献[29]提出了PEFKS方案,在服务器端进行模糊陷门测试,过滤大部分不相关邮件,最后在本地精确匹配,得到检索结果.该方案通过引入模糊陷门,一定程度地降低了接收者外部PEKS算法的一致性,使其能够抵御关键词猜测攻击,但增加了客户服务器通信量和用户端计算量.
4.4 扩展研究 4.4.1 安全性完善PEKS中,发送者将邮件以(PKE.Encrypt(pk,MSG),PEKS.Encrypt(pk,W))的形式通过服务器发送给接收者,安全要求仅考虑邮件密文中PEKS部分,而忽略整个系统(结合公钥密码和PEKS)的隐私性,使恶意攻击者可利 用PKE.Encrypt(pk,MSG)与PEKS.Encrypt(pk,W)的“间隙”实施某些攻击.例如:删除PKE.Encrypt(pk,MSG)的部分内容,使接收者无法获得完整邮件;将服务器上的两封密文邮件的PEKS部分交换位置,使接收者无法检索到期望的邮件等.
针对此问题,文献[30]提出了PKE/PEKS-1和PKE/PEKS-2方案,在加密过程中除执行PKE.Encrypt(pk,MSG)和PEKS.Encrypt(pk,W)外,额外生成标签s,用于邮件内容密文和关键词密文的相关性和完整性保护,只有在s是(PKE.Encrypt(pk,MSG),PEKS.Encrypt(pk,W))的合法标签时,才能进行测试.文献[31]在文献[30]的基础上提出了关于PKE/PEKS的新安全模型,增加对关键词隐私的要求,并描述了PKE/PEKS在标准模型下的一般构造框架.
另一方面,基本PEKS中,关键词陷门的传输需要在安全信道进行,否则,外部恶意攻击者能够通过公开信道截获和篡改陷门和查询结果.另外,某些恶意服务器也可以存储已查询的陷门与检索结果,以预测未来的查询结果.这就要求发送者预先指定服务器,在其上执行检索功能.
针对此问题,文献[32]提出了dPEKS方案,发送者在加密过程中使用接收者和服务器的公钥,使只有发送者指定的服务器才具备检索能力.该方案使用聚合技术,在随机预言机模型下可证安全.文献[33]定义了安全模型,描述了在具有恶意服务器和恶意接收者的内部攻击方式下dPEKS的安全目标.基于此,Rhee等人[33]提出了dPEKS方案,在随机预言机模型下可证安全.另外,关于dPEKS的研究还包括文献[34,35],研究了能够抵御关键词猜测攻击的dPEKS方案.
4.4.2 查询方式扩展4.4.2.1 多关键词检索
PECK(public key encryption with conjunctive field keyword search)的概念源于文献[36],其目的是在PEKS的基础上检索使用“逻辑与”连接的多个关键词的问题.典型方案见表 4.
|
|
Table 4 Comparison on PECK schemes 表 4 PECK典型方案对比 |
由表 4可知:现有PECK方案几乎都基于双线性对运算;通信量、服务器端存储量和检索时双线性对运算次数方面,PECK-1[36]都具有较好的效果,然而该方案在加密关键词时,需执行li次对运算,效率很低;HVE[38]计算和存储耗费最大,却具有广泛适用性,可用于实现逻辑连接词连接的多关键词查询和数据库中的比较查询,成为后来查询方式扩展研究的主要参考.
4.4.2.2 模糊关键词检索文献[39]使用HVE[38]构造包含通配符的PEKS方案.HVE中,每个密文C和密钥K都分别与一个二进制属性向量X=(X1,X2,…,Xn)和Y=(Y1,Y2,…,Yn)相关联,这里,Y中的某个分量不存在时,记为‘*’.K可以用来解密C当且仅当X与Y在除‘*’外的所有分量都相同.包含通配符的PEKS中,将每个关键词视为属性向量:发送者使用邮件包含的关键词作为公钥,对该邮件执行HVE加密;接收者发送给服务器的陷门是待检索关键词的解密密钥,服务器试图执行HVE解密,如果解密成功,说明两个关键词除‘*’外所有分量都相同,从而达到包含通配符的关键词检索的目的.
5 工作展望 5.1 应用场景展望由于可搜索加密技术能够提供安全的加密和密文直接检索功能,因此适合于外包敏感数据加密领域,除第1.2节中概述的个人数据外包加密和邮件信息加密外,还包括:
1) 外包数据库字段加密
在外包数据库中,由于服务提供商的不可信赖,对数据库中的敏感信息加密是非常必要的.然而,在数据库中加密数据一直是一个难题,因为加密数据库中的信息即意味着破坏该信息的本质特征,以致无法执行某些查询和检索操作.引入确定性的可搜索加密技术[42],使用数据拥有者的公钥分别对所有字段加密,可极大地提高数据库的安全性.同时,由于加密方式的确定性,也可使数据库系统结构仍然以标准数据结构组织和管理.目前,该领域已成为可搜索加密的一个新的研究热点.
2) 云计算中隐私数据的保护和共享
近年来,随着云计算的不断普及,面临的安全问题的重要性逐步上升,保护数据的隐私是云安全的一个重要课题[3].由于可搜索加密技术能够提供对密文进行基于关键词检索的功能,使其非常适用于云端隐私数据的保护,同时也不会牺牲对云端数据的提取和使用效率.在云端隐私数据的高效共享方面,可搜索加密也发挥巨大作用,其能有效地支持最基本形式的隐私数据共享,即,文件的发送和接收.结合基于属性加密和代理重加密技术,SE能够适用于各种场景下高细粒度控制的云端数据共享.
3) 密文直接操作的相关应用
除了上述敏感信息的数据加密以外,SE还非常适用于对密文数据进行直接操作的一类应用,这将是SE在未来的一个重要的应用领域.例如,文献[43]在邮件路由问题的基础上进一步考虑了另一种实际应用场景:假设发送者所发邮件中携带恶意程序,由于邮件已被加密,服务器无法检测其恶意内容,而直接交由接收者执行本地检查会增加终端计算负载.引入可搜索加密技术,通过接收者向服务器提供陷门,使服务器能够使用本地恶意代码特征库扫描匹配密文邮件恶意代码,无需解密查看邮件明文.
5.2 研究方向展望作为基本工具,对称和非对称可搜索加密可与其他技术结合,应用于解决各种场景下的各种形式的关键词检索问题.表 5根据当前和未来可能广泛应用的SE系统模型与关键词检索中查询策略和返回结果的灵活性,总结了当前的研究工作中已解决哪些问题,从而展望未来的研究方向.
|
|
Table 5 Research of SE 表 5 SE研究情况总结 |
需要指出的是,除当前广泛研究和应用的4种系统模型外(详细介绍见第2.1节),我们认为,用户存储的多服务器模型将是未来发展的方向.简单地说,多服务器模型是对用户使用习惯和网络发展趋势的一种顺应.例如,随着如今云服务市场的兴起,针对同一类型的云服务,通常有多个服务提供商存在(从宏观角度来看,每个云服务提供商都可视为一个逻辑上的服务器).用户因此期望能够将个人数据分散存储到多个服务提供商处,然后通过多个提供商的协议合作,共同来为用户提供存储和关键词检索的服务.相比于单服务器在数据存储和处理方面的局限性,这种多个服务器存储文件的模式能够加强用户远程数据的可靠性,并可通过多个服务器协同处理提高对大型数据文件的处理能力.
通过对上述研究情况进行的总结和分析,我们认为,SE研究中仍存在着值得深入研究的问题,主要包括:
1) 多服务器系统模型下的关键词检索问题
相比于单服务器,多服务器的关键词检索涉及到了多个不可信赖实体,其难点在于如何设计一种执行于这些存储服务器的多方协议,使其能够协作地执行密文关键词检索的任务.传统的多方计算方法允许多个实体在分别保有自己秘密的前提下共同计算并得到基于所有实体持有秘密的结果,但难以适用于多服务器的关键词检索情景,这是因为用户并不希望最后协作计算检索到的文件(像多方计算的计算结果一样)泄漏给任何一个不可信赖服务器.因此,解决多服务器模型下的关键词检索问题成为应用这种模型前的一个迫切需求.
2) 多用户共享模式下潜在的密钥泄漏问题
虽然现有方案已能解决多用户共享模式下的关键词检索问题,但其基于较高的系统模型假设(例如,引入可信第三方)[44]或较低的安全目标(例如,允许服务器获得关键词信息)[45,46]或由于通过服务器重加密或其他复杂运算而导致效率较低[47, 48, 49].若要同时解决以上3个问题,需要所有用户共享同一私钥,这会导致密钥泄漏的潜在风险.因此,完善现有的多用户共享模式下的关键词检索机制,是未来需要研究的一个重要方向.
3) 多用户单服务器模型下的查询结果排序问题
文献[17,18]关于SE中查询结果排序的研究仅仅适用于广播模式,并要求广播者事先向授权用户发布必要的秘密参数以辅助查询.该技术难以推广到多个广播者的情况,且由于发送者与接收者之间的秘密沟通,限制了其应用范围.因此,未来需要探究一种更加完备、多用户单服务器模型下的查询结果排序机制.
4) PEKS的安全性问题
除以上问题之外,PEKS的安全性也需要受到关注.PEKS能够适用于最基本的共享模式,具有广阔的应用空间.然而,其安全性问题是阻碍PEKS应用的重要原因.如前所述,几乎所有PEKS都遭受猜测关键词攻击的潜在威胁.虽然PERKS[28]和PEFKS[29]能够抵御关键词猜测攻击,但牺牲了一定的性能:PERKS[28]要求构建安全通道完成关键词注册;PEFKS[29]的返回结果包含非目标文件,需进行本地二次精确陷门测试.因此,设计一种更加安全、高效的PEKS扩展方案,也是未来研究的方向之一.
6 结 论可搜索加密为不可信服务器的密文检索提供了解决办法,已在云存储密文检索环境中得到了广泛应用.可搜索加密的提出,源于解决两类可搜索加密的基本问题:① 不可信赖服务器的存储问题;② 不可信赖服务器的路由问题.问题①推动了对称可搜索加密的研究进展,问题②推动了非对称可搜索加密的研究进展.两类可搜索加密均为不可信服务器的密文检索提供了解决办法,已在云存储密文检索环境中得到了广泛应用.本文围绕两类非对称可搜索加密进行了综述.
在对称可搜索加密方面,介绍了SSE定义、相关安全目标和典型构造,总结了两种基本SSE方案的构建策略:基于顺序扫描的构建策略和基于索引的构建策略.前者需要遍历整个文件,效率极低;后者通过构造索引,能够高效地支持关键词查询操作,已成为SSE方案构造的主要策略.分析了两种主流索引构建思想:“文件-关键词”和“关键词-文件”索引构建思想,指出操作处理的基本单位的不同决定了在完成这些操作时效率上的差异.介绍了SSE的相关扩展,主要表现在对查询方式的扩展、对查询结果的优化以及对方案本身安全机制的完善上.
在非对称可搜索加密方面,介绍了PEKS定义、算法一致性和相关安全目标,描述了PEKS的典型构造及其与IBE的相互转换算法,指出现有PEKS的构造通常基于已提出的IBE.安全性方面,对导致关键词猜测攻击的原因进行了分析,总结了针对关键词猜测攻击的预防措施.介绍了PEKS的相关扩展,主要表现在对安全性的改善和对查询方式的扩展上.
最后,总结和展望了可搜索加密的未来研究方向,以期对其在国内的研究起到一定的推动作用.
| [1] | Song XD, Wagner D, Perrig A. Practical techniques for searches on encrypted data. In: Proc. of the IEEE Symp. on Security and Privacy. IEEE Press, 2000. 44-55 . |
| [2] | Boneh D, Di Crescenzo G, Ostrovsky R, Persiano G. Public key encryption with keyword search. In: Camenisch LJ, Cachin C, eds. Proc. of the Advances in Cryptology—EUROCRYPT 2004. LNCS 3027, Berlin: Springer-Verlag, 2004. 506-522 . |
| [3] | Feng DG, Zhang M, Zhang Y, Xu Z. Study on cloud computing security. Ruan Jian Xue Bao/Journal of Softwase, 2011,22(1): 71-83 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3958.htm |
| [4] | Goh E. Secure indexes. Technical Report, 2003/216, IACR ePrint Cryptography Archive, 2003. http://eprint.iacr.org/2003/216 |
| [5] | Chang Y, Mitzenmacher M. Privacy preserving keyword searches on remote encrypted data. In: Ioannidis J, Keromytis A, Yung M, eds. Proc. of the Applied Cryptography and Network Security. LNCS 3531, Berlin: Springer-Verlag, 2004. 391-421 . |
| [6] | Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: Improved definitions and efficient constructions. In: Proc. of the 13th ACM Conf. on Computer and Communications Security (CCS 2006). New York: ACM Press, 2006. 79-88. |
| [7] | Van Liesdonk P, Sedghi S, Doumen J, Hartel P, Jonker W. Computationally efficient searchable symmetric encryption. In: Jonker W, Petkovic M, eds. Proc. of the Secure Data Management. LNCS 6358, Berlin: Springer-Verlag, 2010. 87-100 . |
| [8] | Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption. In: Proc. of the 19th ACM Conf. on Computer and Communications Security (CCS 2012). New York: ACM Press, 2012. 965-976 . |
| [9] | Kamara S, Papamanthou C. Parallel and dynamic searchable symmetric encryption. In: Sadeghi AR, ed. Proc. of the Financial Cryptography and Data Security. LNCS 7859, Berlin: Springer-Verlag, 2013. 258-274 . |
| [10] | Golle P, Staddon J, Waters B. Secure conjunctive keyword search over encrypted data. In: Jakobsson M, Yung M, Zhou J, eds. Proc. of the Applied Cryptography and Network Security. LNCS 3089, Berlin: Springer-Verlag, 2004. 31-45 . |
| [11] | Ballard L, Kamara S, Monrose F. Achieving efficient conjunctive keyword searches over encrypted data. In: Qing S, Mao W, Lopez J, Wang G, eds. Proc. of the Information and Communications Security. LNCS 3783, Berlin: Springer-Verlag, 2005. 414-426 . |
| [12] | Byun J, Lee D, Lim J. Efficient conjunctive keyword search on encrypted data storage system. In: Atzeni SA, Lioy A, eds. Proc. of the Public Key Infrastructure. LNCS 4043, Berlin: Springer-Verlag, 2006. 184-196 . |
| [13] | Li J, Wang Q, Wang C, Cao N, Ren K, Lou WJ. Fuzzy keyword search over encrypted data in cloud computing. In: Proc. of the 29th IEEE Int’l Conf. on Computer Communications (INFOCOM). IEEE Press, 2010. 1-5 . |
| [14] | Wang C, Ren K, Yu SC, Urs KMR. Achieving usable and privacy-assured similarity search over outsourced cloud data. In: Proc. of the 31th IEEE Int’l Conf. on Computer Communications (INFOCOM). IEEE Press, 2012. 451-459 . |
| [15] | Bösch C, Brinkman R, Hartel P, Jonker W. Conjunctive wildcard search over encrypted data. In: Jonker W, Petkovic, eds. Proc. of the Secure Data Management. LNCS 6933, Berlin: Springer-Verlag, 2011. 114-127 . |
| [16] | Swaminathan A, Mao Y, Su GM, Gou H, Varna A, He S, Wu M, Oard D. Confidentiality-Preserving rank-ordered search. In: Proc. of the ACM Workshop on Storage Security and Survivability (StorageSS 2007). New York: ACM Press, 2007. 7-12 . |
| [17] | Wang C, Cao N, Li J, Ren K, Lou WJ. Secure ranked keyword search over encrypted cloud data. In: Proc. of the 30th Int’l Conf. on Distributed Computing Systems (ICDCS). IEEE Press, 2010. 253-262 . |
| [18] | Cao N, Wang C, Li M, Ren K, Lou WJ. Privacy-Preserving multi-keyword ranked search over encrypted cloud data. In: Proc. of the 32th IEEE Int’l Conf. on Computer Communications (INFOCOM). IEEE Press, 2011.829-837 . |
| [19] | Chai Q, Gong G. Verifiable symmetric searchable encryption for semi-honest-but-curious cloud servers. In: Proc. of the IEEE Int’l Conf. on Communications. IEEE Press, 2012. 917-922 . |
| [20] | Kurosawa K, Ohtaki Y. UC-Secure searchable symmetric encryption. In: Keromytis A, ed. Proc. of the Financial Cryptography and Data Security. LNCS 7397, Berlin: Springer-Verlag, 2012. 285-298 . |
| [21] | Boneh D, Franklin M. Identity-Based encryption from the Weil pairing. In: Kilian J, ed. Proc. of the Advances in Cryptology—CRYPTO 2001. LNCS 2139, Berlin: Springer-Verlag, 2001. 213-229 . |
| [22] | Khader D. Public key encryption with keyword search based on K-resilient IBE. In: Gavrilova M, Gervasi O, Kumar V, et al., eds. Proc. of the Computational Science and Its Applications—ICCSA 2006. LNCS 3982, Berlin: Springer-Verlag, 2006.298-308 . |
| [23] | Crescenzo GD, Saraswat V. Public key encryption with searchable keywords based on Jacobi symbols. In: Srinathan K, Rangan PC, Moti Y, eds. Proc. of the Progress in Cryptology—INDOCRYPT 2007. LNCS 4859, Berlin: Springer-Verlag, 2007. 282-296 . |
| [24] | Abdalla M, Bellare M, Catalano D, Kiltz E, Kohno T, Lange T, Malone Lee J, Neven G, Paillier P, Shi HX. Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions. In: Shoup V, ed. Proc. of the Advances in Cryptology—CRYPTO 2005. LNCS 3621, Berlin: Springer-Verlag, 2005. 205-222 . |
| [25] | Byun J, Rhee H, Park HA, Lee DH. Off-Line keyword guessing attacks on recent keyword search schemes over encrypted data. In: Jonker W, Petkovic M, eds. Proc. of the Secure Data Management. LNCS 4165, Berlin: Springer-Verlag, 2006. 75-83 . |
| [26] | Yau WC, Heng SH, Goi BM. Off-Line keyword guessing attacks on recent public key encryption with keyword search schemes. In: Rong C, Jaatun MG, Sandnes FE, et al., eds. Proc. of the Autonomic and Trusted Computing. LNCS 5060, Berlin: Springer-Verlag, 2008. 101-105 . |
| [27] | Jeong IR, Kwon JO, Hong D, Lee DH. Constructing PEKS schemes secure against keyword guessing attacks is possible. Computer Communications, 2009,32(2):394-396 . |
| [28] | Tang Q, Chen L. Public-Key encryption with registered keyword search. In: Martinelli F, Preneel B, eds. Proc. of the Public Key Infrastructures, Services and Applications. LNCS 6391, Berlin: Springer-Verlag, 2010. 163-178 . |
| [29] | Xu P, Jin H. Public-Key encryption with fuzzy keyword search: A provably secure scheme under keyword guessing attack. IEEE Trans. on Computers, 2012,62(11):2266-2277 . |
| [30] | Baek J, Safavi NR, Susilo W. On the integration of public key data encryption and public key encryption with keyword search. In: Katsikas KS, Lopez J, Backes M, et al., eds. Proc. of the Information Security. LNCS 4176, Berlin: Springer-Verlag, 2006.217-232 . |
| [31] | Zhang R, Imai H. Generic combination of public key encryption with keyword search and public key encryption. In: Bao F, Ling S, Okamato T, et al., eds. Proc. of the Cryptology and Network Security. LNCS 4856, Berlin: Springer-Verlag, 2007.159-174 . |
| [32] | Baek J, Safavi NR, Susilo W. Public key encryption with keyword search revisited. In: Gervasi O, Murgante B, Lagana A, et al., eds. Proc. of the Computational Science and Its Applications—ICCSA 2008. LNCS 5072, Berlin: Springer-Verlag, 2008. 1249-1259 . |
| [33] | Rhee HS, Park JH, Susilo W, Lee DH. Improved searchable public key encryption with designated tester. In: Proc. of the 4th Int’l Symp. on Information, Computer, and Communications Security (ASIACCS 2009). New York: ACM Press, 2009. 376-379 . |
| [34] | Rhee HS, Susilo W, Kim HJ. Secure searchable public key encryption scheme against keyword guessing attacks. IEICE Electronics Express, 2009,6(5):237-243 . |
| [35] | Hu C, Liu P. A secure searchable public key encryption scheme with a designated tester against keyword guessing attacks and its extension. In: Lin S, Huang X, eds. Proc. of the Advances in Computer Science, Environment, Ecoinformatics, and Education. CCIS 215, Berlin: Springer-Verlag, 2011. 131-136 . |
| [36] | Park D, Kim K, Lee P. Public key encryption with conjunctive field keyword search. In: Lim HC, Yung M, eds. Proc. of the Information Security Applications. LNCS 3325, Berlin: Springer-Verlag, 2005. 73-86 . |
| [37] | Hwang Y, Lee P. Public key encryption with conjunctive keyword search and its extension to a multi-user system. In: Takagi T, Okamoto T, Okamoto E, et al., eds. Proc. of the Pairing-Based Cryptography—Pairing 2007. LNCS 4575, Berlin: Springer-Verlag, 2007. 2-22 . |
| [38] | Boneh D, Waters B. Conjunctive, subset, and range queries on encrypted data. In: Vadhan PS, ed. Proc. of the Theory of Cryptography. LNCS 4392, Berlin: Springer-Verlag, 2007. 535-554 . |
| [39] | Sedghi S, Van Liesdonk P, Nikova S, Hartel P, Jonker W. Searching keywords with wildcards on encrypted data. In: Garay AJ, Prisco DR, eds. Proc. of the Security and Cryptography for Networks. LNCS 6280, Berlin: Springer-Verlag, 2010. 138-153 . |
| [40] | Li M, Yu SC, Cao N, Lou WJ. Authorized private keyword search over encrypted data in cloud computing. In: Proc. of the 31st Int’l Conf. on Distributed Computing System (ICDCS). Minneapolis: IEEE Press, 2011. 383-392 . |
| [41] | Waters B, Balfanz D, Durfee G, Smetters DK. Building an encrypted and searchable audit log. In: Proc. of the 11th Annual Network and Distributed System Security Symp. 2004. http://www.isoc.org/ndss04/proceedings/Papers/Waters.pdf |
| [42] | Bellare M, Boldyreva A, O’Neill A. Deterministic and efficiently searchable encryption. In: Menezes A, ed. Proc. of the Advances in Cryptology—CRYPTO 2007. LNCS 4622, Berlin: Springer-Verlag, 2007. 535-552 . |
| [43] | Ibraimi L, Nikova S, Hartel P, Jonker W. Public-Key encryption with delegated search. In: Lopez J, Tsudik G, eds. Proc. of the Applied Cryptography and Network Security. LNCS 6715, Berlin: Springer-Verlag, 2011. 532-549 . |
| [44] | Li JW, Li J, Liu ZL, Jia CF. Enabling efficient and secure data sharing in cloud computing. Concurrency and Computation: Practice and Experience, 2014,26(5):1052-1066 . |
| [45] | Canard S, Fuchsbauer G, Gouget A, Laguilaumie F. Plaintext-Checkable encryption. In: Dunkelman O, ed. Proc. of the Topics in Cryptology—CT-RSA 2012. LNCS 7178, Berlin: Springer-Verlag, 2012. 332-348 . |
| [46] | Li JW, Li J, Chen XF, Liu ZL, Jia CF. Privacy-Preserving data utilization in hybrid clouds. Future Generation Computer Systems, 2014,30:98-106 . |
| [47] | Dong C, Russello G, Dulay N. Shared and searchable encrypted data for untrusted servers. Journal of Computer Security, 2011, 19(3):367-397 . |
| [48] | Popa RA, Zeldovich N. Multi-Key searchable encryption. Technical Report, 2013/508, IACR ePrint Cryptography Archive, 2013. https://eprint.iacr.org/2013/508 |
| [49] | Zheng Q, Xu S, Ateniese G. VABKS: Verifiable attribute-based keyword search over outsourced encrypted data. Technical Report, 2013/462, IACR ePring Cryptography Archive, 2013. https://eprint.iacr.org/2013/462 |
| [3] | 冯登国,张敏,张妍,徐震.云计算安全研究.软件学报,2011,22(1):71-83. http://www.jos.org.cn/1000-9825/3958.htm |