張剛，鄭志銳，潘建業(yè)，周德華

（暨南大學信息科學技術(shù)學院計算機科學系，廣州　510000）

云環(huán)境下可有效搜索的加密系統(tǒng)的設(shè)計與實現(xiàn)

張剛，鄭志銳，潘建業(yè)，周德華

（暨南大學信息科學技術(shù)學院計算機科學系，廣州510000）

0　引言

當今，社會信息化和網(wǎng)絡化的發(fā)展導致數(shù)據(jù)爆炸式增長?？茖W計算、醫(yī)療衛(wèi)生、金融、零售業(yè)各行業(yè)有大量數(shù)據(jù)產(chǎn)生，個人產(chǎn)生和需要保存的信息也越來越多，所以很多機構(gòu)和個人選擇將數(shù)據(jù)存儲在不屬于自己的服務器上，這樣一來，當用戶對自己的數(shù)據(jù)進行檢索時，可能會被服務器所有者監(jiān)視，通過搜索的關(guān)鍵字獲取用戶個人信息，對用戶的信息安全造成威脅。對所有文檔進行加密且在需要時下載是一種可行的方法，但是隨著數(shù)據(jù)量增加，下載和解密文檔的成本也不斷上升。因此需要一種高效的密文檢索方案。

許多文獻提出了各種提高密文搜索效率和安全性的方案。文獻［2］提出了一種亞線性的密文檢索方法。它基于在實際過程中搜索的關(guān)鍵詞數(shù)只占總關(guān)鍵詞的小部分的事實，在每次搜索時檢測關(guān)鍵詞是否曾經(jīng)被搜索過，如果沒有被搜索過，就取得對應索引返回給用戶，并將該關(guān)鍵詞和索引存入搜索歷史中；如果曾被搜索過，就從搜索歷史中直接取得對應索引返回。文獻［3］提出了兩個對稱可搜索加密方案。其搜索原理與本文方案相似，但第一個方案使用了靜態(tài)歷史記錄，第二個方案使用了動態(tài)歷史記錄。文獻［4］介紹了可加密搜索各種方案各自的特點和它們之間的聯(lián)系。文獻［5］提出了在大量的數(shù)據(jù)中進行分布式搜索的方案，并將授權(quán)機制整合到其中。文獻［6］提出了實現(xiàn)亞線性搜索時間和抗自適應選擇明文攻擊的方案。

本文實現(xiàn)了一種可高度擴展的密文檢索系統(tǒng)，使服務器可以用已加密的關(guān)鍵字進行查找，返回符合要求的文件索引給用戶，但服務器并不知道用戶搜索的內(nèi)容。用戶也無須下載所有的加密文檔，根據(jù)返回的索引解密下載即可。本文還詳細介紹搜索內(nèi)容僅有一個關(guān)鍵字時的程序?qū)崿F(xiàn)方法，并通過控制變量反復試驗，總結(jié)出保證加密和搜索效率的參數(shù)選取原則。

1　加密搜索方案原理

1.1基本原理

用戶提交的關(guān)鍵字經(jīng)過加密轉(zhuǎn)換后，由服務器在已有的關(guān)鍵字與文檔索引的對應關(guān)系中進行匹配，然后將成功匹配的文檔索引返回給用戶。系統(tǒng)總體架構(gòu)如圖1所示。

圖1　總體架構(gòu)圖

1.2方案描述

本節(jié)詳細闡述了從建立加密索引數(shù)組到搜索時各方交互的過程，并重點對過程中的TSet的實現(xiàn)方法進行了描述［1］。

（1）整體方案描述

圖2　處理過程與搜索過程示意圖

注意：上圖數(shù)字標號表示發(fā)生順序，相同標號的活動發(fā)生先后不論。

方案中所用算法的術(shù)語描述如下：

DB：包含所有文件的索引和對應的關(guān)鍵字的集合，數(shù)據(jù)結(jié)構(gòu)采用字典的形式；

W：包含所有文檔的關(guān)鍵字的集合，數(shù)據(jù)結(jié)構(gòu)采用集合的形式；

w：關(guān)鍵字；

T：包含所有關(guān)鍵字和對應的文檔索引的集合，其中文檔索引已加密，數(shù)據(jù)結(jié)構(gòu)采用字典的形式。用于進一步操作得到TSet，得到TSet后T不予保留。

