云环境下可有效搜索的加密系统的设计与实现

张刚，郑志锐，潘建业，周德华

（暨南大学信息科学技术学院计算机科学系，广州　510000）

云环境下可有效搜索的加密系统的设计与实现

张刚，郑志锐，潘建业，周德华

（暨南大学信息科学技术学院计算机科学系，广州510000）

0　引言

当今，社会信息化和网络化的发展导致数据爆炸式增长。科学计算、医疗卫生、金融、零售业各行业有大量数据产生，个人产生和需要保存的信息也越来越多，所以很多机构和个人选择将数据存储在不属于自己的服务器上，这样一来，当用户对自己的数据进行检索时，可能会被服务器所有者监视，通过搜索的关键字获取用户个人信息，对用户的信息安全造成威胁。对所有文档进行加密且在需要时下载是一种可行的方法，但是随着数据量增加，下载和解密文档的成本也不断上升。因此需要一种高效的密文检索方案。

许多文献提出了各种提高密文搜索效率和安全性的方案。文献［2］提出了一种亚线性的密文检索方法。它基于在实际过程中搜索的关键词数只占总关键词的小部分的事实，在每次搜索时检测关键词是否曾经被搜索过，如果没有被搜索过，就取得对应索引返回给用户，并将该关键词和索引存入搜索历史中；如果曾被搜索过，就从搜索历史中直接取得对应索引返回。文献［3］提出了两个对称可搜索加密方案。其搜索原理与本文方案相似，但第一个方案使用了静态历史记录，第二个方案使用了动态历史记录。文献［4］介绍了可加密搜索各种方案各自的特点和它们之间的联系。文献［5］提出了在大量的数据中进行分布式搜索的方案，并将授权机制整合到其中。文献［6］提出了实现亚线性搜索时间和抗自适应选择明文攻击的方案。

本文实现了一种可高度扩展的密文检索系统，使服务器可以用已加密的关键字进行查找，返回符合要求的文件索引给用户，但服务器并不知道用户搜索的内容。用户也无须下载所有的加密文档，根据返回的索引解密下载即可。本文还详细介绍搜索内容仅有一个关键字时的程序实现方法，并通过控制变量反复试验，总结出保证加密和搜索效率的参数选取原则。

1　加密搜索方案原理

1.1基本原理

用户提交的关键字经过加密转换后，由服务器在已有的关键字与文档索引的对应关系中进行匹配，然后将成功匹配的文档索引返回给用户。系统总体架构如图1所示。

图1　总体架构图

1.2方案描述

本节详细阐述了从建立加密索引数组到搜索时各方交互的过程，并重点对过程中的TSet的实现方法进行了描述［1］。

（1）整体方案描述

图2　处理过程与搜索过程示意图

注意：上图数字标号表示发生顺序，相同标号的活动发生先后不论。

方案中所用算法的术语描述如下：

DB：包含所有文件的索引和对应的关键字的集合，数据结构采用字典的形式；

W：包含所有文档的关键字的集合，数据结构采用集合的形式；

w：关键字；

T：包含所有关键字和对应的文档索引的集合，其中文档索引已加密，数据结构采用字典的形式。用于进一步操作得到TSet，得到TSet后T不予保留。

TSet：由T进一步处理得到，发送给Web服务器持有。结构为二维，每个元素是一个结构体，其中包含label和value。label包含识别关键字的信息，value包含索引信息。一个TSet实例包含了三个函数，分别是TSetSetup（T），TSetGetTag（Kt，w），TSetRetrieve（TSet，stag）：TSetSetup（）的作用是建立TSet，TSetGetTag（）的作用生成包含关键字信息的随机数stag，TSetRetrieve（）的作用是得到关键字对应的所有文档索引的信息。

EDB：由TSet赋值得到，可理解为就是TSet。

F：伪随机函数，产生伪随机数。

本方案的交互对象有三个：客户端，Web服务器和云服务器。客户端持有用于加密关键字的秘钥Kt和解密索引的秘钥Ks；Web服务器持有TSet，简单地说就是文件索引的加密版本；云服务器持有所有文档的加密版本。

●云服务器的处理：

1.选择用于伪随机函数F的公钥Ks，DB是所有文档和文档索引标识符的集合。

