基于BSSEVD的可搜索加密方案原型系统设计与实现

厉 鹏， 周福才， 张 帅

(1. 东北大学 软件学院， 辽宁 沈阳 110169； 2. 辽东学院 信息工程学院， 辽宁 丹东 118000)

随着云存储技术应用的日益普及，云存储服务以其价格低廉、可扩展性高等特点吸引了大量用户.但是，在云存储服务带来极大的便利的同时，许多安全问题也随之产生，网络攻击技术日新月异的发展以及人们对经济利益的不当追逐，导致云存储服务器可能同时面临外部敌手的攻击或服务器内部管理者的人为泄漏和破坏.为了防止云服务器及其他非授权用户获取这些数据，加密技术是最安全有效的手段之一.然而，明文数据在经过加密方法的处理变成密文数据之后，会丧失许多原有特性[1]，虽然通过这种方式保证了用户存储在云端的数据的机密性，但同时也使得用户的许多应用无法直接在密文数据上进行，例如：通过关键字来搜索密文文件.

最早可搜索加密[2](searchable encryption，SE)这一概念是由Goldreich和Ostrovsky提出的，是在不解密密文情况下实现对加密数据的搜索.Song 等[3]在2000年首先提出了基于密文扫描思想的SWP方案，该方案将明文文件划分为“关键字”，并对关键字进行特殊的双层加密.该方案基于对称密码学算法实现在密文上进行关键字搜索，然而，该方案需要扫描整个文件，搜索效率极低，不适合大型数据集.在此基础上，Goh[4]在2003年提出了一种利用安全索引进行关键字搜索的SE方案.该方案基于文件和关键字构建安全索引，安全索引不会向服务器泄露关于明文文件和关键字的任何信息.在可搜索加密领域，已有很多研究者从实现的角度来提出可搜索加密方案，可以大致分为两类：基于对称密钥的可搜索加密方法以及基于公钥加密的可搜索加密方法.文献[3-7]提出基于对称加密的可搜索加密方法，文献[8-13]提出基于公钥加密的可搜索加密方法.在用户数据集较大情况下，由Cash等[14]提出了一种动态可搜索加密方案，该方案利用multi-map的结构特性，对安全索引进行了优化，可实现大型安全索引情况下的单关键字密文搜索.

通过以上分析，目前的可搜索加密方法虽然可以实现在密文数据上进行关键字搜索，但依然存在以下两个问题：1)在大型数据集条件下，关键字对应文件信息的键值对数量过多，使得安全索引过大，从而导致传统可搜索加密方案的关键字搜索时间复杂度过高、效率低；2)方案多为单关键字搜索方案，不能满足实际应用中对多关键字布尔搜索的需求.

针对以上两个问题，论文提出了大型数据集下支持布尔搜索的可搜索加密(BSSEVD，Boolean symmetric searchable encryption in very-large databases)方案，包括初始化算法、搜索令牌生成算法、搜索算法三个主要算法，以及文件加密算法、文件解密算法.该方案在保证访问模式不泄露的前提下，提供一种在大型数据集条件下支持布尔搜索的可搜索加密方案.在该方案基础上，设计与实现原型系统.

1 BSSEVD方案

1.1 BSSEVD架构

大型数据集下支持布尔搜索的可搜索加密(BSSEVD)方案的架构如图1所示.

在图1中，BSSEVD方案中包括两个实体：数据拥有者和云存储服务器.

数据拥有者(用户)：负责在本地进行原始文件集预处理和初始化处理，生成安全索引结构以及密文数据文件，将其上传至云服务器进行存储；搜索阶段负责布尔搜索表达式解析、搜索令牌生成，并将搜索请求发送给云存储服务器.

云存储服务器：云存储服务器存储加密文件和加密索引，并利用用户的搜索令牌实现高效安全的多关键字布尔搜索计算，并将搜索结果返回给数据拥有者(客户).

1.2 方案模型

本方案主要由5个多项式时间算法：初始化算法、文件加密算法、令牌生成算法、搜索算法、文件解密算法组成，大型数据集下支持布尔搜索的可搜索加密方案可形式化描述为BSSEVD=(Init，Enc，TokenGen，Search，Dec).下面对方案中的5个算法进行形式化定义.

