支持联合查询的高效可搜索对称加密方案

古宜平， 马昌社

(华南师范大学计算机学院， 广州 510631)

基于云服务的数据外包技术可以有效地减负用户的本地资源开销. 然而，云服务器并非完全安全可靠，其一般被认为是诚实却好奇的，它诚实执行程序，却不具有可控性，存在窥探用户数据的威胁. 因此，用户的普遍做法是对数据先加密后上传. 但对数据采用标准加密算法加密后，完全破坏了数据的可搜索性，一个解决此问题的直接方法是用户先将所有加密数据下载到本地，然后进行解密，对明文进行搜索. 但这种操作并不具有可用性，因为一方面因下载了大部分不需要的数据而浪费带宽；另一方面解密所有密文又占用了用户大量的本地存储和计算开销. 而理想的做法是由服务器利用其强大的资源进行检索，将搜索结果返回给用户，同时保证泄露给服务器的信息足够少，以最大限度地保证数据隐私安全性.

为解决这类问题，可搜索对称加密(Searchable Symmetric Encryption，SSE)技术[1-4]应运而生. 自从SONG等[1]于2000年提出第1个SSE方案后，学者们提出了一批涉及功能、性能和安全之间权衡的SSE方案[2-4]. 其中，功能方面描述方案支持的数据集结构和查询类型，性能方面分析方案的存储大小、用户和服务器的计算量、交互轮数及带宽开销，安全方面分析和概括数据集的加密结果和查询过程的全部泄露. 2004年，GOLLE等[5]最先针对联合查询提出2个SSE方案，此后，一系列工作[6-9]改进了联合查询的性能和安全，包括将IND-CKA(Indistinguishability under Chosen Keyword Attacks)安全从单关键字查询推广到多关键字查询，减少查询过程中客户端和服务器的计算量和交互开销，减少存储开销，使得数据集的文档不需要关联关键字集. 但是，这些方案的查询效率皆与数据集的大小呈线性关系，直到2013年，采用基于Diffie-Hellman类型操作的安全两方计算，CASH等[10]针对联合查询提出第一个亚线性的SSE方案(Oblivious Cross-Tags，OXT). 但面对大量数据时，计算量开销大的Diffie-Hellman类型操作[11]将成为该方案的计算性能瓶颈.

为了提高支持联合查询的可搜索对称加密方案的计算性能，本文提出一个支持联合查询的高效可搜索对称加密方案(Efficient Cross-Tags，EXT). 该方案采用客户端单独计算关键字与文档之间的关系，并交给服务器检验这一关系的方法来实现联合查询，从而避免Diffie-Hellman类型操作. 另外，从正确性、安全性以及性能方面对该方案进行分析.

1 预备知识

本节对本文的符号进行说明，并列举方案构造以及分析用到的密码学原语.

1.1 符号说明

设C(·)为概率多项式时间(PPT，Probabilistic Polynomial Time)算法，c←C(·)表示算法C(·)的输出赋值给变量c. 假设a和b为正整数，且aN0，皆有neg()<1/p()，则称neg()是可忽略函数. 令∅表示空集或空字符串.

1.2 可搜索对称加密

一般地，在SSE方案中，客户端先在本地加密数据集，然后将加密结果存储于服务器. 为了让服务器能够基于加密结果进行查询，客户端基于明文数据集生成加密的索引数据结构. 以下是可搜索对称加密方案的形式化定义：

定义1[1](可搜索对称加密方案)给定安全参数,SSE方案Π=(Setup,Search)由初始化加密算法Setup和查询协议Search组成. 其中，Setup算法运行于客户端，Search协议由客户端和服务器通过交互共同完成. 方案的具体过程为：

(1)(SK,EDB)←Setup(1,DB)：系统初始化算法. 给定明文数据集DB，该算法输出密钥SK和数据集密文EDB. 其中,客户端秘密存储SK，服务器存储EDB.

对于SSE方案Π，用泄漏函数表示诚实却好奇的服务器能够从数据集的加密结果和查询过程中分析得到的有用信息. 下面是SSE方案的语义安全的形式化定义：

定义2[12-13](SSE方案的语义安全)给定SSE方案Π=(Setup,Search). 对于PPT敌手和仿真器，定义算法)和)如下：

1.3 T-Set方案

