随着云计算的迅速发展, 云存储技术被广泛地应用, 用户逐渐将数据迁移到云端服务器, 来避免本地庞大的存储开销以及繁琐的数据管理, 并获得更便捷的服务.但云端自身的开放性和共享性^[1], 同样给存储在分布式环境中的数据安全性带来了非常大的挑战.为了保证数据安全性以及用户隐私, 数据一般都是以密文的形式存储在云端服务器中.但是明文数据经过加密变为密文后, 虽然保证了数据的机密性及安全性, 却丧失了许多明文数据原有的特性, 使得在密文上进行关键字查找成为了难题.可搜索加密^[2](searchable encryption, SE)技术是近几年发展起来的支持在密文上进行关键字搜索的密码学原语, 它为用户节省大量的计算和网络开销, 并充分利用云环境中的分布式存储和计算能力进行密文上的关键字查找.随着云计算的发展, 在海量用户和海量数据的应用场景下, 提供安全灵活高效的SE机制将是研究者所极力追求的目标之一^[2-3].

根据构造方法的不同, 可搜索加密可分为基于对称加密的可搜索加密方案以及基于公钥加密的可搜索加密方案.在可搜索加密方案中, 用户首先使用加密算法对数据进行加密, 并将密文存储到云端服务器中; 当用户发起搜索请求时, 发送关键字陷门给云端服务器, 服务器将收到的陷门对每个文件进行试探匹配, 如果匹配成功, 说明文件中包含该关键字; 最后服务器将匹配到的文件密文发回给用户, 用户只需要对返回的文件进行解密.在安全性上, 云端服务器除了得到访问模式、搜索模式以及文件密文、密文大小、文件个数等信息外, 不会获得所搜索的关键字内容以及明文的任何信息.

Song等^[4]首先提出了适用于单用户模型的对称可搜索加密(symmetric searchable encryption, SSE)方案——SWP方案, 完成了关键字搜索功能, 开创了实用性的可搜索加密机制来实现在密文上进行关键字搜索的先例.该方案在搜索时需要对每个文件进行扫描, 以匹配搜索的关键字, 这使其搜索时间与文件大小呈线性相关, 搜索效率低下, 不适用于大型数据集下的搜索.针对其缺陷, Goh^[5]找到了一种基于Bloom Filter建立安全索引的方法, 将搜索时间提高到线性时间.之后, Chang等^[6]利用矢量索引, 提出了基于关键字字典的加密方案.为了提高安全性, Stefanov等^[7]提出了动态可搜索加密方案(dynamic SSE), 该方案较之前的方案具有更小的泄露量和更高的效率.在用户数据较大情况下, Cash等^[8]又提出了一种新的dynamic SSE方案, 该方案利用Multi-map数据结构, 完成了对安全索引的优化, 实现了安全索引较大情况下的单关键字搜索密文.Kamara等^[9]使用Multi-map数据结构实现了多关键字查询, 并得到了更优的通信复杂性和更少的泄露.

虽然目前多数可搜索加密方案中的索引在理论上具有最佳的搜索时间, 但是在大型数据集上执行的性能却并不理想.并且, I/O延迟、存储利用率、以及数据集分布式存储都会降低对称可搜索加密方案的实际性能^[10].当面向大型数据集时, 构建安全索引过大, 并且通过安全索引顺序地匹配关键字进行搜索, 是实践中搜索效率低下的一个重要原因.

为解决在可搜索加密方案安全索引生成过程中由于关键字对应文件标识信息的键值对数量过多造成安全索引过大, 导致传统方案搜索时间复杂度过高这一问题, 本文提出分布式环境下针对大型数据集的可搜索加密方案, 该方案通过在安全索引生成算法中将索引分层进行间接寻址的思想, 优化了安全索引的存储结构, 使得在安全索引过大的情况下, 仍然保持一个良好的时间复杂度.同时, 用户在上传数据的过程中, 对数据进行加密操作, 使得服务器无法获取数据信息, 从而保证了数据的机密性.