1) 初始化算法：(K,IE)←Init(1k,IP)为概率性算法.输入安全参数k和明文倒排索引IP，输出令牌生成密钥K和安全索引IE.

2) 文件加密算法：c←Enc(Kc,f)为确定性算法.输入对称加密密钥Kc和文件集合f，输出密文集合c.

3) 令牌生成算法：tk←TokenGen(K,Bw)为概率性算法.输入令牌生成密钥K和搜索布尔表达式Bw，输出搜索令牌tk.

4) 搜索算法：R←Search(tk,IE)为确定性算法.输入搜索令牌tk和安全索引IE，输出搜索令牌所对应的含有密文标签信息的搜索结果集合R.

5) 文件解密算法：f←Dec(Kc,c)为确定性算法.输入对称加密密钥Kc和密文文件c，输出为明文文件f.

1.3 关键技术

1) 倒排索引.倒排索引(inverted index)是一种实现关键字到文件映射关系的有效索引结构，是实现“关键字-文件矩阵”的一种具体存储形式.通过倒排索引，可以根据关键字快速检索出包含这个关键字的文件列表.倒排索引主要由两部分组成：关键字字典和倒排文件.

关键字字典(lexicon)：关键字字典是由文件集合中出现过的所有关键字构成的字符串集合，关键字字典内的索引项中记录着关键字本身的信息以及指向“倒排列表”的指针.倒排列表中记录着出现过某个关键字的所有文件的相关信息，每条记录被称之为一个倒排项.

倒排文件(inverted file)：所有关键字的倒排列表一般顺序地存储在磁盘上的某个文件中，这个文件被称之为倒排文件.

2) 分层块状安全索引结构.传统方案基于安全索引的可搜索加密方案，在大型数据集下构建的庞大索引中，通过顺序匹配关键字实现关键字搜索的方法效率低.受到数据存储在外部存储器(磁盘)与存储在内部存储器中读取效率的差异巨大的启发，通过将安全索引三层分块进行间接搜索的方法，优化安全索引结构，使本方案在安全索引过大情况下，仍然具有良好的搜索性能.

分层块状安全索引构造过程：

①设定分块参数B和b，关键字ω倒排索引长度不大于B2b.如果一级分块长度不足b，二级、三级分块长度不足B，填充随机数据.

②当关键字ω倒排索引长度|IP(ω)|≤b，形成1块一级索引块.

③当b<|IP(ω)|≤Bb，将IP(ω)分成「IP(ω)/B⎤块，作为二级索引块.计算得到「IP(ω)/B⎤个块的标签和块指针键值对，形成1块一级索引块.

④当Bb<|IP(ω)|≤B2b，将IP(ω)分成「IP(ω)/B⎤块作为三级索引块，计算得到「IP(ω)/B⎤个三级索引块的标签和块指针键值对，再将其分成「IP(ω)/B/B⎤块作为二级索引块，计算得到「IP(ω)/B/B⎤个二级索引块的标签和块指针键值对，形成1块一级索引块.

2 关键算法描述

本方案涉及的5个算法中文件加密算法、文件解密算法与传统可搜索加密方案类似，使用成熟的对称加密算法，故在本文中主要介绍大型数据集下支持布尔搜索的可搜索加密方案的核心内容——初始化算法、令牌生成算法、搜索算法.算法中应用到传统SSE方案中的伪随机数函数F、对称加密算法Enc、字典加密算法DX(Init，TokenGen，Search)和multi-map加密算法MM(Init，TokenGen，Search)不在此赘述.算法中涉及的符号定义如表1所示.下面分别对这3个主要算法进行具体的描述.

表1 符号说明Table 1 Instructions of symbol

2.1 初始化算法

初始化算法Init(1k,IP)：数据拥有者执行该算法.算法的主要工作是对文件预处理构建完成的明文倒排索引IP进行加密、关键字交集索引计算、分块处理构建安全索引IE，并生成搜索令牌生成密钥K.具体算法执行步骤如下：

1) 利用安全参数k，使用伪随机数生成器生成随机数K1,K2作为随机函数的密钥.