2.初始化T为空数组，其中的信息是可以通过W中的关键字索引得到的。也就是说T［w］中包含了以w为关键字的所有文档标识符。

3.对W中的所有w按照下面步骤建立T［w］.

①初始化t为空队列，计算由函数F（Ks，w）计算得到密钥Ke；

②对所有含有w关键字的标识符ind，由Ke，ind加密得到e，把e加入t，这样就可以完成t的建立，也就是T［w］的建立；

4.t赋给T［w］。

5.以T为参数，由TSetSetup函数得到TSet和KT。

6.综上可得到Ks和KT以及加密后的DB（EDB），也就是TSet。

●搜索协议

1.客户端从云服务器分配得到密钥Ks和KT，输入关键字w进行查询。客户端以KT和w为参数，用TSetGetTag计算得到stag，把stag发送给Web服务器。完成了对查询内容的隐藏，服务器无法获取用户搜索的内容。

2.Web服务器从云服务器获得EDB，即TSet，以TSet和客户端发送的stag为参数，由TSetRetrieve函数返回包含对应索引加密信息的t，把t发送给客户端。

3.客户端接收t。由随机函数F计算出Ke，对t中每个e，用Ke和e，解密得到ind。

到此过程结束。

（2）TSet实例描述

一个TSet实例包含三个函数，TSetSetup（），TSet-GetTag（）和TSetRetrieve（）。

分别交由云服务器，客户端，Web服务器执行。

为了清晰地阐述TSet实例，首先对算法用到的定义和表示做一些说明。

F'（）：以Kt和w作为参数，计算出包含关键字信息的stag。

F（）：以stag和位置标志i作为参数，结果作为H（）的参数。

b：与j共同决定信息在TSet中的位置

j：与b共同决定信息在TSet中的位置

L：用于验证TSet中是否存有某索引的信息。

K：与β和si连接起来的串进行异或运算。包含了索引信息si。

H（）：哈希函数，计算出包含关键字和索引位置信息的串（b，L，K），b，L，K按照一定规则划分该串。

TSet：二维数组，大小为B*S。它要比所有关键字下的所有文档数大得多才能有效生成。放入信息时要尽量避免位置发生碰撞。每个元素类型都是record，record包含label和value两个变量，用于存储文档索引信息，由w，Kt，b和索引在t队列中的位置i共同决定索引信息在TSet中的位置。同关键字下的不同索引未必都在TSet［b］中。对于两个不同的索引，一旦发生碰撞，即计算出相同的位置，则选取新的Kt，重新执行TSetSetup（）。

record：一种数据类型，有label和value两个变量。label等于L，value等于K与β和si连接起来的串进行异或运算的结果。

Free：用于检测索引计算出来的位置是否发生碰撞。

B、S：分别表示TSet和Free的行数和列数，设置没有严格限制。B、S要足够大才能降低碰撞的概率。频繁的碰撞会导致TSet生成时间过长。

以下描述函数TSetSetup（），TSetGetTag（）和TSetRetrieve（）的实现过程。

●TSetSetup（T）

1.初始化二维数组TSet，大小为B行，S列，每个元素的类型为record。

2.初始化二维数组Free，大小为B行，每行的内容都是｛1，…，S｝，即大小也是B*S。1…S都是整数。

3.选择一个随机值Kt作为伪随机函数F'的参数。

4.对W中的浏览所有关键字w进行如下操作：

（1）计算stag=F'（Kt，w），令t=T［w］.

（2）对于i=1，…，|t|，令si等于t中的第i个串，再进行下面的操作：

①由H（F（stag，i））计算得到b，L，K

②若Free［b］为空，则选用新的Kt，重新执行TSet-Setup（T）

③在Free［b］中随机选取一个数j，把j移除

④如果i＜|t|，令β=1，如果i=|t|，令β=0

⑤令TSet［b，j］.label=L，令TSet［b，j］.value=（β|si）⊕K

5.输出TSet和Kt。

●TSetGetTag（Kt，w）

计算F'（Kt，w），得到stag。

●TSetRetrieve（TSet，stag）

1.初始化t为空数组，令β=1，i置为1

2.当β为1时重复以下循环：