T-Set方案是倒排索引数据结构的具体实现之一. 一般地，T-Set方案包含3个算法：TSSetup、TSGetTag和TSRetrieve. 这些算法的具体定义、安全以及实现均可参照文献[10]. 本文采用文献[14]设计的T-Set方案Πbas，其具体实现及安全性描述如下：

(2)stag←TSGetTag(KT,w)：计算K1||K2←F(KT,w)，令stag←K1||K2作为w的查询陷门.

(3)Tw←TSRetrieve(D,stag)：首先，展开stag为K1||K2，令Tw←∅，c←1，计算←F(K1,c). 然后，一直执行以下循环直至D[]=⊥：解密Tw[c]←Dec(K2,D[l])，令c←c+1，计算←F(K1,c).

定理1[14]在随机预言机模型下，假设F是安全的伪随机函数，(Enc,Dec)是IND-CPA安全的对称加密方案，那么Πbas方案在自适应式攻击下是T(T,q)安全的.

1.4 困难性假设

以下分别给出伪随机函数以及IND-CPA(Indistinguishability under Chosen-Plaintext Attacks)安全的对称加密方案的定义.

定义3[15](伪随机函数)称函数F:{0,1}×{0,1}n→{0,1}m为伪随机函数，如果对于任意PPT敌手，都有

成立，其中第1个概率依赖于K{0,1}的均匀随机性和敌手的随机性，第2个概率依赖于fFun({0,1}n,{0,1}m)的均匀随机性和敌手的随机性.

定义4[16](IND-CPA安全的对称加密方案)对称加密方案(Symmetric Encryption Scheme，SKE)Ω=(Gen,Enc,Dec)包含3个算法. 给定安全参数，算法Gen输出密钥K{0,1}. 算法Enc的输入为密钥K{0,1}和明文M，输出为密文C. 算法Dec的输入为密钥K{0,1}和密文C，输出为明文M. 方案需要保证对任意合法的密钥K和明文M都具有计算正确性. 称方案Ω为IND-CPA安全的SKE方案，如果对任意PPT敌手，都有

2 EXT方案

算法1EXT系统初始化算法

输入：1，DB

输出：SK，EDB

Step 2. 分别为伪随机函数FC和FS选择相应的密钥KC和KS；初始化T←∅，XSet←∅；

Step 3. 对每个wW执行以下步骤：

初始化链表tw←∅；计算Ke←FS(KS,w)；

e←Enc(Ke,id)，将e添加到tw；

xtag←FC(KC,w||id)，XSet←XSet∪{xtag}；

令T[w]←tw；

Step 4. (D,KT)←TSSetup(T)；

Step 5. 令SK←(KC,KS,KT)，EDB←(D,XSet)，返回SK，EDB.

图1 EXT查询协议

以下是算法Setup和协议Search的详细过程：

(1)Setup(1,DB)：首先，展开明文数据集并分别为伪随机函数FS和FC选择相应密钥KS和KC，以及初始化数组T←∅和集合XSet←∅. 然后，按如下步骤生成D：(i)对于所有wW，初始化链表tw←∅并计算Ke←FS(KS,w);(ii)对每个wW,对每个idDB[w],加密e←Enc(Ke,id)并将e插入链表tw，令T[w]←tw；(iii)调用算法(D,KT)←TSSetup(T). 其次，对每对(w,id)(idDB[w])，计算xtag←FC(KC,w||id)并更新集合XSet←XSet∪{xtag}. 最后，输出SK←(KC,KS,KT)和EDB←(D,XSet).

Step 1. 客户端调用算法stag←TSGetTag(KT,w1)并发送stag给服务器.

Step 2. 服务器调用算法tw1←TSRetrieve(D,stag)并发送tw1给客户端.

Step 3. 客户端首先计算Ke←FS(KS,w1)，然后按如下步骤生成XTags：①对所有c[1,|tw1|]，令ec←tw1[c]，解密idc←Dec(Ke,ec)；②对每个[2,n],计算XTags[c,]←FC(KC,w||idc). 最后发送XTags给服务器.

Step 4. 服务器首先初始化集合E←∅；然后，对所有c[1,|tw1|]，如果对所有[2,n]均有XTags[c,]XSet，则更新集合E←E∪{c}；最后，发送E给客户端.

Step 5. 客户端首先初始化集合R←∅；然后，对所有cE更新集合R←R∪{idc}；最后，输出R.

3 方案分析

3.1 正确性分析

以下给出EXT方案的正确性分析.