TSet：由T進一步處理得到，發(fā)送給Web服務器持有。結(jié)構(gòu)為二維，每個元素是一個結(jié)構(gòu)體，其中包含label和value。label包含識別關(guān)鍵字的信息，value包含索引信息。一個TSet實例包含了三個函數(shù)，分別是TSetSetup（T），TSetGetTag（Kt，w），TSetRetrieve（TSet，stag）：TSetSetup（）的作用是建立TSet，TSetGetTag（）的作用生成包含關(guān)鍵字信息的隨機數(shù)stag，TSetRetrieve（）的作用是得到關(guān)鍵字對應的所有文檔索引的信息。

EDB：由TSet賦值得到，可理解為就是TSet。

F：偽隨機函數(shù)，產(chǎn)生偽隨機數(shù)。

本方案的交互對象有三個：客戶端，Web服務器和云服務器?？蛻舳顺钟杏糜诩用荜P(guān)鍵字的秘鑰Kt和解密索引的秘鑰Ks；Web服務器持有TSet，簡單地說就是文件索引的加密版本；云服務器持有所有文檔的加密版本。

●云服務器的處理：

1.選擇用于偽隨機函數(shù)F的公鑰Ks，DB是所有文檔和文檔索引標識符的集合。

2.初始化T為空數(shù)組，其中的信息是可以通過W中的關(guān)鍵字索引得到的。也就是說T［w］中包含了以w為關(guān)鍵字的所有文檔標識符。

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

①初始化t為空隊列，計算由函數(shù)F（Ks，w）計算得到密鑰Ke；

②對所有含有w關(guān)鍵字的標識符ind，由Ke，ind加密得到e，把e加入t，這樣就可以完成t的建立，也就是T［w］的建立；

4.t賦給T［w］。

5.以T為參數(shù)，由TSetSetup函數(shù)得到TSet和KT。

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

●搜索協(xié)議

1.客戶端從云服務器分配得到密鑰Ks和KT，輸入關(guān)鍵字w進行查詢?？蛻舳艘訩T和w為參數(shù)，用TSetGetTag計算得到stag，把stag發(fā)送給Web服務器。完成了對查詢內(nèi)容的隱藏，服務器無法獲取用戶搜索的內(nèi)容。

2.Web服務器從云服務器獲得EDB，即TSet，以TSet和客戶端發(fā)送的stag為參數(shù)，由TSetRetrieve函數(shù)返回包含對應索引加密信息的t，把t發(fā)送給客戶端。

3.客戶端接收t。由隨機函數(shù)F計算出Ke，對t中每個e，用Ke和e，解密得到ind。

到此過程結(jié)束。

（2）TSet實例描述

一個TSet實例包含三個函數(shù)，TSetSetup（），TSet-GetTag（）和TSetRetrieve（）。

分別交由云服務器，客戶端，Web服務器執(zhí)行。

為了清晰地闡述TSet實例，首先對算法用到的定義和表示做一些說明。

F'（）：以Kt和w作為參數(shù)，計算出包含關(guān)鍵字信息的stag。

F（）：以stag和位置標志i作為參數(shù)，結(jié)果作為H（）的參數(shù)。

b：與j共同決定信息在TSet中的位置

j：與b共同決定信息在TSet中的位置

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

K：與β和si連接起來的串進行異或運算。包含了索引信息si。

H（）：哈希函數(shù)，計算出包含關(guān)鍵字和索引位置信息的串（b，L，K），b，L，K按照一定規(guī)則劃分該串。

TSet：二維數(shù)組，大小為B*S。它要比所有關(guān)鍵字下的所有文檔數(shù)大得多才能有效生成。放入信息時要盡量避免位置發(fā)生碰撞。每個元素類型都是record，record包含label和value兩個變量，用于存儲文檔索引信息，由w，Kt，b和索引在t隊列中的位置i共同決定索引信息在TSet中的位置。同關(guān)鍵字下的不同索引未必都在TSet［b］中。對于兩個不同的索引，一旦發(fā)生碰撞，即計算出相同的位置，則選取新的Kt，重新執(zhí)行TSetSetup（）。

record：一種數(shù)據(jù)類型，有l(wèi)abel和value兩個變量。label等于L，value等于K與β和si連接起來的串進行異或運算的結(jié)果。

Free：用于檢測索引計算出來的位置是否發(fā)生碰撞。

B、S：分別表示TSet和Free的行數(shù)和列數(shù)，設(shè)置沒有嚴格限制。B、S要足夠大才能降低碰撞的概率。頻繁的碰撞會導致TSet生成時間過長。

以下描述函數(shù)TSetSetup（），TSetGetTag（）和TSetRetrieve（）的實現(xiàn)過程。

●TSetSetup（T）