（1）由H（F（stag，i））计算得到b，L，K，令B为TSet ［b］

（2）在1，……，S中查找j，满足B［j］.label=L

（3）令v=B［j］.value⊕K，令β等于v的第一位，s等于v除第一位的剩余部分

（4）将s加入t，i加1

3.输出t

2　具体实现

2.1云服务器的主要函数及实现

以下是云服务器的主要函数。

EDBSetup（DB）：产生密匙key（Ks，Kt），并对数据库DB的所有关键词W及索引ind进行加密，最终得到EDB（即TSet）。入口参数：DB；出口参数：key（Ks，Kt）和EDB。此过程只需执行一次。

TSetSetup（T）：将 EDBSetup（DB）过程中对 W 及ind加密后产生的T整合为对应的01串，存储在TSet中，用于搜索部分的查找匹配。其中也生成了随机密匙Kt。入口参数：T；出口参数：TSet和Kt。此过程只需执行一次。

F（Ks，w）：伪随机函数，以Ks和w为参数生成Ke。入口参数：Ks和w；出口参数：一个随机字符串e。

_F（Kt，w）：伪随机函数，以Kt和w为参数生成stag。入口参数：Kt和w；出口参数：一个随机字符串。encrypt（Ke，ind）：索引加密函数，采用AES加密算法，用Ke加密ind。入口参数：Ke和ind；出口参数：一个加密的字符串。

H（stag，i）：哈希函数，将F（stag，i）产生的随机字符串经哈希函数处理，产生一个01串，并按一定的位数映射到（b，L，K）上。入口参数：stag和i；出口参数：（b，L，K）。

db_server（）：实现云服务器与WEB服务器的通信。从而将EDB（即TSet）发送给WEB服务器。

db_client（）：实现云服务器与客户端的通信。从而将key（Ks，Kt）客户端，或者将客户端通过索引找到的文件信息发送给客户端。

Downfiles（ind_list）：当客户端得到索引的列表后，云服务器为其提供下载文件服务。入口参数：ind_list；出口参数：files。

关键部分的实现：

2.2Web服务器的主要函数及实现

以下是Web服务器的主要函数及实现。

server_db（）：实现Web服务器与云服务器的通信。从而从云服务器获得EDB（即TSet）。

server_client（）：实现WEB服务器与客户端的通信。从而接收客户端发送的用搜索关键字w加工后隐藏了信息的stag以进行搜索，并返回给客户端搜索到的t（隐含了索引ind的信息）。

TSetRetrieve（TSet，stag）：从TSet中搜索到与stag相关的隐藏了文件索引的列表 t。入口参数：Tset和stag；出口参数：t

关键部分的实现：

2.3客户端的主要函数及实现

以下是客户端的主要函数。

client_db（）：实现客户端与云服务器的通信。从而从云服务器获取密匙key（Ks，Kt），或者用从Web服务器搜索到的索引来向云服务器的提取相关的文件信息。

client_server（）：实现客户端与Web服务器的通信。从而将其搜索关键字w加工后隐藏了信息的stag发送给Web服务器以进行搜索，并接收从Web服务器搜索到的t（隐含索引ind的信息）。

downfiles（ind_list）：当客户端得到索引的列表后，向数据库提交索引获取相应文件。入口参数：ind_list；出口参数：files。

decrypt（Ke，e）：索引解密函数。用Ke从e中解密出需要的索引ind。入口参数：Ke和e；出口参数：ind。TSetGetTag（Kt，w）：加工w得到隐藏了信息的stag。入口参数：Kt和w；出口参数：stag

F（Ks，w）：伪随机函数，以Ks和w为参数生成Ke。入口参数：Ks；出口参数：一个随机字符串。

关键部分的实现：

3　性能测试

影响本方案索引数组建立时间和搜索时间的关键因素有文件索引数目N和两个关键参数B、S。

下面是针对这些因素进行的性能测试。

测试环境配置为Win10 64位操作系统，1.35GHz处理器，4GB内存。

3.1EDB建立时间测试

采用文件数目间接控制文件索引数目N，设定B= 600，S=600，保证EDB的建立重启次数为0，测量EDB建立时间。

表1　EDB建立时间测试数据

图3　EDB建立时间折线图