1 预备知识 1.1 基于安全索引的可搜索加密方案

基于安全索引的可搜索加密方案中, 明文数据在本地进行加密处理得到密文数据, 之后将密文数据及生成的安全索引上传至云端服务器.在进行搜索的过程中, 云端服务器根据安全索引与用户输入的搜索关键字集合进行计算, 得到最终的搜索结果.其形式化定义为

Scheme=(KeyGen, IndexGen, TrapdoorGen, Search).

K←KeyGen(1^k):密钥生成算法, 输入为安全参数k, 输出为主密钥K.该算法为概率性算法.

I_F←IndexGen_K(F):安全索引生成算法, 输入为主密钥K及原始文件集F, 输出F的安全索引I_F.该算法为确定性算法.

τ_w←TrapdoorGen_K(w):陷门生成算法, 输入为主密钥K以及关键字w, 输出为该w对应的陷门τ_w.该算法为确定性算法.

b_{{0, 1}}←Search(τ_w, I_F):匹配算法, 输入为τ_w及I_F, 输出为F中关键字w匹配结果b_{{0, 1}}.当b=0时, 表示I_F中不包含w, 即认为F中未匹配到w; 当b=1时, 表示I_F中包含w, 即认为F中匹配到w.该算法为确定性算法.

1.2 亚线性曲线

亚线性(sublinear)是用于描述变量之间变化关系的概念.例如对于函数y=a+bxⁿ, 当n=1时, x与y之间的变化关系为线性关系; 当0 < n < 1时, x与y之间的变化关系即为亚线性关系, 其图像为亚线性曲线.

亚线性曲线典型的特性是y的变化速率随着x的增大而减小, 即其一阶导数随着x的增大而减少.

2 密文大型数据集可搜索加密方案 2.1 参与的实体

1) 数据拥有者.拥有的数据:原始文件集、安全索引、关键词陷门、密钥; 参与的活动:文本分词、文件上传和下载、文件加解密、安全索引生成、关键字陷门生成.

2) 索引服务器.拥有的数据:安全索引; 参与的活动:索引信息检索.

3) 数据服务器.拥有的数据:加密后的数据集; 参与的活动:文件检索.

2.2 系统模型

为了保证数据的机密性, 本文的系统模型中数据的处理过程均在本地完成, 分布式服务器作为云存储服务的提供者, 除了存储密文数据及索引, 还会根据数据拥有者的请求执行密文数据的搜索任务.此外, 假设云端服务器是诚实且好奇的, 服务器会执行正确的搜索操作并且返回所有的搜索结果, 但也会尝试获取用户的数据隐私.本文的系统模型主要包括3个阶段:文件上传、关键字搜索以及文件下载.

文件上传阶段:数据拥有者Owner_F首先对原始文件集进行预处理, 包括使用对称加密生成密文数据、对原始文件集F进行语义分析并提取关键词、为关键词构造倒排索引并生成加密索引I; 之后, 数据拥有者将密文数据按照某种规则等分为N份上传至数据服务器S_F1, S_F2, …, S_FN, 并将加密索引上传至索引服务器S_I.

关键词搜索阶段:Owner_F向S_I发出对关键词w搜索请求, 并向S_I提供陷门τ_w; S_I根据τ_w及I计算出w所在的数据服务器S_F; S_F向Owner_F返回τ_w对应的密文数据E(f₁, f₂, …).

文件下载阶段:Owner_F下载E(f₁, f₂, …), 使用K解密E(f₁, f₂, …)，得到包含原始文件集f₁, f₂, ….

2.3 数据结构

本文中分布式环境下大型数据集的可搜索加密方案所用到的数据结构如下:

1) 关键词-文档倒排索引结构.本文中使用Multi-map(K, V)集合建立关键词-文档矩阵模型.