定理2假设(TSSetup,TSGetTag,TSRetrieve)是具有计算正确性的T-Set方案，FC和FS是安全的伪随机函数，那么对于任意PPT敌手，均有)=1]≤neg()，即EXT具有计算正确性.

3.2 安全性分析

证明定义一系列游戏G0,G1,…,G6以及仿真器，使得游戏G0与)具有相同的分布，游戏G6与仿真器具有相同的分布. 其中游戏G0,G1,…,G6输入(DB,q)，仿真器输入EXT(DB,q)，而游戏G0,G1,…,G6和仿真器均向敌手提供二元组(EDB,Tr). 最后，游戏和仿真器均输出敌手返回的判断值. 如果对任意i(0≤i<6)，都有|Pr[Gi=1]-Pr[Gi+1=1]|≤neg()，则

下面分别构造游戏G0,G1,…,G6和仿真器，并分别证明),G0,…,G6,中所有相邻的2个分布计算不可区分.

(1)游戏G0：

②生成EDB[1]：首先，初始化集合XSet←∅；然后，对每对(w,id)(idDB[w])，计算xtag←FC(KC,w‖id)，并更新集合XSet←XSet∪{xtag}；最后，令EDB[1]←XSet.

③生成Tr[1]：(i)对每个i[1,Q]，按如下步骤生成XTags[i]：首先，调用算法ti←TSRetrieve(D,STags[i])，计算Ke←FS(KS,w1)；其次，对每个c[1,|DB[s[i]]|],解密idc←Dec(Ke,ti[c])，并计算XTags[i,c]←FC(KC,x[i]‖idc). (ii)令Tr[1]←XTags.

(2)游戏G1：

②生成EDB[1]：首先，初始化集合XSet←∅；然后，对每对(w,id)(idDB[w]),调用xtag←A[w,id]并更新集合XSet←XSet∪{xtag}；最后,令EDB[1]←XSet.

③生成Tr[1]：(i)对每个i[1,Q],按如下步骤生成XTags[i]：首先，展开读取排列σ←Wperms[s[i]]；然后，对每个c[1,Ts],令令Tr[1]←XTags.

相较于游戏G0，游戏G1首先生成数组A，即对每对(w,id)计算A[w,id]←FC(KC,w‖id)；然后，在XSet和XTags的构建中需要调用FC的地方直接引用A相应的值. 因为这部分内容只包含表达上的更改，所以

Pr[G1=1]=Pr[G0=1].

(3)游戏G2：将伪随机函数FS和FC替代为随机函数. 将游戏G1的②③保持不变，仅将G1的①作如下修改：

因为FS与FC是安全的伪随机函数，所以存在PPT敌手2,1和2,2，使得

由于(End,Dec)是IND-CPA安全的SKE，而且对0的加密次数是关于的多项式次，即poly()次，则存在PPT敌手3，使得

|Pr[G3=1]-Pr[G2=1]|≤poly().

(5)游戏G4：将游戏G3第①部分中生成字典D的语句(D,KT)←TSSetup(T)和生成STags的语句STags[i]←TSGetTag(KT,s[i])改为(D,STags)←T(T(T,s))，其中T是T-Set的PPT仿真器.

因为(TSSetup,TSGetTag,TSRetrieve)是在(非自适应式)攻击下具有T安全的T-Set方案，所以，存在PPT敌手4，使得

(6)游戏G5：将游戏G4的第②部分作如下修改，其他部分保持不变:

生成EDB[1]：首先，初始化集合XSet←∅；然后，对每对(w,id)(idDB[w])，判断是否存在i使得idDB[s[i]]∧x[i]=w，是则读取xtag←A[w,id]，否则随机生成并更新集合XSet←XSet∪{xtag}；最后，令EDB[1]←XSet.

Pr[G5=1]=Pr[G4=1].

(7)游戏G6：将游戏G5的第③部分作如下修改，其他部分保持不变.

生成Tr[1]：(i)对每个i[1,Q]执行如下步骤生成XTags[i]：首先，展开读取排列σ←Wperms[s[i]]；然后，对每个c[1,Ts]，如果DB[s[i]]∩DB[x[i]]，则令否则，如果DB[s[j]]∧x[j]=x[i]，则令否则令令Tr[1]←XTags.