2) 初始化字典结构DP和multi-map结构GMM.

3) 生成单关键字的加密倒排索引和关键字交集加密倒排索引.对关键字集合W中的每一个关键字ω，执行如下操作：

①使用伪随机函数F为包含关键字ω的每一个文件计算标识符加密标签tagid.

②根据用户定义的分块参数B,b，将包含关键字ω的文件标识符加密标签(tagid)id∈IP(ω)分块存入GMM[ω].

③初始化一个#tl(ω)大小的multi-map结构IMM，计算关键字ω与tl(ω)中每一个关键字v的文件标识符交集，为交集中每一个文件计算标识符加密标签tagid，分块存入IMM[v].应用multi-map加密算法加密生成关键字ω的交集安全所引IMME和密钥Kω，将安全索引IMME存入字典DP[ω].

4) 应用字典加密算法加密字典DP，生成关键字交集安全索引字典DE和密钥Kd.

5) 应用multi-map加密算法加密GMM生成单关键字安全索引GMME和密钥Kg.

6) 生成完整的安全索引IE和令牌生成密钥K，并输出.

初始化算法伪代码:

02 create a dictionaryDPand a multi-map GMM；

03 for allω∈W:

04 for all id∈IP(ω):tagid:=EncK1(id;FK2(id‖ω))；

05 Btagω:=Blockput((tagid)id∈IP(ω),B,b)；

06 GMM[ω]:=Btagω；

07 create a multi-map IMM of size #tl(ω)；

08 for allv∈tl(ω):

09 SI=Intersection(IP(v)，IP(ω));

10 for all id∈SI:

tagid:=EncK1(id;FK2(id‖ω))；

11 Btagν:=Blockput((tagid)id∈IP(ν)∩IP(ω),B,b)；

12 IMM[v]:=Btagν；

13 (Kω,IMME)←∑MMInit(1k,IMM)；

14DP[ω]:=IMME；

15 (Kd,DE)←∑DXInit(1k,DP)；

16 (Kg,GMME)←∑MMInit(1k,GMM)；

17K=(Kg,Kd,{Kω}ω∈W)；

18IE=(GMME,DE)；

19 ouput(K,IE).

2.2 令牌生成算法

令牌生成算法TokenGen(K，Bw)：数据拥有者执行该算法.解析用户输入的布尔搜索表达式Bw，利用初始化生成的令牌生成密钥K，生成对应的搜索令牌tk.具体算法执行步骤如下：

1) 解析密钥K，得到GMME加密密钥Kg，DE密钥加密Kd，DE中IMME加密密钥Kω.

2) 解析布尔搜索表达式Bw，转换成合取范式(conjunctive normal form ，CNF)Δ1∧…∧Δl.Δl为搜索关键字的析取范式(disjunctive normal form ，DNF)Δi=ωi,1∨…∨ωi,q.

3) 生成搜索Δ1的令牌tk1，具体过程如下：

①从关键字ω1,1至ω1,q-1：生成ω1,i对应的GMME搜索令牌gtk1,i，生成ω1,i对应的DE搜索令牌dtk1,i，生成ω1,i+1到ω1,#Δ1中ω1,j与ω1,i的交集对应的IMME搜索令牌Itk1,i,j.合并生成ω1,i对应的交集搜索令牌集合tk1,i=(dtk1,i,gtk1,i,Itk1,i,i+1,…,Itk1,i,#Δ1).

②生成Δ1中最后一个关键字ω1,q对应的GMME搜索令牌gtk1,q.

③生成Δ1的搜索令牌tk1=(tk1,1,…,tk1,q-1,gtk1,q).

4) 生成从Δ2到Δl对应的搜索令牌tk2,…,tkl，具体过程执行如下：

①生成Δi中关键字ωi,j和Δ1中关键字ωi,s的交集搜索令牌Itks,i,j，组合生成Δi中关键字ωi,j与Δl的交集搜索令牌Itki,j=(Itk1,i,j,…,Itkq,i,j).

