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

林濤 蔡睿琪 邱緒堯 廖文喆

摘 要： 云與移動設備的融合使得用戶能夠更加方便快捷地訪問、檢索文件，但是由于移動設備自身資源的局限性，如何縮短檢索時間并得到更加準確的目標文件，以避免無謂的資源消耗已經成為研究熱點。因此，提出一種高效的基于移動云的可搜索加密方案，該方案結合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.