支持語義擴展的動態多關鍵詞密文排序檢索

龐曉瓊 嚴小龍 陳文俊 余本國 聶夢飛

摘 要：針對云存儲環境下已有的動態多關鍵詞密文排序檢索方案不支持關鍵詞語義擴展、不具備前向安全和后向安全的問題，提出一種支持語義檢索且具備前向安全和后向安全的動態多關鍵詞密文排序檢索方案。該方案通過構建語義關系圖實現查詢關鍵詞的語義擴展;使用樹索引結構實現數據的檢索和動態更新;利用向量空間模型實現多關鍵詞排序搜索;基于安全K近鄰算法對維度擴展后的索引和查詢向量進行加密。安全性分析表明，該方案在已知密文模型下是安全的且具有動態更新時的前向安全和后向安全。效率分析及仿真實驗結果表明，該方案在服務器檢索效率方面優于目前同類型具有相同安全性或相同功能的方案。

關鍵詞：?對稱可搜索加密;多關鍵詞排序檢索;動態更新;語義擴展

中圖分類號：TP309

文獻標志碼：A

文章編號：1001-9081（2019）04-1059-07

Abstract： Since existing dynamic multi-keyword ranked search schemes over encrypted data in cloud storage can not support semantic extension and do not have forward and backward security， a multi-keyword ranked search scheme over encrypted cloud data was proposed， which supported semantic search and achieved forward and backward security. The semantic extension of query keywords was achieved by constructing semantic relationship graph， the retrieval and dynamic update of data were achieved by use of tree-based index structure， the multi-keyword ranked search was achieved based on vector space model， and the extended index and query vectors were encrypted by using secure K-nearest neighbor algorithm. Security analysis indicates that the proposed scheme is secure under the known ciphertext model and achieves forward and backward security during dynamic update. Efficiency analysis and simulation experiments show that this scheme is superior to the same type schemes with the same security or function in server retrieval efficiency.

Key words： symmetric searchable encryption; multi-keyword ranked search; dynamic update; semantic extension

0?引言

隨著云計算的迅速發展，用戶開始將數據遷移到云服務器，以避免繁瑣的本地數據管理同時獲得更加便捷的服務[1]，但近年來頻繁發生的用戶數據隱私泄露問題使得云安全問題受到人們的廣泛關注。為保護敏感數據的隱私性，許多用戶選擇將數據以密文形式存儲在云端[2]。但是，數據加密使得傳統的明文關鍵詞檢索機制失效，如何對密文數據進行高效安全的檢索成為亟待解決的問題。可搜索加密技術就是為了解決密文檢索難題而提出的，該技術允許服務器在收到用戶提交的關鍵詞陷門后對密文直接進行檢索，并將檢索到的密文數據返回給用戶;同時在檢索過程中，云服務器無法根據密文文件以及用戶提交的查詢陷門推測出有關用戶數據和檢索詞的有用信息。

可搜索加密主要分為對稱可搜索加密和非對稱可搜索加密[3]，本文研究前者。最初，大多數對稱可搜索加密方案都僅支持單關鍵詞檢索[4-8]，然而實際情形中，用戶為了更精確獲取感興趣的內容，往往輸入多個關鍵詞進行檢索，并希望返回與輸入關鍵詞最相關的前K個文件。

為了滿足此需求，近年來，支持多關鍵詞排序檢索的方案陸續被提出：2011年，Cao等[9]利用坐標匹配和向量內積技術首次提出了隱私保護的多關鍵詞排序檢索方案，該方案在構建文件索引向量和查詢向量時未考慮不同關鍵詞對文件的重要程度。2014年，Sun等[10]對Cao方案[9]作了改進，在構建索引向量和查詢向量時引入了關鍵詞權重，并通過向量余弦計算相關性提高了排序的精度。但以上工作都未考慮數據的動態更新。

現實情境中，數據擁有者需對其在云端的數據增加或刪除。2014年，Sun等[11]以平衡二叉樹作為索引提出了支持動態更新的多關鍵詞排序檢索方案。2017年，那海洋等[12]以B+樹作為索引提出了支持動態更新的多關鍵詞排序檢索方案。但是，這兩個工作都未考慮不可信云服務器可能會保存已經搜索過的檢索或已經刪除的文檔，并利用先前的查詢對新插入文檔進行檢索和利用新查詢對已被刪除文件進行檢索，即方案未實現前向安全和后向安全。2014年，Yang等[13]提出了在動態更新時具有前向安全和后向安全的多關鍵詞排序檢索方案，但該方案采用倒排索引使得檢索效率較低。