从图3可看出，EDB建立时间与文件索引数N呈近线性关系。大致符合本文根据算法所作出的推测。

3.2搜索时间测试

搜索时间的测试分别以B和S为变量。为了减少测量误差和控制变量，本测试固定文件数为8000，对应文件索引数N=180956。每次测试搜索三个关键词"word"，"by"，"that"，观察它们在不同的B、S下的搜索时间。

表2　以S为变量的搜索时间数据

图4　以S为变量的搜索时间折线图

从图4可看出，在保证碰撞概率足够低的情况下，搜索时间与S呈正相关性。

从图5可看出，在保证碰撞概率足够低的情况下，搜索时间与B的值没有明显相关性。

本方案的搜索过程是根据加密后的关键字计算出哈希值，并在大小为S的索引队列中进行顺序查找，因此搜索时间与S正相关，与B无关的结果符合预期。

本方案建立EDB时发生碰撞的概率［1］为：

可根据该公式对碰撞概率进行控制，并尽量减少S的值，以达到更高的搜索效率。

图5　以B变量的搜索时间折线图

4　结语

本方案实现了静态的单关键字密文检索，详细介绍了TSet的建立过程和搜索过程中服务器和客户端的交互方式，并通过测试估计方案的时间效率与文件索引数和相关参数之间的关系。多关键字的检索可以通过在单关键字的基础上做布尔查询实现，具体算法在文献［1］中有所提及。

本方案可以应用在云存储环境下对用户数据的保护上，可以做到保护用户的外包数据的安全和查询隐私而不影响数据检索功能，除了个人，在政府、企业等持有大量敏感数据的场合，有效搜索的加密系统都将发挥它的优势。

［1］David Cash，Stanislaw Jarecki，Charanjit Jutla，Hugo Krawczyk，et al.Highly-Scalable Searchable Symmetric Encryption with Support for Bollean Queries［EB/OL］.http：//eprint.iacr.org/2013/169.pdf，2015-12-20.

［2］Florian Hahn，Florian Kerschbaum.Searchable Encryption with Secure and Efficient Updates［EB/OL］.http：//www.fkerschbaum.org/ ccs14b.pdf，2015-12-20.

［3］Curtmola R，Garay J，Kamara S，et al.Searchable Symmetric Encryption：Improved Definitions and Efficient Construction［C］.Proc of the 13th ACM Conference on Computer and Communications Security.New Yokr：ACM Press，2006：79-88.

［4］Christoph Bosch，Pieter Hartel，Willem Jonker，Andreas Peter.A Survey of Provably Secure Searchable Encryption［EB/OL］.http：//dl .acm.org/citation.cfm？id=2636328，2015-12-20.

［5］Mehmet Kuzu，Mohammad Saiful Islam，Murat Kantarcioglu.Distributed Search over Encrypted Big Data［EB/OL］.http：//dl.acm.org/citation.cfm？id=2699116，2015-12-20.

［6］Seny Kamara，Charalampos Papamanthou，Tom Roeder.Dynamic Searchable Symmetric Encryption［EB/OL］.http：//eprint.iacr.org/2012/ 530.pdf，2015-12-20.

［7］Alexandra Boldyreva，Nathan Chenette.Efficient Fuzzy Search on Encrypted Data［EB/OL］.http：//link.springer.com/chapter/10.1007%2F978-3-662-46706-0_31，2015-12-20.

表3　以B变量的搜索时间数据

［8］David Cash，Joseph Jaeger，Stanislaw Jarecki，Charanjit Jutla，Hugo Krawczyk，Marcel-Catalin Rosu，and Michael Steiner.Dynamic Searchable Encryption in Very-Large Databases Data Structures and Implementation［EB/OL］.http：//www.internetsociety.org/sites/default/files/07_4_1.pdf，2015-12-20.

［9］Christopher D.Manning，Prabhakar Raghavan，Hinrich Schutze.信息检索导论［M］.北京：人民邮电出版社，2010.

［10］Bruce Schneier.应用密码学：协议、算法与C源程序［M］.北京：机械工业出版社，2014.

［11］Nam-Su Jho，Ku-Young Chang，Dowon Hong，et al.Symmetric Searchable Encryption with Efficient Range Query Using Multi-Layered Linked Chains［EB/OL］.http：//link.springer.com/article/10.1007/s11227-015-1497-6，2015-12-19.

