面向移动云的高效可搜索加密方案

林涛 蔡睿琪 邱绪尧 廖文喆

摘 要： 云与移动设备的融合使得用户能够更加方便快捷地访问、检索文件，但是由于移动设备自身资源的局限性，如何缩短检索时间并得到更加准确的目标文件，以避免无谓的资源消耗已经成为研究热点。因此，提出一种高效的基于移动云的可搜索加密方案，该方案结合K邻近算法，设计了初始陷门匹配表，实现了多关键字的布尔查询，提高了查询精度，缩短了检索时间。

关键词： 移动云； 可搜索加密方案； K邻近算法； 检索时间； 目标文件； 资源消耗

中图分类号： TN915.08?34； TP309.7 文献标识码： A 文章编号： 1004?373X（2018）22?0170?04

Abstract： The integration of the cloud and mobile device enables users to access and retrieve files more quickly and conveniently， but how to shorten retrieval time and get more accurate target files to avoid unnecessary resource consumption has become a research focus due to the self?limitations of mobile device resources. Therefore， a high?efficient searchable encryption scheme based on the mobile cloud is proposed. In the scheme， the initial trapdoor matching table （TMT） is designed by combining with the K?nearest neighbor algorithm， which can realize the Boolean query based on multiple keywords， improve query precision， and shorten retrieval time.

Keywords： mobile cloud； searchable encryption scheme； K?nearest neighbor algorithm； retrieval time； target file； resource consumption

0 引 言

通过外包模式将用户从繁重的数据、密钥的管理任务中解放出来，并且将大量的计算、存储任务分配给云端，避免受到本地资源的限制[1]。然而，外包意味着数据属主将数据的管理交给云端，从而造成新的安全问题[2]。为了保证数据的安全性和隐私性，外包文件和索引在上传到云端之前，需要进行加密操作。云计算的部署方式决定了获取数据资源必须完全依赖于网络服务[3]。随着人们对移动终端的检索服务需求的增大，通信带宽的不断增长和数据内容的日益丰富，数据安全管理和快速检索的难度也随之增大[4]。

传统的云端数据检索系统需要两次用户与数据属主的网络延迟，在用户和云端需要一次网络延迟，三次网络延迟会造成一定的检索延迟和多余的网络负载，这会严重消耗移动终端的资源[5]。本文关注移动终端检索数据时间消耗长、资源消耗大的问题，提出了一种高效的面向移动云的可搜索加密方案（Efficient encrypted Data search system，EnDas）。本方案提出构建移动终端的陷门匹配表，并结合K邻近算法，支持多关键字的布尔查询，减少了网络延迟次数，有效地缩短了检索时间和降低了通信带宽消耗。

1 传统的可搜索加密系统

如图1所示，传统的可搜索加密系统由三部分参与者组成：数据属主、云数据中心和用户。数据属主具有一系列文件和索引，并将其加密后发送至云数据中心以供用户进行检索服务[6]；云数据中心作为一个商业组织提供强大的存储、计算、带宽等资源[7]；用户提交检索关键字来搜索目标文件，本文假设用户检索所用的工具为智能移动终端。当用户需要检索文件时，首先将需要检索的关键字发给数据属主；之后数据属主生成加密的关键字，即陷门，并将陷门发送给用户，用户再将陷门发送到云端；在云端接收陷门之后，基于加密的索引和陷门选取特定的文件；最后，用户利用解密密钥获取文件明文[8?10]。

式中：[Ttrr]為总时间延迟；[Tnet]为一次网络延迟的时间延迟；[Tgen]为陷门生成的时间延迟。根据测量结果，陷门生成（图1的第5～第8步）时间延迟大约占总时间延迟的59.9%。另一方面，检索过程通常采用串行检索排名（Ranked Serial Search，RSS）算法，并不支持布尔查询，检索结果准确性不足会造成严重的资源消耗。

2 EnDas方案的设计

本节介绍了EnDas方案的设计，通过比较EnDas方案和传统的可搜索加密方案，EnDas减少了网络延迟的次数，提出并设计了陷门匹配表（Trapdoor Matching Table，TMT），结合K邻近算法，实现了更加快速的文件检索，并支持基于关键字的布尔查询。

2.1 EnDas方案的架构

EnDas方案的整体架构如图2所示，本方案优化了陷门生成过程以及检索算法，使得其在有效减少了延迟时间的同时，支持多关键字的布尔查询。

1） 初始化