1.初始化二維數(shù)組TSet，大小為B行，S列，每個元素的類型為record。

2.初始化二維數(shù)組Free，大小為B行，每行的內(nèi)容都是｛1，…，S｝，即大小也是B*S。1…S都是整數(shù)。

3.選擇一個隨機值Kt作為偽隨機函數(shù)F'的參數(shù)。

4.對W中的瀏覽所有關(guān)鍵字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，重新執(zhí)行TSet-Setup（T）

③在Free［b］中隨機選取一個數(shù)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為空數(shù)組，令β=1，i置為1

2.當β為1時重復以下循環(huán)：

（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　具體實現(xiàn)

2.1云服務器的主要函數(shù)及實現(xiàn)

以下是云服務器的主要函數(shù)。

EDBSetup（DB）：產(chǎn)生密匙key（Ks，Kt），并對數(shù)據(jù)庫DB的所有關(guān)鍵詞W及索引ind進行加密，最終得到EDB（即TSet）。入口參數(shù)：DB；出口參數(shù)：key（Ks，Kt）和EDB。此過程只需執(zhí)行一次。

TSetSetup（T）：將 EDBSetup（DB）過程中對 W 及ind加密后產(chǎn)生的T整合為對應的01串，存儲在TSet中，用于搜索部分的查找匹配。其中也生成了隨機密匙Kt。入口參數(shù)：T；出口參數(shù)：TSet和Kt。此過程只需執(zhí)行一次。

F（Ks，w）：偽隨機函數(shù)，以Ks和w為參數(shù)生成Ke。入口參數(shù)：Ks和w；出口參數(shù)：一個隨機字符串e。

_F（Kt，w）：偽隨機函數(shù)，以Kt和w為參數(shù)生成stag。入口參數(shù)：Kt和w；出口參數(shù)：一個隨機字符串。encrypt（Ke，ind）：索引加密函數(shù)，采用AES加密算法，用Ke加密ind。入口參數(shù)：Ke和ind；出口參數(shù)：一個加密的字符串。

H（stag，i）：哈希函數(shù)，將F（stag，i）產(chǎn)生的隨機字符串經(jīng)哈希函數(shù)處理，產(chǎn)生一個01串，并按一定的位數(shù)映射到（b，L，K）上。入口參數(shù)：stag和i；出口參數(shù)：（b，L，K）。

db_server（）：實現(xiàn)云服務器與WEB服務器的通信。從而將EDB（即TSet）發(fā)送給WEB服務器。

db_client（）：實現(xiàn)云服務器與客戶端的通信。從而將key（Ks，Kt）客戶端，或者將客戶端通過索引找到的文件信息發(fā)送給客戶端。

Downfiles（ind_list）：當客戶端得到索引的列表后，云服務器為其提供下載文件服務。入口參數(shù)：ind_list；出口參數(shù)：files。

關(guān)鍵部分的實現(xiàn)：

2.2Web服務器的主要函數(shù)及實現(xiàn)

以下是Web服務器的主要函數(shù)及實現(xiàn)。

server_db（）：實現(xiàn)Web服務器與云服務器的通信。從而從云服務器獲得EDB（即TSet）。

server_client（）：實現(xiàn)WEB服務器與客戶端的通信。從而接收客戶端發(fā)送的用搜索關(guān)鍵字w加工后隱藏了信息的stag以進行搜索，并返回給客戶端搜索到的t（隱含了索引ind的信息）。

TSetRetrieve（TSet，stag）：從TSet中搜索到與stag相關(guān)的隱藏了文件索引的列表 t。入口參數(shù)：Tset和stag；出口參數(shù)：t

關(guān)鍵部分的實現(xiàn)：

2.3客戶端的主要函數(shù)及實現(xiàn)

以下是客戶端的主要函數(shù)。

client_db（）：實現(xiàn)客戶端與云服務器的通信。從而從云服務器獲取密匙key（Ks，Kt），或者用從Web服務器搜索到的索引來向云服務器的提取相關(guān)的文件信息。

client_server（）：實現(xiàn)客戶端與Web服務器的通信。從而將其搜索關(guān)鍵字w加工后隱藏了信息的stag發(fā)送給Web服務器以進行搜索，并接收從Web服務器搜索到的t（隱含索引ind的信息）。

downfiles（ind_list）：當客戶端得到索引的列表后，向數(shù)據(jù)庫提交索引獲取相應文件。入口參數(shù)：ind_list；出口參數(shù)：files。