［12］Tsu-Yang Wu，Tung-Tso Tsai，Yuh-Min Tseng.Efficient Searchable ID-Based Encryption with a Designated Server［EB/OL］.http：// link.springer.com/article/10.1007/s12243-013-0398-z/fulltext.html#copyrightInformation，2015-12-19.

［13］Changhui Hu，Lidong Han.Efficient Wildcard Search Over Encrypted Data［EB/OL］.http：//link.springer.com/article/10.1007/s10207-015-0302-0/fulltext.html，2015-12-18.

［14］Mohammad Ali Hadavi，Rasool Jalili，Ernesto Damiani，Stelvio Cimato.Security and Searchability in Secret Sharing-Based Data Outsourcing［EB/OL］.http：//link.springer.com/article/10.1007/s10207-015-0277-x/fulltext.html，2015-12-18.

［15］Li Xu，Chi-Yao Weng，Lun-Pin Yuan，Mu-En Wu，Raylin Tso，Hung-Min Sun.A Shareable Keyword Search Over Encrypted Data in Cloud Computing［EB/OL］.http：//link.springer.com/article/10.1007/s11227-015-1515-8/fulltext.html，2015-12-19.

［16］Ke Tian，Weiming Zhang，Ke Li，Junming Wu，Nenghai Yu.A Novel Fuzzy Keyword Retrieval Scheme Over Encrypted Cloud Data ［EB/OL］.http：//link.springer.com/article/10.1007/s11859-013-0947-3，2015-12-15.

［17］Chih-hung Wang，Tai-yuan Tu.Keyword Search Encryption Scheme Resitant Against Keyword-Guessing Attack by the Untrusted Server［J］.Journal of Shanghai Jiaotong University（Science）.2014/8，19（4）：440-442.

［18］Md Iftekhar Salam，Wei-Chuen Yau，Ji-Jian Chin，et al.Implementation of Searchable Symmetric Encryption for Privacy-Preserving Keyword Search on Cloud Storage［EB/OL］.http：//link.springer.com/article/10.1186/s13673-015-0039-9，2015-12-17.

［19］Clemens Heidinger，Klemens Bohm，Erik Buchmann，et al.Efficient and Secure Exact-Match Queries in Outsourced Databases［J］. World Wide Web，2015/5，18（3）：567-605.

Ciphertext Retrieval；Information Security；Encryption；Cloud Environment

Design and Implement of Effectively Searchable Encryption System in Cloud Environment

ZHANG Gang，ZHENG Zhi-rui，PAN Jian-ye，ZHOU De-hua
（College of Information Science and Technology，Jinan University，Guangzhou 510000）

1007-1423（2016）24-0054-07DOI：10.3969/j.issn.1007-1423.2016.24.014

张刚（1995－），男，安徽六安人，本科，研究方向为信息安全、密码学

郑志锐（1994－），男，广东汕头人，本科，学生，研究领域为信息安全、密码学

潘建业（1994－），男，本科，学生，研究方向为信息安全、密码学

周德华（1977-），男，博士，副教授，研究方向为密码学与信息安全

2016-05-19

2016-08-10

为了保护搜索过程中用户的隐私安全，提出一种云环境下可有效搜索的加密系统，系统采用基于布尔查询的可高度扩展的对称搜索加密算法，可以在不解密云端文件的情况下对文件进行检索，并返回正确结果，且几乎不向云端透露关键字信息。对该加密系统的性能进行测试，提出可供参考的参数选取原则。

密文检索；信息安全；加密；云环境

国家自然科学基金（No.61572235）、广东省自然科学基金（No.2014A030310172）、中央高校基本科研业务费专项资金（No.21615445）

To protect the user's privacy security in the process of searching，proposes a type of encryption system which can be searched effectively under a cloud environment，and realizes a version of single keyword.The system adopts highly-scalable searchable symmetric encryption algorithm based on Boolean queries.And it is competent for retrieving without decrypting the files，then returns correct answers，which has never divulge the keyword.Shows the testing process of the performance of encryption system，and provides suggestions of choosing appropriate parameters which can be referred.