2) 安全索引块状存储结构.传统基于安全索引的SSE方案中, 执行搜索会遍历整个加密索引, 使得在安全索引过大情况下会浪费很多时间.本文通过调整安全索引的存储结构, 减少安全索引的搜索时间.

安全索引块状结构构造过程如下:

1) 给定索引分块参数B和b, 根据关键词w的倒排索引长度|DB(w)|将DB(w)分为Small, Medium, Large三类:

2) DB(w)⊆Small时, 取分块个数Num_BS=1, 即无需分块操作, 当|DB(w)| < b时, 进行随机数据填充, 补齐到b大小, 记该块为Block_S.

3) DB(w)⊆Medium时, 取分块个数Num_BM=「BD(w)/B⌉, Num_BM≤b, 最后一块不足B大小的, 进行随机数据填充, 补齐到B大小.对于每个分块BM_i, I≤i≤Num_BM，使用对称加密计算其标签tag_BMi, 将tag_BMi随机存储到S_I中, 其指针记为address_BMi, 得到二元组 < address_BMi, tag_BMi>, 其中, 1≤i≤Num_BM.将address_BMi写入数组A中, 对A按照b大小进行分块, 取分块个数Num_BM=「Len(address_BM)/b⌉, 由于Num_BM≤b, 此时仅分为一块, 即Num_bL=1, 分块中若不足b大小, 进行随机数据填充, 补齐到b大小, 记该块为Block_M, 该过程实际是进行一次间接寻址操作.

4) DB(w)⊆Large时, 取分块个数Num_BL=「DB(w)/B⌉, b < Num_BL≤Bb, 在计算得到数组A后, 对A中的Num_BL条数据继续按照B大小进行分块操作, 进行第二次间接寻址.取分块个数Num_BL=「Len(address_BL/B⌉, Num_BL≤b, 最后一块不足B大小的, 进行随机数据填充, 补齐到B大小.对于每个分块BL′_j, 1≤j≤Num′_BL, 使用对称加密算法计算其标签tag_BL′j, 将BL_j′随机存储到S_I中, 其指针记为address_BL′j, 得到二元组 < address_BL′j, tag_BL′j>, 其中, 1≤j≤Num′_BL.将address_BL′j写入数组A.最后, 将A中由address_BL′j组成的数据按照b大小进行分块, 取分块个数Num_bL=「Len(address_BL′)/b⌉, 由于Num_BL′≤b, 此时仅分为一块, 即Num_bL=1, 分块中若不足b大小, 进行随机数据填充, 补齐到b大小, 记该分块为Block_L.

按照上述方法分类后, 得到用来存储块信息的A以及Block, 之后将Block和使用K生成的加密标签存储在列表L，记录间接寻址时用的指针列表.搜索过程中, DB(w)⊆Small时, 进行直接寻址, 返回搜索结果; DB(w)⊆Medium时, 进行一次间接寻址, 返回搜索结果; DB(w)⊆Large时, 进行两次间接寻址, 返回搜索结果.在进行安全索引块状结构构建过程中, 分块大小B和b由数据所有者按照原始文件集大小进行指定.一般地, 单一数据拥有者的DB(w)大小不会超过B²b, 因此分为三类即可.

2.4 形式化定义

本方案由密钥生成算法、文件加密算法、安全索引生成算法、陷门生成算法、搜索算法、更新算法和文件解密算法等7个多项式时间算法构成, 其形式化定义为

LDSSE=(KeyGen, Enc, IndexGen, TrapdoorGen, Search, Update, Dec).

1) 密钥生成算法:K←KeyGen(k)为概率性算法, 输入安全参数k, 输出密钥K;

2) 文件加密算法:c←Enc(f)为确定性算法, 输入原始文件f, 输出加密文件c;

3) 安全索引生成算法:

EDB ←IndexGen(K, PRF, W, DB), 输入密钥K、长度可变的伪随机函数PRF、关键字集W和倒排索引DB, 输出安全索引EDB;