文獻[9-13]的研究工作都是基于查詢關鍵詞的嚴格匹配，未考慮詞語間的語義關系，這意味著返回的檢索結果完全取決于用戶的查詢詞是否與文檔中預設的關鍵詞嚴格匹配。然而在某些情況下，用戶對相關領域知識了解不足，提交的關鍵詞不能準確全面地表達用戶的實際檢索意圖，造成檢索結果不全面。針對此問題，2016年，Xia等[14]從語義角度考慮，通過構建語義關系圖擴展用戶的查詢，構成新查詢以更全面表達用戶查詢的語義信息，并提出了基于語義擴展的多關鍵詞排序檢索方案;但該方案不具備數據動態更新時的前向安全和后向安全。

本文針對支持語義擴展的多關鍵詞密文排序檢索技術展開研究，并提出一個支持語義擴展的動態多關鍵詞密文排序對稱可搜索加密方案，該方案同時具備前向和后向安全的數據動態更新功能，方案在已知密文模型下是安全的，且具有較高的檢索效率。

1?系統模型與威脅模型

1.1?系統模型

系統模型包含三個實體，如圖1所示。

1）數據擁有者（Data Owner， DO）。

DO加密文檔、構建安全索引，將它們存儲到云端;將用于檢索的秘密信息通過安全信道發送給已認證用戶。更新時，DO生成更新信息分別發送給云服務器和認證用戶。

2）認證用戶（Authenticated User， AU）。

AU生成查詢陷門，并將陷門和希望返回的文檔數K發送到云端。收到云端返回的前K個最相關的密文文檔后對其進行解密。

3）云服務器（Cloud Server， CS）。

收到AU的檢索請求后，CS對加密索引進檢索，并且依據相關性規則對檢索結果排序，最后返回與檢索請求最相關的前K個密文文檔。數據更新方面，CS根據接收到的信息更新密文索引和密文文檔集合。

1.2?威脅模型

方案中考慮如下敵手模型：收到用戶的查詢請求時，CS會遵守既定的規則，執行相關操作;但CS對存儲在其上的數據是好奇的，并試圖通過分析存儲在其上的數據和接收到的信息獲取盡可能多的用戶數據隱私。在已知密文模型下CS可獲得密文文檔集合、密文索引、加密后的查詢陷門。此外CS可能會保存已經搜索過的陷門或已刪除的文檔，能夠利用以前的陷門對新插入的文檔進行檢索，或利用新陷門對已被刪除的文件進行查詢。

2?預備知識

2.1?符號定義

通過計算向量Dfj和Q的內積可得到fj與查詢間的相關度。

2.3?語義關系圖

2.4?語義擴展后的查詢向量構建

AU生成待檢索關鍵字集，并根據語義關系圖生成語義擴展后的檢索關鍵詞集s，然后生成語義擴展后的查詢向量Q，構建方法見算法GenSemanticExtentionVector（）。經語義擴展后的檢索關鍵詞集合s和文件fj的相關性分數計算如式（7）所示：

2.5?未加密索引樹構建

在具體方案中，采用安全K近鄰技術[16]加密上述索引樹T中的葉子節點向量和查詢向量。

3?本文方案

本文方案包含四個子算法（Setup、GenIndex、GenTrapdoor、Search），具體過程如下：

DO生成一個（m+d+1）維二進制向量S作為拆分指示向量，以及兩個（m+d+1）×（m+d+1）階可逆矩陣{M1，M2}用于加密拆分后的向量，其中m是關鍵詞詞典的基數，d是外包文件可能的最大數量。安全密鑰為SK={S，M1，M2}，同時生成對稱密鑰sk用于加密文件集合。

收到AU的搜索請求后，CS對加密索引樹I進行檢索。若u為I中的一個內部節點，對于Ts中的每一項f（k1，wt），令at=λu[f（k1，wt）]，如果至少存在一個at使得Dec（g（k2，wt），at）=1，則以相同步驟繼續檢索u的左右孩子。當到達某一葉子節點時，計算該葉子節點的加密文件索引向量fj與AU加密的查詢向量間的內積，有式（10）成立。