②将Δi中关键字ωi,j与Δ1的交集搜索令牌组合生成Δi与Δ1的交集搜索令牌tki=(Itki,1,…,Itki,l)，也可称之为Δi的搜索令牌.

5) 将Δ1到Δl的令牌组合生成总搜索令牌tk=(tk1,…,tkl)，并输出.

令牌生成算法伪代码:

01 convertKto(Kg,Kd,{Kω}ω∈W)；

02 convert Bw to(Δ1∧…∧Δl)where fori∈[l]，

Δi=(ωi,1∨…∨ωi,q)；

03 for 1≤i≤[q-1]:

04 gtk1,i←∑MMTokenGen(Kg,ω1,i)；

05 dtk1,i←∑DXTokenGen(Kd,ω1,i)；

06 fori+1≤j≤#Δ1:

Itk1,i,j←∑MMTokenGen(Kω1,i,ω1,j)；

07 tk1,i=(dtk1,i,gtk1,i,Itk1,i,i+1,…,Itk1,i,#Δ1)；

08 gtk1,q←∑MMTokenGen(K1,q,ω1,q)；

09 tk1=(tk1,1,…,tk1,q-1,gtk1,q)；

10 for 2≤i≤landj∈[q]:

11 for 1≤s≤q:

Itks,i,j←∑MMTokenGen(Kω1,s,ωi,j)；

12 Itki,j=(Itk1,i,j,…,Itkq,i,j)；

13 tki=(Itki,1,…,Itki,l)；

14 output tk=(tk1,…,tkl).

2.3 搜索算法

搜索算法Search(tk,IE):服务器执行该算法.解析数据拥有者端发送的搜索令牌tk，在安全索引IE中搜索存储于服务器端的加密文件的索引信息.具体算法执行步骤如下：

1) 解析IE得到单关键字安全索引GMME和关键字交集安全索引字典DE.

2) 解析令牌tk，得到每一个析取范式Δi对应的索搜令牌tki.

3) 根据令牌tk1搜索获得关键字析取范式Δ1对应的文件标签集合R1作为第一轮搜索结果，执行如下操作：

①从ω1,1到ω1,q-1在GMME中搜索并分层按块提取ω1,i的文件标识符集合T1,i，依次减去从DE[ω1,i]对应的IMME搜索得到的ω1,i和ω1,i+1到ω1,q的交集T′.

②从GMME搜索并分层按块提取ω1,q的文件标识符集合T1,q.

③计算T1,1到T1,q的并集，得到Δ1的搜索结果R1=∪i∈|q|T1,i.

4) 从Δ2到Δl，对每一个Δi计算并保留上一轮搜索结果集合Ri-1与Δi中关键字ωi,j和Δ1中关键字ωi,s的关键字标识符交集再计算交集.执行如下操作：

①搜索并分层按块提取Δi中关键字ωi,j和Δl中关键字ωi,s的关键字标识符交集.

②计算并保留Ri-1与Δi中关键字ωi,j和Δl中关键字ωi,s的关键字标识符交集的交集.

5) 最后一轮搜索结果集合Rl即为最终的搜索结果.输出最终搜索结果R.

搜索算法伪代码:

01 convertIEto (GMME,DE)；

02 convert tk to (tk1,…,tkl)；

03 Search fromIEwithΔ1′s token tk1：

04 convert tk1as tk=(tk1,1,…,tk1,q-1,gtk1,q)；

05 for 1≤i≤[q-1]:

06 convert tk1,ias (dtk1,i,gtk1,i,Itk1,i+1,…,Itk1,q)；

07 Btag←∑MMSearch(GMME,gtk1,i)；

08T1,i←Blockget(Btag)；

09 IMME←∑DXSearch(DE,dtk1,i)；

10 fori+1≤j≤q:

11 Btag←∑MMSearch(IMME,Itk1,i)；

12T′←Blockget(Btag)；

13T1,i=T1,iT′;

14 Btag←(∑MMSearch(GMME,gtk1,q))；

15T1,q←Blockget(Btag)；

16R1=∪i∈|q|T1,i；

17 for 2≤i≤l:

18 create an empty setRi；

19 convert tkias (Itki,1,…,Itki,q)；

20 for allj∈[q]:

21 IMME←∑DXSearch(DE,dtk1,j)；

22 convert Itki,jto (Itk1,i,j,…,Itkq,i,j)；

23 for 1≤s≤q:

24 Btag←∑MMSearch(IMME,Itks,i,j)；

25R′←Blockget(Btag)；

26Ri=Ri∪(Ri-1∩R′)；

27 outputRl.

3 原型系统设计与实现

基于BSSEVD方案，大型数据集下支持布尔搜索的可搜索加密原型系统由文件预处理模块、初始化模块和搜索模块所组成.按照最终实现的系统功能，具体可分为8个子模块.系统功能模块结构如图2所示.

1) 文件预处理模块包括中文文件分词模块、倒排索引生成模块.

中文文件分词模块：运行于客户端，实现对中文文件关键字的提取.

倒排索引生成模块：运行于客户端，根据关键字集合、文件集合，生成倒排索引.

2) 初始化模块包括文件加密模块、安全索引生成模块、安全数据上传模块.

文件加密模块：运行于客户端，使用对称加密算法对上传云服务器的文件加密.

安全索引生成模块：运行于客户端，处理倒排索引，生成上传云服务器的安全索引和用于令牌生成的密钥.

安全数据上传模块：同时运行于客户和服务器两端，上传加密文件和安全索引，并存储于云服务器.

3) 关键字搜索模块包括搜索令牌生成模块、搜索模块和文件下载与解密模块.

搜索令牌生成模块：运行于客户端，解析用户输入的布尔搜索表达式，并生成对应的搜索令牌，将令牌上传至服务器端，进行搜索操作.

搜索模块：运行于服务器端，接收客户端上传的搜索令牌，利用令牌来进行多关键字的布尔搜索.

文件下载与解密模块：同时运行于客户端和服务器两端，将搜索结果返回客户端，根据用户选择下载加密文件，并解密.

本原型采用的系统开发语言为Java，版本号1.7.0_75.在本系统的实现过程中，使用开源Java函数库Bouncy Castle提供的算法实现加解密；使用开源的跨平台的Apache POI提供API实现对Microsoft Office格式档案读写；使用Apache软件基金会开放源代码的全文检索引擎工具包Lucene实现文件分词功能；使用Google Guava Collections 设计实现安全索引数据结构.

4 系统测试与性能分析

本原型系统在由2台实体机构建的实验环境中进行性能测试，实体机硬件配置：Intel(R) Core(TM) i5 CPU 9400 @2.9 Hz处理器，16 GB内存；实体机软件环境：Windows 10 64位操作系统.测试数据包含中文数据和英文数据.中文数据采用搜狗实验室(SougouLabs)提供的新闻数据，英文数据采用Enron公开邮件数据.

通过实验，测试原型系统对不同大小的安全索引(反映不同规模数据集)进行同一布尔搜索表达式的搜索时间，找出搜索时间与安全索引规模之间的关系，分析本方案中新的安全索引存储结构带来的搜索性能上的影响.实验中，分别在100 KB到600 KB六个不同大小安全索引上对同一搜索布尔表达式进行查询.

实验结果如图3所示，当安全索引增大时，搜索时间也相应变长.但应当注意到，当安全索引大小超过200 KB之后，本方案的搜索时间开始呈亚线性增长.这正是使用分层按块存储数据结构优化传统SSE方案的安全索引结构带来的积极影响.本方案在安全索引尺寸较小时没有优势甚至搜索性能会略差于传统SSE方案，但当安全索引规模超过某个阈值之后，本方案表现出其优势，安全索引尺寸越大优势越明显.显然，本方案更适用于大规模数据集的可搜索加密.

5 结 语

本文在传统可搜索加密方案基础上，通过应用三层间接寻址块状存储安全索引结构优化加密倒排索引；通过增加关键字交集加密倒排索引的方法解决多关键字布尔搜索带来的泄露问题，提出一种满足动态自适应安全的大型数据集下支持布尔搜索的可搜索加密方案BSSEVD，并设计实现其原型系统.在满足动态自适应安全的前提下，实现多关键字布尔搜索，并实现在大型数据集下亚线性搜索效率.