支持關鍵字更新的可搜索加密方案

?

支持關鍵字更新的可搜索加密方案

引文格式： 譚彭超,張應輝,鄭東.支持關鍵字更新的可搜索加密方案[J].桂林電子科技大學學報,2016,36(1):44-47.

譚彭超1,張應輝1,2,鄭東1

(1.西安郵電大學 無線網絡安全技術國家工程實驗室，西安710121;

2.中國科學院 信息安全國家重點實驗室，北京100093)

摘要：針對可搜索加密方案不支持關鍵字更新的問題，采用帶計數器的布隆過濾器，設計了一種支持關鍵字更新的可搜索加密方案。該方案允許在索引密文中增加或者刪除關鍵字，能夠對文件的索引密文進行動態修正，使得文件索引和文件的關聯更加緊密，提高了檢索效率。分析結果表明，該方案在已知密文模型下是安全的，可保證查詢關鍵字陷門信息不被云存儲服務器獲取。

關鍵詞：可搜索加密；隱私保護；關鍵字更新；云存儲

伴隨著計算機網絡的快速擴張，數據存儲已經變成網絡世界中一項費時費力的任務。為了節省存儲空間，簡化存儲過程，科學家提出了云存儲。然而服務器可能成為“內部攻擊者”[1]。可搜索加密技術有效防范系統內部攻擊的同時，允許用戶對自己的隱私數據進行高效查詢。

在可搜索加密研究領域，眾多專家學者做出了杰出的貢獻。Song等[2]率先提出“可搜索加密”的概念，并構建出首個基于全文本掃描的對稱可搜索加密方案。隨后Boneh等[3]于2004年提出PEKS方案，也是第一種公鑰可搜索加密方案。Goh[4]提出了基于索引的Z-IDX方案，使用布隆過濾器作為單個文件的索引結構。2011年Wang等[5]提出了支持多關鍵字排序的密文檢索算法(multi-keyword ranked search over encrypted，簡稱MRSE)，其相似性匹配的特性借鑒了knn算法[6]，向量內積的運用使得該算法支持多關鍵字和相似度排序，極大豐富了可搜索加密的內涵。MRSE算法是一種非常高效的可搜索加密算法，Wang等[7]也不遺余力地進行改進，在2014年提出了云環境下支持多關鍵字模糊查詢的可搜索加密隱私保護方案。

然而上述方案一旦生成一個文件的索引并為之加密，該索引的密文將不可更改，這大大限制了方案的靈活性。存儲是一個動態過程，數據也不可能一成不變，因此關鍵字變動的功能對于可搜索加密而言是非常適用的，而上述方案尚未考慮該功能。為此，結合一種帶計數器的布隆過濾器，構建了一種支持關鍵字變動的可搜索加密方案。

1預備知識

符號及其說明如表1所示。

表1　符號說明

布隆過濾器[8]是一種簡單的數據結構，其實質是一個x位的向量．若存在集合W={w1,w2,…,wl}，利用y個相互獨立的Hash函數H={h：{0,1}*→{1,x}}，將集合中每個元素wi∈W(1≤i≤l)的Hash值作為布隆過濾器的下標，對應位置為1。判斷一個元素x是否屬于集合P，將元素p作用于y個獨立的哈希函數：若輸出結果對應布隆過濾器的相應位有一位為0，則元素p不屬于集合P；若y個相應位置均為1，則元素p屬于P或者不屬于P，不屬于P的現象稱為假陽性。一個x位的布隆過濾器出現假陽性的概率大約為(1-e-ly/x)t，其中x為布隆過濾器的長度，y為Hash函數的個數，l為插入布隆過濾器中關鍵字的個數。

帶計數器的布隆過濾器是一種在布隆過濾器基礎上的改進型過濾器[9]。當多個關鍵字wi(i=1,2,3,…)通過y個相互獨立的哈希函數映射到同一個j下標時，對應下標位置上的值將不再是1，而是多個映射結果的疊加。圖1為布隆過濾器結構，圖2為帶計數器的布隆過濾器結構。其中X、Y為過濾器中已存在的關鍵字，Z為向過濾器中新添加的關鍵字。

圖1　布隆過濾器結構Fig.1　The structure of Bloom filter

圖2　帶計數器的布隆過濾器結構Fig.2　The structure of counting Bloom filter

2方案模型及性能

2.1系統模型

基于云儲存的可搜索加密系統模型涉及云服務器、數據擁有者和用戶。為保證數據隱私性，數據擁有者對文件加密后將密文上傳至云服務器。此外，數據擁有者需通過特定機制，為數據集中的每個文件構建唯一對應的文件索引，將文件索引的密文與文件的密文一起上傳至云端。用戶通過安全渠道獲得數據使用權后，利用選定的關鍵字構建查詢陷門，加密后發送給服務器。服務器在接收到查詢陷門后，通過特定的搜索機制返回相關密文文件。有關訪問控制見文獻[10]。