CS的檢索過程見算法Search（）。

4?動態更新

4.1?插入和刪除

算法UpdHelper（j，Ts，updtype）→{I′s，cj}由DO執行，以生成需要發送給CS的更新信息{I′s，cj}。輸入參數j為文件標識符;updtype指明更新類型是刪除還是插入;Ts為需要修改的樹節點集合，一般為從更新節點到根節點路徑上的所有節點。具體地：1）當updtype為刪除時。若DO想刪除文件fj，首先把存有fj信息的葉子節點刪除，然后依據索引樹構造規則對Ts中各節點的向量進行修改，得到新的節點集合T′s。例如，在圖3中刪除f3，Ts為{r22，r11，r}，對Ts中節點的向量修改后得到T′s，如r22的向量由（1，1，0，1）更新為（1，0，0，1），刪除f3后的索引樹如圖4所示。接著通過偽隨機函數對T′s中內部節點的向量加密，得到加密后的更新信息集合I′s。DO將{I′s，null}提交給CS，將vj加入集合N，同時將vj發送給AU，AU將vj從中刪除。

5?安全性分析

5.1?索引和陷門的機密性

加密索引樹葉子節點中fj的機密性基于安全K近鄰技術。安全K近鄰是一個不確定算法，即使兩個文檔的關鍵詞集合相同，加密后的文件索引向量也不相同，更多有關安全K近鄰算法加密數據的安全性分析可參考文獻[16]。加密索引樹每個內部節點中的哈希表λu，其第一項將關鍵詞通過偽隨機函數隱藏，第二項將內部節點對應向量位加密，只要保證偽隨機函數密鑰是安全的，僅由加密索引和密文文檔集合，CS不能推斷出內部節點向量Du。

陷門由{Ts，}構成，Ts由偽隨機函數f（k1，·）和g（k2，·）隱藏檢索關鍵詞集合s得到，只要保證密鑰k1和k2是安全的，CS就不能推斷出s。由安全K近鄰加密擴展后的查詢向量得到，由于安全K近鄰是一個不確定算法，即使兩個檢索關鍵詞集合相同，對應的也不相同。

5.2?陷門的無關聯性

本文方案采用二進制向量對文件索引向量和查詢向量隨機拆分，向量加密方法是一種不確定性加密，即使對前后兩次相同的查詢請求，也會生成不同的加密查詢向量，從這個角度看實現了查詢的無關聯性。然而，由于相同的搜索請求會生成相同的Ts，檢索時訪問的內部節點和最終輸出的加密文檔是相同的;另外，即使被加密成了不同的向量，對于相同的查詢請求，CS計算得到的相關性分數是相同的。基于以上兩點，CS能夠關聯相同的查詢請求，也只有在此種情況下，在已知密文模型下會泄露檢索模式或訪問模式。

5.3?前向安全和后向安全

前向安全性保證CS無法利用以前的查詢陷門對新插入文檔檢索;后向安全性保證新陷門不能查詢已刪除文件。利用安全K近鄰算法加密擴展后的文件索引向量和查詢向量，本文方案保證了動態更新時的前向安全和后向安全。

從式（12）可看出，由于aj的隨機性，當查詢非法時，正確的相關性分數將被混淆。因此，本文方案實現了前向安全與后向安全。

5.4?功能及安全性比較

下面從功能和安全性方面將本文方案與文獻[9-14]方案進行比較，結果如表1所示。僅本文方案同時具有語義檢索功能和動態更新時的前向安全和后向安全。

文獻[9-10，14]在已知背景知識模型下保證了陷門不可關聯性，文獻[11-13]和本文方案在已知密文模型下保證了陷門不可關聯性。

6?效率分析及仿真實驗

下面從加密索引構建、服務器檢索和索引更新三個算法的計算開銷方面，將本文方案與文獻[13-14]方案進行對比，結果如表2所示。表2中：L表示構建每個內部節點的操作;X表示向量間點積運算（文獻[13]方案和本文方案中表示兩個（m+d+1）維向量間點積運算，文獻[14]中表示兩個m維向量間點積運算）;E和D分別表示加解密操作;M表示取模運算;R表示更新未加密向量的操作;B表示擴展文件索引向量的構建操作;t為s中的關鍵詞數;m為關鍵詞字典大小;d為外包文檔集合中文件最大數量;θ為包含查詢關鍵詞的文檔數。現實場景中，θ遠小于文檔集合基數n。