decrypt（Ke，e）：索引解密函數(shù)。用Ke從e中解密出需要的索引ind。入口參數(shù)：Ke和e；出口參數(shù)：ind。TSetGetTag（Kt，w）：加工w得到隱藏了信息的stag。入口參數(shù)：Kt和w；出口參數(shù)：stag

F（Ks，w）：偽隨機函數(shù)，以Ks和w為參數(shù)生成Ke。入口參數(shù)：Ks；出口參數(shù)：一個隨機字符串。

關(guān)鍵部分的實現(xiàn)：

3　性能測試

影響本方案索引數(shù)組建立時間和搜索時間的關(guān)鍵因素有文件索引數(shù)目N和兩個關(guān)鍵參數(shù)B、S。

下面是針對這些因素進行的性能測試。

測試環(huán)境配置為Win10 64位操作系統(tǒng)，1.35GHz處理器，4GB內(nèi)存。

3.1EDB建立時間測試

采用文件數(shù)目間接控制文件索引數(shù)目N，設(shè)定B= 600，S=600，保證EDB的建立重啟次數(shù)為0，測量EDB建立時間。

表1　EDB建立時間測試數(shù)據(jù)

圖3　EDB建立時間折線圖

從圖3可看出，EDB建立時間與文件索引數(shù)N呈近線性關(guān)系。大致符合本文根據(jù)算法所作出的推測。

3.2搜索時間測試

搜索時間的測試分別以B和S為變量。為了減少測量誤差和控制變量，本測試固定文件數(shù)為8000，對應文件索引數(shù)N=180956。每次測試搜索三個關(guān)鍵詞"word"，"by"，"that"，觀察它們在不同的B、S下的搜索時間。

表2　以S為變量的搜索時間數(shù)據(jù)

圖4　以S為變量的搜索時間折線圖

從圖4可看出，在保證碰撞概率足夠低的情況下，搜索時間與S呈正相關(guān)性。

從圖5可看出，在保證碰撞概率足夠低的情況下，搜索時間與B的值沒有明顯相關(guān)性。

本方案的搜索過程是根據(jù)加密后的關(guān)鍵字計算出哈希值，并在大小為S的索引隊列中進行順序查找，因此搜索時間與S正相關(guān)，與B無關(guān)的結(jié)果符合預期。

本方案建立EDB時發(fā)生碰撞的概率［1］為：

可根據(jù)該公式對碰撞概率進行控制，并盡量減少S的值，以達到更高的搜索效率。

圖5　以B變量的搜索時間折線圖

4　結(jié)語

本方案實現(xiàn)了靜態(tài)的單關(guān)鍵字密文檢索，詳細介紹了TSet的建立過程和搜索過程中服務器和客戶端的交互方式，并通過測試估計方案的時間效率與文件索引數(shù)和相關(guān)參數(shù)之間的關(guān)系。多關(guān)鍵字的檢索可以通過在單關(guān)鍵字的基礎(chǔ)上做布爾查詢實現(xiàn)，具體算法在文獻［1］中有所提及。

本方案可以應用在云存儲環(huán)境下對用戶數(shù)據(jù)的保護上，可以做到保護用戶的外包數(shù)據(jù)的安全和查詢隱私而不影響數(shù)據(jù)檢索功能，除了個人，在政府、企業(yè)等持有大量敏感數(shù)據(jù)的場合，有效搜索的加密系統(tǒng)都將發(fā)揮它的優(yōu)勢。

［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，F(xiàn)lorian 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變量的搜索時間數(shù)據(jù)

［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.應用密碼學：協(xié)議、算法與C源程序［M］.北京：機械工業(yè)出版社，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－），男，廣東汕頭人，本科，學生，研究領(lǐng)域為信息安全、密碼學

潘建業(yè)（1994－），男，本科，學生，研究方向為信息安全、密碼學

周德華（1977-），男，博士，副教授，研究方向為密碼學與信息安全

2016-05-19

2016-08-10

為了保護搜索過程中用戶的隱私安全，提出一種云環(huán)境下可有效搜索的加密系統(tǒng)，系統(tǒng)采用基于布爾查詢的可高度擴展的對稱搜索加密算法，可以在不解密云端文件的情況下對文件進行檢索，并返回正確結(jié)果，且?guī)缀醪幌蛟贫送嘎蛾P(guān)鍵字信息。對該加密系統(tǒng)的性能進行測試，提出可供參考的參數(shù)選取原則。

密文檢索；信息安全；加密；云環(huán)境

國家自然科學基金（No.61572235）、廣東省自然科學基金（No.2014A030310172）、中央高?；究蒲袠I(yè)務費專項資金（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.