魏国富, 葛新瑞, 于 佳,2,3
1.青岛大学计算机科学技术学院, 青岛266071
2.密码科学技术国家重点实验室, 北京100878
3.中国科学院信息工程研究所信息安全国家重点实验室, 北京100093
随着云计算的日益普及, 越来越多的用户倾向于把自己的数据储存在云服务器上, 以减少本地的储存开销和管理成本.EMC 的调查显示, 云中 75% 的数据是重复的[1].一方面这会增加用户的网络带宽成本, 另一方面也会浪费云服务器的存储资源.因此, 对云数据去重就显得尤为重要.数据去重吸引了越来越多云服务器供应商的注意力.数据去重[2–7](data deduplication) 是一项通过检测并删除重复数据以达到减少存储资源浪费的技术.按数据处理时间, 数据去重可以分为在线去重(inline deduplication) 和后处理去重(post-process deduplication).在线去重指在数据存储到存储设备的同时进行去重处理.后处理去重指在数据存储到设备后统一进行去重处理.在线去重相对来说使用更加广泛, 该技术通过对比云服务器上存储的数据和用户计划上传的数据, 检测云服务器上是否已存在相同的文件, 如果目标文件已存在, 云服务器则为当前用户分配目标文件的权限, 若目标文件不存在, 则允许当前用户上传该文件.数据去重的提出大大的缓解了云服务器的存储压力.
数据存储在云服务器后, 就脱离了用户实际物理控制, 这可能会导致敏感数据的泄露.为了保护敏感数据的隐私性, 用户在外包数据之前往往会对数据进行加密, 数据以密文的形式存储在云服务器上.虽然这可以保证数据的隐私性, 但也使得在密文文件上的搜索变的困难.为了解决这个问题, 可搜索加密[8–13](searchable encryption, SE) 的概念被提出了.为了实现在加密文件上的数据搜索, 用户通常需要对文件提取关键词, 并依据提取的关键词为文件建立相应的索引, 然后用户将加密文件和索引一并上传给云服务器.当用户想要搜索包含某些关键词的文件时, 首先为关键词生成搜索陷门, 然后上传给云服务器.云服务器比较搜索陷门和索引信息, 返回给用户所有相关的密文文件.用户在接收到返回的密文文件后,利用私钥解密密文得到相应的明文文件.
在现实生活中, 当用户搜索包含某一关键词的文件时, 可能会出现关键词拼写错误的问题.在这种情况下, 传统的精确关键词搜索方案[8–13]将无法返回用户想要的文件.为了解决这个问题, 一些模糊关键词搜索方案[14–20]被提出了.模糊搜索实现了在出现一定关键词拼写错误的情况下, 仍然最大程度上搜索到用户最感兴趣的文件.而目前已有的模糊关键词搜索方案中大多假设了云服务器是诚实的, 不会返回错误文件给用户.在云服务器可能出现错误的情况下, 验证返回文件的正确性就很有必要.与此同时, 在只能由数据所有者实现数据搜索的独享场景中和由全部数据所有者共享数据的场景中, 在经过长时间、大规模的使用云存储服务后, 将不可避免地存在大量的冗余数据.而云服务器和数据用户作为可搜索加密方案的参与方, 要避免造成云服务器存储资源和用户网络带宽浪费的行为.因此, 在可验证模糊关键词搜索的基础上是实现数据去重具有重要的实用价值.
本文提出了一种支持数据去重的可验证模糊多关键词搜索方案, 方案实现了以下功能:
(1) 支持数据去重的搜索.为了实现数据去重, 利用收敛加密算法对文件进行加密, 加密文件的密钥是明文文件的哈希值.这就使得不同用户的相同文件得到的密文一致, 从而在数据去重的情况下,实现了安全搜索.
(2) 支持模糊多关键词的搜索.利用局部敏感哈希函数相似的输入会得到相似的输出的特点, 实现了关键词的模糊搜索.根据TF-IDF (term frequency inverse document frequency) 规则计算关键词在包含它的文件中的权重, 根据权重实现对搜索结果的排序.
(3) 支持搜索结果可验证的搜索.利用伪随机函数和在MAC 作用下生成的验证标签构造查找表.通过比对查找表中的验证标签, 实现对搜索结果的验证.
数据去重方案.Bellare 等[3]提出了基于消息的加密 (MLE), 利用 MLE 实现了安全去重.然而, 利用MLE 实现数据去重容易遭受穷举攻击.同时, 在加密文件时会产生大量的密钥导致出现密钥管理问题.为了解决收敛密钥管理问题, Li 等[4]提出了一种新的数据去重系统, 该方案采用多服务器的方式分发密钥.Stanek 等[5]提出了一种支持数据去重的加密方案, 把所有数据分为流行数据和非流行数据.为流行数据和非流行数据提供不同级别的安全性, 但此方案只能在非隐私的流行数据中实现数据去重, 无法实现全部数据去重.
关键词搜索方案.Song 等[8]第一次提出了可搜索对称加密方案, 该方案采用了特殊的两层加密方法, 通过顺序扫描的方式搜索整个文件集合.但每次搜索必须扫描整个文件集合才能得到完整的搜索结果.Goh 等[9]提出了基于布隆过滤器构建索引的关键词搜索方案.对每个文件生成对应的Bloom filter, 把文件中包含的关键词通过哈希函数插入到布隆过滤器的对应位置中.但由于布隆过滤器自身的特性, 所以搜索结果与真实值有一定差异.Curtmola 等[10]提出了两个高效的基于倒排索引的关键词搜索方案.同时给出了非适应性和适应性的定义.但提出的方案无法察觉云服务器欺骗的行为.这些方案支持多用户搜索并实现了亚线性搜索.Wang 等[11]根据关键词频率提出了一个支持结果排序的关键词搜索方案.以上方案均应用于单关键词搜索场景中.单关键词搜索由于缺乏搜索精度导致返回的文件较多, 这会增加用户的存储和计算负担, 降低用户的操作体验.为了使用户能够高效的检索数据, 多关键词搜索方案被提出了.例如, Cao 等[12]提出了一个隐私保护的多关键词排序搜索方案.此方案采用内积匹配相似性规则来测量文件与查询关键词之间的相似度.但此方案只适用于小规模数据集, 对中等规模以上数据集效率不高.Sun等[13]利用向量空间模型[21]和 MDB 树提出了一个多关键词排序搜索方案.Ding 等[22]提出了一个隐私保护的多关键词搜索方案.此方案采用树形结构构建索引并设计了一个随机遍历算法, 即使是相同的查询关键词也会产生不同的访问路径.但由二叉树本身特性的限制, 索引树的结构较为复杂, 搜索时间耗费较高.Peng 等[23]提出了一个支持多数据所有者场景的多关键词排序搜索方案.方案中采用树形结构索引和TF-IDF 模型.通过整合每个数据所有者拥有的加密的基于树的索引, 能够在云服务器不知道索引内容的情况下提高查询效率.
模糊关键词搜索方案.Li 等[15]提出了一个模糊关键词搜索方案.此方案使用编辑距离来测量两个关键词之间的相似程度, 利用通配符技术来构建模糊关键词集.此方案虽然可以实现对关键词的模糊搜索, 但是存储的数据量较大.Kuzu 等[16]提出了一个模糊关键词搜索方案.利用基于 Jaccard 距离的MinHash 技术实现模糊关键词搜索.Fu 等[14]提出了一个多关键词模糊排序搜索方案.此方案利用关键词转换和局部敏感哈希函数等技术实现了快速、高效的可搜索加密方案.但是方案中在对关键词转换时会产生乱序问题, 使得搜索结果存在一定的误差.Wang 等[17]提出了一个支持范围查询的模糊关键词搜索方案.此方案利用保序加密和局部敏感哈希函数等技术构建索引.
可验证搜索方案.Chai 等[24]首次提出了一个可验证关键词搜索方案.此方案使用基于哈希的索引树, 要求服务器将检索路径的哈希序列作为证据一并返回给用户, 用户可根据证据对搜索结果进行完整性和正确性验证.Kurosawa 等[25]首次提出了 UC-secure 模型下的可验证对称加密方案, 能够验证搜索结果是否被篡改.但此方案需要大量的计算开销和存储空间, 验证过程的计算开销与文件数量是线性关系.Sun 等[26]提出了一个基于双线性映射累加器树的可验证连接关键词搜索方案.但由于使用双线性映射累加器, 所以验证过程的时间耗费较大.Jiang 等[18]提出了一个可验证的多关键词排序搜索方案, 利用一个特殊的数据结构QSet 实现关键词排序搜索.Ge 等[19]提出了一个可验证关键词模糊搜索方案, 利用MAC 可验证机制来验证搜索结果的正确性.Zhu 等[20]提出了一个满足UC-security 的可验证动态模糊关键词搜索方案, 同方案 [26]类似, 由于使用基于公钥密码体制的 RSA 累加器, 所以验证过程的时间耗费较大.Zhu 等[27]在单一数据所有者多数据用户的场景下提出了一个可验证的搜索方案.此方案可以为可搜索对称加密方案提供可验证性.方案中利用Merkle Patricia Tree (MPT) 和Incremental Hash 构建了支持数据更新的验证索引.
图1 系统模型Figure 1 System model
如图1 所示.系统模型中包含三个实体: 数据所有者, 数据用户, 云服务器.数据所有者拥有一个文件集合, 为了保护数据隐私性, 需要将文件进行加密.然后构建安全索引和查找表, 再把密文文件、安全索引和查找表一同上传给云服务器.数据用户是拥有数据所有者分享的私钥的一组用户.当要搜索包含某些关键词的文件时, 首先根据关键词生成陷门, 然后把陷门上传给云服务器.云服务器在接收到授权用户的陷门后, 根据安全索引进行搜索, 然后返回搜索结果给授权用户.授权用户在接收到云服务器返回的加密文件和验证标签后, 对结果进行验证, 若验证通过, 则接受文件, 否则, 则拒绝接受.
提出的方案满足以下要求:
(1) 支持数据去重.当用户想要上传文件时, 云服务器对该文件进行去重检测, 若云服务器未储存该文件, 则允许该文件上传; 否则通知用户该文件已存在, 并为当前用户分配该文件的访问权限.
(2) 支持多关键词模糊搜索.当用户出现关键词拼写错误时, 云服务器仍然能够返回用户最感兴趣的文件.
(3) 支持对搜索结果的验证.当云服务器返回不正确的结果, 在用户对搜索结果验证时能够识别出来.
(4) 支持隐私性保护.在用户上传加密文件和安全索引后, 云服务器不能从加密文件和安全索引中得到关于明文文件和关键词的信息.
方案用到的一些符号标记如表1 所示.
在支持排序的可搜索加密方案中, TF-IDF 规则被广泛用于衡量文件与关键词之间的相关度.词频TF 表示一个给定关键词在某一文件中出现的次数, 一个关键词的TF 值越大, 代表这个关键词在这个文件中越重要; 逆向文档频率IDF 用来衡量一个关键词的普遍重要性, 是通过将文件总数除以包含此关键词的文件数获得的.一个关键词的IDF 值越大, 代表这个关键词越重要.
表1 符号描述Table 1 Symbol description
以下是相关度函数中用到的一些标识:
•fi,j- 关键词wi在文件fj中出现的次数;
• |fj| - 文件fj中关键词的个数;
•F(wi) - 包含关键词wi的文件集合;
• |F(wi)| - 包含关键词wi的文件数;
• TFi,j- 关键词wi在文件fj中的 TF 值;
• IDFi- 关键词wi在文件集合中的 IDF 值.
wi在文件fj中的TF 值、IDF 值、相关度函数分别被定义为
布隆过滤器 (Bloom filter, BF)[9]是一种空间效率高的数据结构.它能够判断一个元素是否属于某个集合.它利用一个m位的数组表示一个集合, 数组的所有位初始化为 0.若要把一个给定的集合S={a1,a2,··· ,an} 插入到布隆过滤器中, 可以利用l个独立哈希函数H={hi|hi:S→m,1 ≤i≤l},分别对集合中的每个元素进行l次哈希映射, 把布隆过滤器中映射到的位置置为1.当检测一个元素q是否属于集合S时, 通过计算l个哈希值得到l个布隆过滤器中的对应位置, 若任意一位为0, 则q不属于集合S; 否则, 认为q属于集合S.一个m位数组的布隆过滤器误识率近似为时, 最优误识率为
局部敏感哈希函数(locality-sensitive Hashing, LSH) 是在一种高维空间中求解近似或精确近邻搜索(near neighbor search) 的算法.对于两个相隔一定距离的相似输入, LSH 函数能够高概率得到相似的输出.若一个哈希函数族H中任意两个点x,y满足:
• 若d(x,y)≤r1; Pr[h(x)=h(y)]≥p1;
• 若d(x,y)≥r1; Pr[h(x)=h(y)]≤p1;称这个哈希函数族为(r1,r2,p1,p2)-sensitive.其中d(x,y) 表示点x和点y之间的距离.
方案中使用的是P-stable LSH 函数族.
• 当p=1, 符合柯西分布, 定义为密度函数
• 当p=2, 符合高斯分布, 定义为密度函数
P-stable LSH 函数定义为
其中a是一个d维的向量,b∈[0,w]是一个实数, 对一个函数族来说,w是固定常数.
因为局部敏感哈希函数以向量作为输入, 所以方案中使用向量表示关键词, 通过一元模型把关键词转换成向量的形式.具体步骤如下:
(1) 关键词转换成一元模型.例如, 关键词 “secure” 的一元模型表示是 {s1,e1,c1,u1,r1,e2}.s1表示关键词中的第一个s,e2表示关键词中的第二个e.
(2) 关键词插入到对应的关键词向量中.对每个关键词生成一个160 位长的向量, 其中26×5=130位表示字母, 剩余 30 位表示数字和符号.一个给定关键词的每一个字母对应在向量中的位置置为1.
收敛加密(convergent encryption)[6]可以在数据去重中提供数据机密性.它的特征是利用明文文件的哈希值作为文件加密的密钥.文件加密密钥也被称为收敛密钥.当上传文件时, 会利用文件生成验证标签, 上传给云服务器用于数据去重检测.若两个文件相同, 则对应的验证标签也会相同.一个收敛加密方案由以下四部分算法构成:
• 密钥生成算法: KeyGen(M) →K.输入明文文件M, 输出收敛密钥K.一般使用哈希函数H1(M)=K来生成收敛密钥;
• 文件加密算法: Enc(K,M)→C.输入明文文件M和收敛密钥K, 输出密文文件C;
• 文件解密算法: Dec(K,C)→M.利用密文文件C和收敛密钥K解密得到明文文件M;
• 标签生成算法: 利用另一哈希函数H2生成用于去重检测的验证标签.
方案的核心过程如图2 所示.首先假定一个对称加密算法ε= {Gen,Enc,Dec}, 其中 Gen 为密钥生成算法, Enc 为加密算法, Dec 为解密算法.
• 密钥生成输入一个安全参数m, 生成一个随机的(m+m′) 位向量S, 两个(m+m′)×(m+m′) 的可逆矩阵M1和M2, 其中m′位为虚拟值; MAC 密钥k; 伪随机变换函数密钥rk; 加密收敛密钥的密钥ck.利用对称加密算法中ε.Gen 生成对称密钥sk.输出密钥集合SK={S,M1,M2,k,rk,ck,sk}.
• 构建索引
从P-stable LSH 函数族H= {h: {0,1}160→ {0,1}m} 中选定l个独立 LSH 函数.为文件fj,j=1,2,··· ,n构建一个m位的布隆过滤器I:
(1) 从文件fj提取关键词集Wfj={w1,w2,···},wi∈ 0,1160.
(2) 对关键词集中的每个关键词wi, 通过hj∈H,1 ≤j≤l插入关键词权重 TF-IDF 值到相应布隆过滤器I中.
图2 方案的核心过程Figure 2 Core process of scheme
(3) 把布隆过滤器扩展到 (m+m′) 位, 在剩余的m′位中插入随机数αi,i=1,··· ,m′.
(4) 加密索引I.根据以下步骤把向量I分成两个向量I′和I′′:
(a) 若sj∈S且sj为 1, 对每个元素ij∈I, 令否则, 选择两个随机数和其中j=1,··· ,(m+m′).
(b) 用可逆矩阵M1和M2加密 {I′,I′′} 生成安全索引
(5) 构建查找表T.查找表的构造形式如图3 所示.关键词域为关键词wi的模糊关键词集的伪随机变换, 其中模糊词集是根据方案[15]中的构造方法, 在编辑距离为1 的情况下构造得到的.标签域为γi和 MACk(wi,vi) 的串联值, 其中γi=ε.Encsk(vi),vi为关键词wi在每个文件中是否出现的向量.若vi,j为1, 则表示第j个文件包含关键词wi; 若为0, 则表示第j个文件不包含关键词wi.
图3 查找表 TFigure 3 Look-up table T
最后, 把所有文件的安全索引和查找表T上传给云服务器.
• 文件上传
在索引上传完成后, 数据所有者开始上传文件集合, 对文件集合中的每个文件f, 根据收敛加密方案的标签生成算法, 计算出上传文件的去重验证标签ηf=H2(f) 上传给云服务器用于数据去重检测:
– 若云服务器上已经存储了该验证标签, 则通知用户检测结果并为其分配访问权限.
– 若云服务器上没有存储该验证标签, 说明文件是首次上传, 则存储该验证标签并由用户计算
出文件的收敛密钥Kf=H1(f), 然后加密文件f得到密文c=EncKf(f) 和加密收敛密钥Kf得到cKf=Encck(Kf).最后, 上传密文c和收敛密钥密文cKf给云服务器.
• 生成陷门
(1) 假设查询关键词集合Wq={w1,··· ,wt}, 为其生成一个m位的布隆过滤器.对于查询关键词wi,i=1,··· ,t, 在经过关键词转换后, 通过相同的l个 LSH 函数hj∈H, 1 ≤j≤l, 插入到布隆过滤器中, 得到查询向量Q.
(2) 把布隆过滤器扩展到 (m+m′) 位, 在剩余的m′位中插入βj,j= 1,··· ,m′, 其中βj∈R{0,1}.
(3) 加密查询向量Q.根据以下步骤把向量Q分成两个向量Q′和Q′′:
(a) 若sj∈S且sj为0, 对每个元素qj∈Q, 令否则, 选择两个随机数和满足其中j=1,··· ,(m+m′).
(b) 用可逆矩阵M1,M2加密 {Q′,Q′′} 生成
(4) 对查询关键词wi∈Wq,i=1,··· ,t, 做伪随机变换生成φrk(wi), 然后插入集合ϕ(Wq) 中.
• 搜索
内积的结果由大到小排序, 并返回给用户前k个文件的密文.
(2) 对于集合ϕ(Wq) 中的每一个φ(wi),i=1,··· ,t, 搜索查找表T中的关键词域, 并返回对应的 vtag 给用户.
• 验证搜索结果
用户接收到搜索结果后做如下验证:
(1) 解析标签 vtagi,i=1,··· ,t得到γi和 MACk(wi,vi).
(a) 对 vtagi,i= 1,··· ,t计算ε.Decsk(γi) 得到vi, 再计算 MAC′k(wi,vi), 然后与MACk(wi,vi) 作比, 若相同则进行下一步验证, 否则拒绝接收.
(b) 计算v=v1∧v2∧···∧vt, 然后查看返回的加密文件集合, 检验v中对应位置是否为1,若都为1 则进行下一步验证, 否则拒绝接收.
(2) 解密收敛密钥密文得到Kf= Decck(cKf), 解密文件密文得到f= DecKf(cf), 然后用户计算并比较Kf和若相同则接收, 否则拒绝接收.
定理1提出的方案满足已知密文模型下的安全性.
证明:在已知密文模型中, 敌手不能根据文件密文、加密索引和陷门推断明文的信息.由于对称加密的安全性, 概率多项式时间的敌手不能以超过的概率区分一个文件的密文C是由明文A或者B加密得到的.而索引和陷门的不可区分性是基于安全kNN 加密[28]的不可区分性和在索引、陷门分裂过程中插入的随机数.通过引入随机数, 相同的搜索请求将会生成不同的查询向量, 使得搜索请求具有不可区分性, 并且最后得到的相关度分数的分布也不同.因此, 查询的不可链接性得到了很好的保证.方案 [14]中查询向量扩展到了 (m+1), 只增加了一位随机数.在提出的方案中, 随机数位数扩展m′位, 使得相同的关键词搜索的结果更加具有不可区分性.最终计算结果如下:
其中IT·Q里包含真实值和随机值
定理 2提出的方案满足已知背景模型下的安全性.
证明:令 Sim 是一个模拟器, 其模拟出的 viewV′与云服务器产生的 view 不可区分.以下为模拟过程:
• Sim 随机选择一个加密向量S′∈{0,1}m+m′, 两个可逆矩阵MAC 密钥k′, 伪随机变换函数密钥 rk′, 并生成加密收敛密钥的密钥 ck′, 加密索引向量的密钥 sk′.令 SK′=
(2) 对每个关键词生成陷门BF′, 以及
• Sim 生成索引I(∆′):
(5) 最后Sim 再对每个关键词生成模糊词集, 并对准确关键词生成索引向量, 构造查找表T′.
定理 3提出的方案满足可验证性.
证明:假设A 是一个多项式时间内的敌手, 他能给出一个伪造的使得其能通过验证算法.如果存在一个这样的 A, 那么它将有悖于 MAC、哈希函数H和对称加密算法ε的安全性.假设包含查询关键词的文件个数大于等于k, 即 |C(W)| ≥k, (Cf,vtag) 是正确的查询结果, 其中Cf={c1,··· ,ck},W= {w1,··· ,wt} 为t个查询关键词的集合, 需要证明敌手 A 无法伪造正确的查询结果,即时, 有以下两种情况需要考虑:
(2) 文件cj没有返回给用户.首先敌手随机选择一个关键词wi∈W, 为其生成一个N-bit 的向量敌手令然后把剩余的位置0.把伪造的返回给用户.由于MAC 可保证消息的不可伪造性, 伪造一个MAC 值使其通过验证的概率是可忽略的.而且对称加密算法满足选择明文攻击安全性, 在不知密钥sk 的情况下是不能伪造出一个正确的加密消息的.
综上所述, 不存在多项式时间内的敌手能够打破方案的可验证性, 因此所提方案满足可验证性.
表2 为本文方案与文献[14]和文献[2]的方案在功能上比较的结果.从表中可以看出, 文献[14]不能支持数据去重以及对搜索结果的可验证, 文献[2]支持数据去重, 虽然可以支持可验证, 但是只能验证返回的文件内容正确与否, 不能验证文件是否包含查询关键词.而提出的方案能够支持多关键词模糊搜索, 能对搜索结果进行排序, 实现对云中数据的去重, 还能验证返回结果是否包含搜索关键词以及文件是否被篡改.
表2 功能比较Table 2 Functionality comparison
如表3 所示, 本文方案与文献[14]和文献[2]的方案在索引建立、搜索和验证阶段进行了效率比较.
表3 效率分析Table 3 Efficiency analysis
其中,t为搜索关键词的个数,k为返回的文件个数.方案中生成一个索引向量需要O(m+m′) 的时间, 向量分裂需要O(m+m′) 的时间, 矩阵相乘需要O((m+m′)2) 的时间, 所以索引建立时间复杂度为O(N(m+m′)2).由于所提方案中的索引能够实现对搜索结果的排序, 所以索引建立上要比方案[2]耗时, 而且建立索引是线下完成的, 只需建立一次.所提方案中云服务器执行搜索操作的时间耗费为O(N(m+m′)2).由于在每个文件中进行搜索时需要对两个(m+m′) 位的向量执行内积运算, 所以每个文件搜索需要O((m+m′)2) 的时间.验证返回文件是否被篡改需要O(k) 的时间, 验证返回文件是否包含搜索关键词需要O(2t) 的时间, 所以验证搜索结果需要O(2t+k) 的时间.由于方案 [2]不能验证返回文件是否包含搜索关键词, 所以验证效率为O(k).
提出一个支持数据去重, 对搜索结果可验证的模糊多关键词搜索方案.为了降低云服务器上数据冗余和减少用户的网络带宽开销, 根据收敛加密实现对云服务器上加密数据去重; 为了解决用户搜索时出现的关键词错误拼写等问题, 利用局部敏感哈希函数实现对关键词搜索的模糊处理; 为了验证搜索结果的正确性, 利用消息验证码和伪随机函数生成验证标签, 保证搜索结果的真实性.安全性分析和功能比较、效率分析显示所提方案是安全、高效的.