文獻[13]方案采用倒排索引結構，本文方案和文獻[14]方案為提高服務器檢索效率，采用平衡二叉樹作為索引。文獻[13]方案在加密索引構建和更新索引方面效率最優，在檢索時需計算2n次兩個（m+d+1）維向量間點積運算。文獻[14]方案在構建加密索引樹時，利用安全K近鄰技術對葉子節點和內部節點加密，因此在檢索時，需對檢索路徑中的內部節點和葉子節點求相關性分數，最壞情況下，需做2θ lb n次兩個m維向量間點積運算。本文方案在構建加密索引樹時，僅利用安全K近鄰技術對葉子節點加密，因此在檢索時，僅需對葉子節點求相關性分數，對內部節點做解密操作，在最壞情況下，需做2θ次兩個（m+d+1）維向量間點積運算。

接下來，對本文方案和文獻[13-14]方案的服務器檢索開銷進行仿真實驗及對比。實驗中使用的數據集來源于英文文檔集RFC（Request For Comments database）[18]，截止進行實驗時RFC共包含8267篇文檔，本文選用6000篇文檔作為測試數據，利用全文檢索工具Lucene對文檔進行關鍵詞提取，共得到9208個不同的關鍵詞。實驗環境：基于VMWare Workstation的虛擬機，宿主機CPU為Intel酷睿i7 6500U，虛擬機分配了1顆2核CPU、2GB內存，操作系統為Ubuntu 16.04 LTS 32位，對稱加密算法為SM4，設置m=4000，d=6000，t=10。

為觀察本文方案服務器檢索開銷與文檔數n的關系，實驗1中，固定θ分別為90和300，設置n=1000～6000（步長1000），實驗結果如圖6所示。可以看出，當θ確定時，檢索時間隨文檔數增加呈對數增長，與性能分析結果一致。特別地，當θ=90時，n=1000，6000的檢索時間分別為16.30ms和18.69ms;當θ=300時，n=1000，6000的檢索時間分別為51.13ms和59.49ms。

為觀察本文方案服務器檢索開銷與θ的關系，實驗2中，固定文檔數n為2000，設置θ從50～300，步長50，實驗結果如圖7所示。可以看出，檢索時間隨θ的增加呈線性增長，與性能分析結果一致。特別地，當θ=50，300時，檢索時間分別為9.37ms和54.13ms。

文獻[13]方案的檢索開銷與θ無關，文獻[14]方案和本文方案的檢索開銷與θ相關，為對三者進行比較，實驗3中，固定θ分別為90和300，設置文檔數n從1000～6000，步長1000，實驗結果如圖8所示。可以看出：1）文獻[13]方案的檢索時間隨著n的增加基本呈線性增長;2）文獻[14]方案在θ=90的檢索開銷略低于文獻[13]方案，在θ=300時顯著高于文獻[13]方案;3）本文方案在θ=90與θ=300時的檢索開銷均明顯低于文獻[13-14]方案，這是因為文獻[13]方案檢索時需要計算2n次兩個（m+d+1）維向量間的點積運算，文獻[14]方案需做2θ lb n次兩個m維向量間點積運算，本文方案只需進行2θ次兩個（m+d+1）維向量的點積運算（θn），當然本文方案還需進行tθ（lb n-1）次一個1bit的解密操作，但1bit解密操作的速度非常快，因此在檢索效率方面本文方案優于文獻[13-14]方案。

7?結語

本文提出了一個支持語義擴展的動態多關鍵詞密文排序檢索方案，對方案的安全性進行了分析，并與現有的多關鍵詞密文排序檢索方案進行了功能和安全性比較，實驗結果表明僅本文方案同時具有語義檢索功能和動態更新時的前向安全和后向安全。此外，對方案的效率進行了理論分析和仿真實驗，實驗結果表明本文方案在加密索引構建和索引更新效率方面弱于文獻[13]方案，但在服務器檢索效率方面顯著優于具有相同安全性的文獻[13]方案和具有語義擴展功能的文獻[14]方案。