4) 陷门生成算法:τ←TrapdoorGen(K, w)为确定性算法, 输入密钥K和关键字w, 输出其陷门τ;

5) 搜索算法:c_res←Search(τ, EDB), 输入陷门τ和安全索引EDB, 输出τ对应的密文集c_res;

6) 更新算法:EDB′←Update(K, PRF, F_op), 输入密钥K、长度可变的伪随机函数PRF、更新操作op ∈{add, del}的原始文件F, 输出更新安全索引EDB′;

7) 文件解密算法:f←Dec(c)为确定性算法, 输入密文文件c, 输出c对应的原始文件f.

2.5 安全性定义

对于一个SSE方案, 其安全性保证:给定安全索引DB及密文集合c, 没有敌手可以知道原始文件集F的任何信息, 同时对于关键词搜索询问Q=(w₁, w₂, …, w_q), 没有敌手可以知道Q的任何信息.但是要实现这样的安全性是很困难的, 已知最好的SSE方案也泄露了访问模式和搜索模式, 因此适当地弱化安全性, 允许泄露给敌手一些有限的信息.

定义泄露函数L₁(F)和L₂(F, W)来表示本方案中允许泄露的信息.

(m, n, u, s)←L₁(F):输入原始文件集F, 输出关键字个数m、文件个数n、文件标识符u以及每个文档大小s.

(ξ, ζ)←L₂(F, w):输入原始文件集F和关键词w, 输出搜索模式ξ和访问模式ζ.

系统安全性满足以下要求:

1) 安全索引不向服务器泄露除L₁和L₂以外任何对获取文件内容有价值的信息;

2) 客户端和云端服务器进行交互的过程中, 云端服务器不会获得文件上传或更新过程中任何明文信息.

定义1  可忽略函数:对于任意一个多项式函数μ(x):N→R, 总存在一个自然数C, 当x>C时, p(x) < 1/μ(x)总成立, 称p(x)为可忽略函数.反之, 称p(x)为不可忽略函数.

定义敌手A, 挑战者C, 有状态的模拟器S, G_real为A与C之间的交互游戏, G_ideal为A与S之间的交互游戏.

定义2  动态自适应安全性:存在一个多项式时间算法PPT内的模拟器S, 对于任何PPT内的敌手A, 其优势:

Adv_{A, S}(k)=|P[G_real=1]-P[G_ideal=1]|≤negl(k)成立, 则称该SSE方案满足动态自适应安全, 其中negl(k)为可忽略函数.

2.6 方案的具体构造

面向密文大型数据集的对称可搜索加密方案由密钥生成算法KeyGen(k)、文件加密算法Enc_K(F)、安全索引生成算法IndexGen_K(W, DB(W))、陷门生成算法TrapdoorGen_K(w)、搜索算法Search((τ₁, τ₂), I)、更新算法Update_K(add, del)和文件解密算法Dec_K(c)构成, 具体描述如下:

1) KeyGen(k):数据拥有者执行该算法, 输入安全参数k, 使用伪随机数生成器{0, 1}^k生成3个随机数K₁, K₂, K₃作为伪随机函数PRF的密钥.然后通过K₃←SKE.Gen(1^k)来加密文档集F, 输出K=(K₁, K₂, K₃)作为密钥.其中SKE=(Gen, Enc, Dec)为一个对称加密方案.

2) Enc_K(F):数据拥有者执行该算法, 输入原始文件集F, 使用密钥K生成密文c.对于文件f_i, 执行c_i←SKE.Enc_K3(f_i), 0 < i≤|F|, 产生密文c_i, 并按照某种规则发送给云端服务器S_F.

3) IndexGen_K(W, DB(W)):数据拥有者执行该算法, 输入关键字集W及倒排索引集DB(W).对于关键词w∈W, 执行K₁, K₂←F(w), 生成与w对应的密钥K₁和K₂; 对于其倒排索引DB(w), 按照|DB(w)|分别执行:

当DB(w)⊆Small时, 执行

α←F_K1(0), β←Enc_K2(Block_S),

L←(α, β),

产生列表L并上传至S_I;

当DB(w)⊆Medium时, 执行

产生列表L并上传至S_I；

当DB(w)⊆Large时，执行

产生列表L并上传至S_I.

L产生后, 执行D←Create(L), 产生字典D.最后输出K, D, A.

4) TrapdoorGen_K(w):数据拥有者执行该算法, 输入搜索关键词w, 执行(τ₁, τ₂)←F_{K1, K2}(w), 生成与w对应的陷门τ₁和τ₂, 将(τ₁, τ₂)作为w的搜索令牌上传给S_I.

5) Search((τ₁, τ₂), I):索引服务器S_I执行该算法, 输入(τ₁, τ₂)和I, 输出(τ₁, τ₂)对应的密文集c_res.其过程为

执行α←F_τ1(I)，获得DB(w)所属分类；

当DB(w)⊆Small时，执行

Block_S←Dec_τ2(D), c_res←Get(S_F; Block_S)；

当DB(w)⊆Medium时，执行

Block_M←Dec_τ2(D), (address_BM1, …, address_BMb)←Block_M,

c_res←Get(S_F, (tag_BM1, …, tag_BMb));

当DB(w)⊆Large时，执行

Block_L←Dec_τ2(D),

(address_BL′1, …, address_BL′b)←Block_L,

(Block₁, …, Block_NumBL′)←Dec_τ2(tag_BL′1, …, tag_BL′b),

(tag_BL1, …, tag_BLd)←(Block₁, …, Block_d)//d=Num_BL,

c_res←Get(S_F, (tag_BL1, …, tag_BLd)).

6) Update_K(add, del)：算法包括文件添加(add)和文件删除(del)两个子过程，数据拥有者执行.

① 文件添加过程:

为了降低在现有安全索引的基础上做更新操作的计算代价, 新增字典D_add, 其构造过程和D类似, 来存储新添加文件的索引信息.

输入待添加的原始文件集F_add, 执行Enc_K(F_add)产生密文c_add并上传至S_F;

输入待添加的关键字集合W_add及倒排索引集DB(W_add), 执行Enc_K(W_add, DB(W_add))产生L_add并上传至S_I, 输出K, D_add, A_add.

② 文件删除过程:

新增字典D_del, 其构造过程和D相同, 来存储删除文件的索引信息.

输入待删除的原始文件集F_del, 提取F_del的关键字集W_del并生成倒排索引集DB(W_del), 执行Enc_K(W_del, DB(W_del))产生L_del并上传至S_I, 输出K, D_del, A_del.

文件添加或删除结束后, 对于搜索关键字w, 其搜索过程转化为对于D+D_add-D_del的搜索, 方法同Search_K(w), 最后将三部分的搜索结果进行合并返回给c_res, 并在客户端进行解密即可.

7) Dec_K(c):数据拥有者执行该算法, 输入搜索后返回的密文c, 使用对称加密算法将c还原为明文文件.对于密文c_i, 执行

f_i←SKE.Dec_K3(c_i)，0 < i≤|c_res|，

还原对应明文f_i, 其中c_res为搜索后返回的密文集.

3 安全性及效率分析 3.1 安全性证明

本文在L₁和L₂的前提下给出了选择关键字安全性定义, 其安全性证明的主要目标是在证明L₁和L₂之外, 所有PPT敌手都无法从密文和查询列表中获得任何有用的信息.

定义游戏G_real0, G_real1, G_ideal0和G_ideal1, 其中G_real0和G_real1代表real过程, G_ideal0和G_ideal1代表ideal过程.定义Q=(w₁, w₂, …, w_q)表示q次关键词询问, 每次询问仅包含一个关键词.

在G_real0和G_real1中, 选择密钥K, 使用PRF计算w对应的陷门τ, 并使用K为所选DB中的每个关键字计算其<标签, 密文>对, 然后创建字典.其形式化定义如下:

在G_real1中, τ_i的返回过程和K的生成过程与G_real0不同.由形式化定义可知, 在G_real0中P[G_real0]=P[Real(k)=1]；在G_real1中, 对于一个有效的敌手Α₁, 其优势

根据使用PRF不同, 在G_real0和G_real1中, 得到

在G_ideal0和G_ideal1中, 该游戏实际是对G_real1, 的演变, 对于查询Q=(w₁, w₂, …, w_q), 若w_j不在Q中, 则随机选取标签l, 从可能未初始化的表P中读取.其形式化定义如下:

对比G_real0和G_real1, G_ideal0和G_ideal1更加精简, 但是对于每个w, G_ideal0和G_ideal1又进行了一次遍历, 对于一个有效敌手Α₂, 其优势

结合G_real0, 之前的概率计算公式可以转化为

在G_ideal1中, 当w_j∉Q时, 用一个新的字符串{0, 1}^l(k)来代替C, 对于一个有效敌手A₃, 其优势

G_ideal0和G_real1的概率关系为

对于G_ideal1, 有P[G_ideal1]=P[Sim_{A, S}(k)=1].

因此, 对于本方案, 其优势

综上, 对于所有有效敌手A, 除了可忽略概率negl(k), Real_{A, S}(k)和Sim_{A, S}(k)的输出是一致的.即|P[Real_{A, S}(k)=1]-P[Sim_{A, S}(k)=1]|=negl(k).

因此, 若敌手能以可忽略的概率区分真实环境和理想环境, 本方案基于云存储环境下的对称可搜索加密满足动态自适应安全.

3.2 效率分析

本方案在1台实体机及4台虚拟机上完成仿真, 其中实体机作为客户端及索引服务器, 虚拟机作为数据服务器.数据来源为搜狗实验室^[11]提供的2012年6月至7月产生的部分新闻数据以及Enron公开邮件数据^[12].

针对大型数据集, 本方案通过大小不同的安全索引的搜索时间来研究关键词搜索性能.安全索引的大小在一定程度上反映了关键词-文件信息映射对数的大小, 随着安全索引的增大, 其映射对数也不断增大.实验中, 在相同的搜索关键字集合下, 使用5种大小的安全索引进行搜索查询, 其大小分别为100, 200, 300, 400, 500 KB.

在传统方案中, 不对上述安全索引作任何存储结构处理, 搜索时直接对安全索引进行遍历操作; 在本文提出的方案中, 对上述安全索引存储前先进行一次块状结构处理, 搜索时通过安全索引块状结构完成.通过对比以上5种安全索引大小的差异性引发的关键词搜索时间的差异性结果, 得到如图 1所示的搜索时间与安全索引大小关系图.

图 1表明, 安全索引的大小发生变化时, 会对搜索时间产生影响, 安全索引越大, 搜索时间也会越长; 在搜索过程中, 与传统的遍历整个安全索引的方法相比, 当安全索引较小时, 本方案的优势并不明显, 甚至搜索时间要略高于传统遍历安全索引方案, 但随着安全索引的增大, 本方案的优势逐渐显现, 搜索时间与传统方案相比越来越短.

本方案使用安全索引分块的思想优化了安全索引的数据结构, 根据安全索引的大小在关键字搜索过程中进行直接或间接寻址, 从而摆脱了传统SSE中需遍历整个安全索引的缺陷.随着安全索引的增大, 当安全索引超过200 KB后, 搜索时间随着安全索引的增大不再呈线性增长, 而降至亚线性增长, 从而提高了搜索效率.

4 结语

本文提出了一种云环境下针对密文大型数据集的可搜索加密方案, 通过对可搜索加密方案中安全索引的优化, 解决了传统可搜索加密方案在安全索引过大情况下搜索时间复杂度过高的问题, 并且该方案满足动态自适应安全.