游戏G6改变XTags构建过程中访问A的模式. 为保证敌手能够检验的XTags模式与游戏G5的相同，对每对(w,id)，如果查询中XTags[w,id]理应含于XSet，则令XTags[w,id]←A[w,id]，如果XTags存在另一个元素XTags[w′,id′]，使得XTags[w,id]=XTags[w′,id′]，亦令XTags[w,id]←A[w,id]. 这些改变恰好使得敌手能够检验的XTags模式与游戏G5的相同,则

Pr[G6=1]=Pr[G5=1].

(1)

(2)

①生成EDB[0]与Tr[0]：(i)对每对(w,id)(w∪i(RP[i]∪∪j≠iIP[i,j])),令(ii)按如下步骤生成D和STags：首先，对所有w选择生成排列且记录此排列Wperms[w]←σ，初始化链表tw←∅并生成密钥然后，对每个w对每个c[1,SP[w]]，加密e←Enc(Ke,0)且令tw[c]←e，令T[w]←tw；最后，令且调用算法(D,STags)←T(T(DB,s)，T[s]). (iii)令EDB[0]←D，Tr[0]←STags.

②生成EDB[1]：首先，初始化集合XSet←∅；然后，对每对(w,id)(w更新集合XSet←XSet∪{A[w,id]}；其次，令j←|XSet|，并从i=j+1到N，依次随机抽取并更新集合XSet←XSet∪{h}；最后，令EDB[1]←XSet.

③生成Tr[1]：(i)对每个i[1,Q],按如下步骤生成XTags[i]：首先，生成集合Ri←RP[i]∪∪j≠iIP[i,j]且令T′←|Ri|；然后，读取排列展开最后，对每个c[1,SP[i]]，判断是否有是则令否则令令Tr[1]←XTags.

3.3 性能分析

本节从计算量、存储开销、交互开销等性能方面，对OXT方案和EXT方案进行对比分析.

在初始化加密算法中，OXT、EXT方案生成的字典D和集合XSet分别包括N个元组. OXT方案采用一个PRF计算和一个SKE加密生成D的每个元组，采用一个DH类型操作生成XSet的每个元组；而EXT方案采用一个SKE加密生成D的每个元组，采用一个PRF计算生成XSet的每个元组. 最后，为节省存储开销，OXT、EXT方案均把XSet转换成布隆过滤器进行存储. 此过程中，OXT、EXT方案的计算量分别为N(TF+TE+Te)+NkTh、N(TE+TF)+NkTh. 另外，OXT、EXT方案的存储开销分别为N(E+p)+m、N(E)+m.

在查询协议中，假设查询为w1∧w2∧…∧wn. 在OXT方案中，首先,客户端生成stag和xtoken并传给服务器；然后，服务器生成相应的xtag，并查看这些xtag相对于XSet的子集关系，把满足查询的加密id传给客户端；最后，客户端解密得到查询结果. 这个过程中，客户端、服务器的计算量分别为TF+α(nTF+(n-1)Te)+βTD、α(n-1)(Te+kTh). 另外，这个过程涉及两轮交互，其带宽开销为F+|t|+α(n-1)D+βE. 而在EXT方案中，首先，客户端生成stag以得到服务器的查询结果T[w1]；然后，客户端据此生成相应的xtag并传给服务器；其次，服务器查看这些xtag相对于XSet的子集关系，并把满足查询的id项编号传给客户端；最后，客户端输出查询结果. 这个过程中，客户端、服务器的计算量分别为TF+α(TD+(n-1)TF)、α(n-1)kTh. 另外，这个过程依旧涉及两轮交互，其带宽开销为F+αE+α(n-1)F+β|t|.

表1 OXT方案与EXT方案的性能比较Table 1 Evaluations of the overheads between OXT and EXT %

4 结论

本文提出了一个支持联合查询的高效可搜索对称加密方案EXT，与OXT方案相比较，EXT方案在保证相同功能和安全的情况下将系统初始化的计算量、查询时客户端的计算量、查询时服务器的计算量、存储开销分别降低了95.05%、97.67%、98.48%、55.05%.

支持动态操作的SSE方案具有更大的实用性，而把EXT方案实现为支持动态操作的SSE方案并同时保证其前向安全和后向安全，需要使其T-Set方案和集合XSet同时支持动态操作. 目前已有一些研究[4,18]着力于实现支持动态操作的T-Set方案，因此，如何实现支持动态操作的集合XSet可作为进一步的研究方向.