參考文獻（References）

[1] 張玉清， 王曉菲， 劉雪峰， 等.云計算環境安全綜述[J]. 軟件學報， 2016， 27（6）： 1328-1348. （ZHANG Y Q， WANG X F， LIU X F， et al. Survey on cloud computing security[J]. Journal of Software， 2016， 27（6）： 1328-1348.）

[2] 魏凱敏， 翁健， 任奎. 大數據安全保護技術綜述[J]. 網絡與信息安全學報， 2016， 2（4）： 1-11. （WEI K M， WENG J， REN K. Data security and protection techniques in big data： a survey[J]. Chinese Journal of Network and Information Security， 2016， 2（4）： 1-11.）

[3] 董曉蕾， 周俊， 曹珍富， 等.可搜索加密研究進展[J]. 計算機研究與發展， 2017， 54（10）： 2107-2120. （DONG X L， ZHOU J， CAO Z F， et al. Research advances on secure searchable encryption[J]. Journal of Computer Research and Development， 2017， 54（10）： 2107-2120.）

[4] SONG X D， WAGNER D， PERRIG A. Practical techniques for searching on encrypted data[C]// Proceedings of the 2000 IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE， 2000： 44-55.

[5] GOH E. Secure indexes[EB/OL]. [2018-05-10]. http：//crypto.stanford.edu/-eujin/papers/secureindex.

[6] CHANG Y C， MITZENMACHER M. Privacy preserving keyword searches on remote encrypted data[C]// ACNS 2005： Proceedings of the 2005 Applied Cryptography and Network Security， LNCS 3531. Berlin： Springer， 2005： 442-455.

[7] CURTMOLA R， GARAY J， KAMARA S， et al. Searchable symmetric encryption： improved definitions and efficient constructions[C]// CCS 2006： Proceedings of the 13th ACM Conference on Computer and Communications Security. New York： ACM， 2006： 79-88.

[8] WANG C， CAO N， REN K， et al. Enabling secure and efficient ranked keyword search over outsourced cloud data[J]. IEEE Transactions on Parallel & Distributed Systems， 2011， 23（23）： 1467-1479.

[9] CAO N， ?WANG C， LI M， et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data[C]// Proceedings of the 30th IEEE International Conference on Computer Communications. ?Piscataway， NJ： IEEE， 2011： 829-837.

[10] SUN W， WANG B， CAO N， et al. Privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking[J]. IEEE Transactions on Parallel & Distributed Systems， 2014， 25（11）： 3025-3035.

[11] SUN X， ZHOU L， FU Z， et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data supporting dynamic update[J]. International Journal of Security & Its Applications， 2014， 8（6）： 1-16.

[12] 那海洋， 楊庚， 束曉偉. 基于B+樹的多關鍵字密文排序檢索方法[J]. 計算機科學， 2017， 44（1）： 149-154. （NA H Y， YANG G， SHU X W. Multi-keyword ranked search method based on B+tree[J]. Computer Science， 2017， 44（1）： 149-154.）

[13] YANG Y， LI H， LIU W， et al. Secure dynamic searchable symmetric encryption with constant document update cost[C]// Proceedings of the 2014 IEEE Global Communications Conference. Piscataway， NJ： IEEE， 2014： 775-780.

[14] XIA Z， CHEN L， SUN X， et al. A multi-keyword ranked search over encrypted cloud data supporting semantic extension[J]. International Journal of Multimedia & Ubiquitous Engineering， 2016， 11（8）： 107-120.

[15] WITTEN I H， MOFFAT A， BELL T C. Managing Gigabytes： Compressing and Indexing Documents and Images[M]. San Francisco： Morgan Kaufmann Publishers， 1999： 180-188.

[16] WONG W K， CHEUNG W L， KAO B， et al. Secure kNN computation on encrypted databases[C]// SIGMOD 2009： Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2009： 139-152.

[17] CORMEN T H， LEISERSON C E， RIVEST R L， et al. Introduction to Algorithms[M]. 3rd ed. Cambridge， MA： MIT Press， 2009： 256-261.

[18] IAB， IETF. Request for comments available[DB/OL]. [2018-05-10]. https：//www.rfc-editor.org/retrieve/bulk/.