2.2安全模型

服務器是“honest-but-curious”，即云服務器是不完全可信的，服務器會根據方案設計協議執行所有過程并提供相應的服務，但有可能會收集用戶的查詢信息并進行分析。基于服務器獲取數據的能力，本研究選用已知密文的威脅模型。在該模型中，服務器僅能獲取數據擁有者上傳文件的密文、索引密文、查詢向量密文及檢索結果。

2.3方案性能

為有效利用加密數據，本方案具有如下性能：

1)支持索引密文中關鍵字的更新。允許用戶對文件索引密文進行動態更新。

2)隱私保護。保障服務器不能獲取文件明文信息，也不能獲取相應的索引明文信息和查詢陷門明文信息。

3)提高效率。盡可能提高執行效率，降低執行的復雜度。

3方案構造與分析

3.1方案構造

本方案采用帶計數器的布隆過濾器，由Setup、BuildIndex、Trapdoor和Query四個算法組成。其功能分別為：初始化方案所需的對稱密鑰；構造文件索引并加密；構建查詢陷門并加密；利用生成的查詢陷門，提交給服務器進行查詢。方案如下：

1)Setup。輸出Sk={S,M1,M2}。其中：k為最相似的文件的個數；(M1,M2)為m+2維隨機矩陣；S為長度為m+2的隨機0、1比特串，m為過濾器的長度。

2)BuildIndex(I,Sk)。利用帶計數器的布隆過濾器(m位，y個相互獨立的Hash函數H={h：{0,1}*→{1,m}})為選定的多個關鍵字wi(i=1,2,3,…)生成索引I，并填充為I=(I,εi,1)，其中εi為隨機數。根據S上每個bit的值，索引I分裂為(I′,I″)，若S[j](j=0,1,…,m+1)的值為1，則分裂后的子向量I′[j]、I″[j]對應位置上的值與I[j]相等；否則，子向量I′[j]、I″[j]可設置為任意隨機數，但需I′[j]+I″[j]=I[j]。分裂完成后便可對明文索引加密，密文形式為：

其結果r(IQ+εi)+t越大，表明相似度越高。根據參數k向用戶返回k個分數最高的文件。

3.2方案分析

2)正確性分析。將{w1,w2,…,w5}的索引密文與{w6,w7,w8}的索引密文相加，其效果等同于{w1,w2,…,w8}的索引密文。具體分析如下。

當S[j]=0時，Q′[j]、Q″[j]、Q[j]三者相等，則

又因為

而I[j]+Ii[j]是關鍵字集{w1,w2,…,w5}和{w6,w7,w8}通過布隆過濾器在相應位置上的結果，與關鍵字集{w1,w2…,w8}通過布隆過濾器的結果相同。因此，可得出結論：遍歷Q[j](I′[j]+I″[j]+I′i[j]+I″i[j])中的每個j(j=0,1,…,m-1)，最終結果是向量積QI。同理可得S[j]=1的情況。

計算結果表明，利用帶計數器的布隆過濾器產生的索引，可以實現關鍵字的更新。

3)安全性分析。對于數據隱私，可利用已經成熟的加密算法[11]。而索引隱私可確保：只要密鑰SK不被泄露，這種向量加密的方法在已知密文模型中被證明是安全的[5]。隨機因子r、t的引入以及隨機分裂過程的應用，可以針對同一查詢向量產生完全不同的2個陷門，保證了陷門的無關聯，即無法從一個可能已經泄露的陷門信息推測出另外未泄露的陷門信息。文件索引或查詢向量加密過程中的算法復雜度為O(m2)，檢索過程中的內積計算復雜度為O(m)。在已知密文模型的條件下，密鑰S是未知的，向量I分裂為2個m+2位的隨機向量I′、I″。假定有n個加密的文件索引，可列出2(m+2)n個線性方程，其中有2(m+2)n個未知量，且矩陣M1、M2中有2(m+2)2個未知量，由于未知量多于已知量，所以無法求解方程組，也就無法獲得索引的明文信息。同樣地，查詢向量q可分裂為q1、q2，也是2個m+2位隨機向量，能夠列出2(m+2)個方程，其中有2(m+2)個未知量和逆矩陣中的2(m+2)2個未知量，由于未知量多于已知量，本方案在已知密文模型下的安全性是有保障的。