在本方案中，数据属主首先设置包含m个关键字的集合W，之后随机生成密钥[K=（S，M1，M2）]，S为一个m+1维的二进制向量，[M1]，[M2]是两个（m+1）·（m+1）的可逆矩阵，其中，m即为关键字的个数。数据属主将（K，sk）发送给通过认证的用户，sk即为加密文件的对称密钥。

2） 建立索引

式中，random为随机值，文件的索引[Ij]设置为[Ij=（paM1，pbM2）]。最后，数据属主将加密文件和对应的索引发送到云端。

3） 陷门匹配表

EnDas预先在移动终端存储一个提前计算的陷门匹配表（Trapdoor March Table，TMT），里面存储常用单词对应的初始陷门Trap。当用户提交一个新的检索需求时，仅需从TMT中获取对应的陷门而不需要从数据属主处获得，这样减少了一次网络延迟。

4） 生成陷门

2.2 EnDas方案的优势

3 实验分析

为了进一步分析检索过程，本文测量评估了传统方案与EnDas方案的检索时间，如表2所示，其中，U代表用户，P代表数据属主，C代表云端数据中心。

由表2可得，在传统方案中会造成两次网络延迟，那么生成、传输一个关键字陷门需要消耗大约251.78 ms，3个关键字需要消耗大约593.71 ms，而EnDas方案中，一个关键字的陷门需要消耗140.39 ms，3个关键字的陷门需要消耗265.39 ms。而且，由于EnDas方案结合了K邻近算法，支持布尔查询，使得检索结果更加准确，进而返回文件消耗的时间更短和资源更少。

4 结 语

本文通过研究可搜索加密过程对时间、资源消耗因素的分析，结合K邻近算法，提出了陷门匹配表，在减少检索时间的前提下，使得EnDas方案支持布尔查询，提高了查询精度，减少了无谓的资源消耗。实验结果表明，此方案在缩短检索时间、精确检索结果上相比传统方案有了很大的提高。

参考文献

[1] LI Hongwei， LIU Dongxiao， DAI Yuanshun， et al. Engineering searchable encryption of mobile cloud networks： when QoE meets QoP [J]. IEEE wireless communications， 2015， 22（4）： 74?80.

[2] 项菲，刘川意，方滨兴，等.云计算环境下密文搜索算法的研究[J].通信学报，2013，34（7）：143?153.

XIANG Fei， LIU Chuanyi， FANG Binxing， et al. Research on ciphertext search for the cloud environment [J]. Journal on communications， 2013， 34（7）： 143?153.

[3] RIBEIRO L S， VIANA?FERREIRA C， OLIVEIRA J L， et al. XDS?I outsourcing proxy： ensuring confidentiality while preserving interoperability [J]. IEEE journal of biomedical and health informatics， 2014， 18（4）： 1404?1412.

[4] LIANG K， SUSILO W. Searchable attribute?based mechanism with efficient data sharing for secure cloud storage [J]. IEEE transactions on information forensics and security， 2017， 10（9）： 1981?1992.

[5] MA R， LI J， GUAN H， et al. EnDAS： efficient encrypted data search as a mobile cloud service [J]. IEEE transactions on emerging topics in computing， 2015， 3（3）： 372?383.

[6] 黄海平，杜建澎，戴华，等.一种基于云存储的多服务器多关键词可搜索加密方案[J].电子与信息学报，2017，39（2）：389?396.

HUANG Haiping， DU Jianpeng， DAI Hua， et al. Multi?sever Multi?keyword searchable encryption scheme based on cloud storage [J]. Journal of electronics & information technology， 2017， 39（2）： 389?396.

[7] CAO N， WANG C， LI M， et al. Privacy?preserving multi?keyword ranked search over encrypted cloud data [J]. IEEE transactions on parallel and distributed systems， 2013， 25（1）： 222?233.

[8] 郭锐.一种特定场景可搜索加密技术及其应用研究[D].成都：电子科技大学，2015.

GUO Rui. Research on searchable encryption technology and its application in a specific situation [D]. Chengdu： University of Electronic Science and Technology of China， 2015.

[9] 徐鹏，金海.可搜索加密的研究进展[J].网络与信息安全学报，2016，2（10）：8?16.

XU Peng， JIN Hai. Research on the searchable encryption [J]. Chinese journal of network and information security， 2016， 2（10）： 8?16.

[10] 李倩，岳风顺，王国军.安全云存储中高效的多关键词查找方案[J].计算机科学，2012，39（12）：158?161.

LI Qian， YUE Fengshun， WANG Guojun. Efficient multi?keyword search over secure cloud storage [J]. Computer science， 2012， 39（12）： 158?161.