4)效率分析。本方案結合文獻[5]、[9]進行了改進。假定本方案與文獻[5]的方案初始化參數相同，比較本方案和文獻[5]的方案，結果表明，本方案只有文件索引生成時間有微小的增加，而文件索引的生成時間、查詢向量的生成時間、文件索引的加密時間、查詢向量的加密時間、搜索時間等指標維持不變。查詢向量生成時間與關鍵字數量呈正相關增長；更新文件索引中的關鍵字耗時與待更新關鍵字的數量呈線性關系；搜索時間與文件集大小呈線性增長；查詢向量中的關鍵字數量對搜索時間幾乎無影響。

4結束語

采用帶計數器的布隆過濾器，設計了一種支持關鍵字更新的可搜索加密方案，允許用戶對已構建的文件索引進行修改。在已知密文模型下對該方案的安全性進行分析，結果表明，該方案能夠保證在已知密文模型下的數據安全。同時，對該方案的性能作了定性分析，分析結果表明，該方案在生成文件索引向量時，耗時有微小的增加，但能夠動態更新文件索引密文中的關鍵字，更新過程的耗時和更新的關鍵字數量呈線性增長關系。

參考文獻:

[1]CHENGFangquan,PENGZhiyong,SONGWei,etal.Anellicientprivacy-preservingrankqueryoverencrypteddataincloudcomputing[J].JournalofComputers,2012,35(11):2215-2227.

[2]SONGDX,WAGNERD,PERRIGA.Practicaltechniquesforsearchesonencrypteddata[C]//ProceedingsoftheIEEESymposiumonSecurityandPrivacy,2000:44-55.

[3]BONEHD,DICRESCENZOG,OSTROVSKYR,etal.Publickeyencryptionwithkeywordsearch[C]//AdvancesinCryptology-EUROCRYPT.Heidelberg:Springer,2004:223-238.

[4]GOHEJ.Secureindexes[R/OL].(2004-03-16)[2015-08-15].http://eprint.iacr.org/2003/216.

[5]CAON,WANGC,LIM,etal.Privacy-preservingmulti-keywordrankedsearchoverencryptedclouddata[J].IEEETransactionsonParallelandDistributedSystems,2014，25(1):222-233.

[6]WONGWK,CHEUNGDWL,KAOB,etal.SecureKNNcomputationonencrypteddatabases[C]//Proceedingsofthe2009ACMSIGMODInternationalConferenceonManagementofData.[S.l.]:ACM,2009:39-152.

[7]WANGBing,YUShucheng,LOUWenjing,etal.Privacy-preservingmulti-keywordfuzzysearchoverencrypteddatainthecloud[C]//IEEEConferenceonComputerCommunications,2014:2112-2120.

[8]BLOOMBH.Space/timetrade-offsinhashcodingwithallowableerrors[J].CommunicationsoftheACM,1970,13(7):422-426.

[9]ROTTENSTREICHO,KANIZOY,KESLASSYI.Thevariable-incrementcountingBloomfilter[J].IEEEACMTransactionsonNetworking,2014,22(4):1092-1105.

[10]BYUNJW,LEEDH,LIMJ.Efficientconjunctivekeywordsearchonencrypteddatastoragesystem[C]//3rdEuropeanPKIWorkshop:TheoryandPractice.Berlin:Springer,2006:184-196.

[11]張應輝，鄭東，趙慶蘭.密碼學綜述[J].西安郵電大學學報，2013,18(6):1-10.

編輯：張所濱

A searchable encryption scheme for supporting keyword update

TAN Pengchao1, ZHANG Yinghui1.2, ZHENG Dong1

(1.National Engineering Laboratory for Wireless Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, China;

2.State Key Laboratory of Information Security, Chinese Academy of Sciences, Beijing 100093, China)

Abstract：Keyword update is not supported by the exiting searchable encryption scheme, so a searchable encryption scheme for supporting keyword update with counting Bloom filter is designed. Fixing cipher index through adding or deleting keyword is allowed in the scheme, the cipher of file index can be revised. And association of file and its index can be made more closely. It is very convenient to improve the efficiency of data retrieval. The analysis result shows that the new scheme is safe in the known cipher model, which can protect the query keyword and the trapdoor information from being elicited by cloud storage server.

Key words：searchable encryption; privacy protection; keyword update; cloud storage

中圖分類號：TP309.2

文獻標志碼：A

文章編號：1673-808X(2016)01-0044-04

通信作者：鄭東(1964-)，男，山西翼城人，教授，博士，研究方向為密碼學、云存儲安全。E-mail:zhengdong@xupt.edu.cn

基金項目：國家自然科學基金(61272037，61402366，61472472)；陜西省自然科學基礎研究計劃(2013JZ020,2015JQ6236)；西安郵電大學研究生創新基金(CXL2014-10，CXL2014-04)

收稿日期：2015-10-10