增量式多關鍵字可搜索加密算法

彭凝多，羅光春，秦 科，李春虎，馬致遠

（電子科技大學 計算機科學與工程學院，四川 成都611731）

0 引 言

多關鍵字可搜索加密算法是可搜索加密技術［1－6］中的重要解決方案。一方面，多關鍵字檢索提供了精煉的檢索結果；另一方面，多關鍵字檢索也是實現高級查詢功能 （例如短語查詢、限定域查詢、模糊查詢等）的基礎。一個安全的多關鍵字可搜索加密算法，不僅要保證文件與查詢內容的保密性，同時要保證敵手無法從查詢的統計信息中獲得有用的信息，包括單次查詢的關鍵字數量、關鍵字之間的關系 （例如屬于同一短語）等［7］。

然而，當前典型的安全多關鍵字可搜索加密方案［8，9］并不適用于云存儲模式。一方面，這類方案通常要求全局索引，因此一般假定用戶是查詢密集型，更新文件的情況較少。事實上，在云存儲應用中 （例如網盤），用戶增刪與更新文件往往較頻繁，每次更新一個文件均會導致重構整個安全索引。由于該重構無法在服務器上完成 （保障安全性），因此效率較低。另一方面，現有的增量式動態索引方案并不直接支持多關鍵字檢索［10］，在該增量式數據結構中，鏈表的一個頭結點只對應于一個關鍵字，而對單關鍵字查詢的結果求交集并不安全 （泄漏統計信息）。同時，非全局索引結構的對稱可搜索加密算法研究較早，且僅支持單關鍵字查詢 （例如基于元數據的結構與分布式索引結構［11］），而支持多關鍵字的算法僅在非對稱可搜索加密算法中 （本文僅討論對稱加密方案）利用特殊的數學性質實現，例如典型的在雙線性空間上運算的可同時匹配多關鍵字的數據結構［7］。

為了滿足安全多關鍵字檢索的需求，適應云存儲模式下頻繁更新的問題，本文首先提出適用于多元素判定的新型隨機布隆過濾器，然后在此基礎上構造安全的多關鍵字可搜索加密方案，最后實驗驗證該方案的實用性。

1 相關符號與數學基礎

稱一個函數negl（k）：N→R 是可忽略的，如果對于任意多項式函數p（k），存在一個整數N＞0，使得對于所有k＞N，滿足關系negl（k）＜1/p（k）。稱一個函數f： ｛0，1｝k× ｛0，1｝n→ ｛0，1｝m為偽隨機函數 （pseudorandom function），如果在多項式時間內無法與一個隨機函數分辨。

2 隨機布隆過濾器

為提高多關鍵字查詢效率并支持更多高級查詢功能，需要一種安全快速支持多關鍵字命中判定的數據結構。傳統布隆過濾器 （Bloom filter，BF）用于快速判斷一個元素是否屬于一個集合，其擴展變化集中在效率與命中率上。本文對布隆過濾器進行安全性擴展，過濾器在保持傳統方案的高效條件下，其特性為支持多元素的同時判定且隱藏查詢元素的統計信息（包括查詢的元素數量、訪問模式等）。

2.1 傳統布隆過濾器

布隆過濾器用于快速判斷一個元素x 是否屬于一個集合S＝ ｛s1，…，sn｝。集合S 編碼為一個具有l比特的比特串B。所有位初始化為0。設置r 個不同的哈希函數h1，…，hr，每一個函數滿足h：｛0，1｝＊→ ［1，l］。對于集合中的任一元素s∈S，設置B 中的第h1（s），…，hr（s）比特位為1 （某一比特位可能被多次重復置為1）。判斷一個數據是否滿足x∈S，只需要檢查B 中的比特位h1（x），…，hr（x）是否全為1。在錯判率為1/2r時，布隆過濾器長度（比特）的最優解為l＝nr/ln2。

2.2 隨機布隆過濾器

擴展的布隆過濾器支持多元素的同時判別，即判斷集合X＝ ｛x1，…，xm｝是否為一個集合S＝ ｛s1，…，sn｝的子集，且在該判斷過程中保證隨機性。

定義1 隨機布隆過濾器為3個多項式時間算法的集合：①B←Build（S）：構造過濾器。輸入集合S＝ ｛s1，…，sn｝。輸出具有l比特的比特串B；②A←Trans（X）：構造過濾器輸入數據。輸入需測試的數據X＝ ｛x1，…，xm｝。輸出轉換結果A。在同樣輸入條件下，輸出具有隨機性；③b←Test（A，B）：測試數據。輸入測試數據X 對應的轉換結果A，目標集合S 對應的比特串B。如果X∈S 則輸出b＝1，否則輸出b＝0。

過濾器的具體構造在算法1中給出。

若以傳統的最優解為標準，對于每一個元素而言，錯判率最高為1/2r（該值在m＝v時取得），最低為1/2rv（該值在m＝1時取得）。因此，對于整體而言，錯判率最高為1－ （1－1/2r）v（該值在m＝v 時取得）。最高錯判率作為一個參數選擇的重要指標，根據應用的需求進行設定。

影響建筑物穩定的因素很多,而建筑物沉降作為系統的主要輸出信息則是一個具有灰色特征的隨機變量，通過分析建筑物沉降數據的特點，結合灰色模型的特征，采用灰色模型來預測建筑物的沉降趨勢是可行、有效的方法。傳統GM(1，1)模型對于不同數據序列，會出現偏差較大的情況。當原始沉降數據序列為持續增長或者數據變化較大的數據序列時，模型預測結果的偏差就會變大，預測精度普遍偏低［2］。另外，灰色模型是用歷史信息來預測將來的信息，所以信息的維數對預測精度也有一定影響，如何合理選擇數據的維度是保證預測精度的關鍵。

2.3 安全性證明

在應用中，判定的隨機性表現為無法通過記錄的統計信息來分辨用戶的查詢，即無法分辨當前查詢是否與之前某一查詢相同。該特性定義如下：

定義2 隨機布隆過濾器的歷史查詢不可分辨性 （indistinguishable chosen history attack，IND－CHA）：

挑戰者設置2rv 個私有哈希函數。敵手提交兩個查詢X1，X2（稱X1為歷史查詢）。挑戰者從查詢 （X1，X2）、（X1，X1）中隨機選擇一個組合 （X1，Xb），計算A1←Trans（X1），Ab←Trans（Xb）并返回 （A1，Ab）給敵手。敵手任意選擇多項式時間函數f 分辨b。稱查詢方案為IND－CHA 安全的，當且僅當在多項式時間內，滿足概率：｜Pr（f（A1，A1）＝1）－Pr（f（A1，A2）＝1）｜≤negl（k）。

需要注意，安全模型的應用前提是哈希函數為私有的。在實際應用中，所有哈希函數均公開。因此，哈希函數的結果安全性需要通過對輸入的數據加密保護來實現。在下一章的應用中將給出其實現方法。

定理1 隨機布隆過濾器具有IND－CHA 安全性，且分辨性上限為1/2r，其中r為正確率相關參數。

證明：由于該方案的安全性較明顯，這里簡化描述證明過程。在任何情況下，轉換函數從2rv個哈希函數中隨機選擇rv個，其選擇方案共有C（2rv，rv）種，因此，分辨該次選擇（即分辨兩次A1）的概率為1/C （2rv，rv）＜＜1/2r。當r較大時，該值為一個可忽略函數值。

該定理指出，安全性與出錯率保持一致。因此，增加哈希函數的數量r 將同時提高安全性與正確性。在這里，典型的安全值為r＝64，128，256 等，一般與應用中加密方案的密鑰長度保持一致。

3 增量式多關鍵字可搜索加密算法

這里，首先定義安全多關鍵字可搜索加密方案的算法模型。

定義3 安全多關鍵字可搜索加密算法 （對稱加密方案）為4個多項式時間算法的集合：①K←Gen （1k）：輸入安全參數k，輸出對稱加密密鑰K。算法由用戶執行；②S←Enc（K，d，id（d））：輸入對稱加密密鑰K、某文檔d和唯一標識符id（d），輸出該文檔的可查詢密文S。算法由用戶執行，可查詢密文連同采用對稱加密算法加密后的文檔 （文檔加密方案獨立于本算法）存儲到遠程服務器；③t←Token（K，W）：輸入對稱加密密鑰K、查詢的多個關鍵字W ＝ ｛w1，…，wm｝，輸出查詢令牌t。算法由用戶執行，t發送到遠程服務器進行查詢；④b←Search（S，id（d），t）：輸入可查詢密文S、對應的文檔唯一標識符id（d）、查詢令牌t。輸出b＝1 （該文檔滿足查詢條件）或b＝0 （不滿足查詢條件）。算法由服務器執行，服務器返回給用戶所有滿足查詢條件的文檔。

其中，文檔唯一標識符id（d）可由服務器提供。接下來討論該方案的具體構造。

定義一個偽隨機置換函數（pseudo－random permutation，PRP）如下 （其中k為密鑰長度，s為元素長度）

定義一個哈希函數如下 （l為布隆過濾器長度）

在具體實現中，偽隨機置換函數可基于對稱加密算法（如AES）或加密哈希函數實現。多關鍵字可搜索加密方案的具體構造在算法2中給出。在算法中，由于一個文件的關鍵字數上限為｜d｜/2 （單詞＋分隔符），因此為保證加密結果與文件內容無關，需用隨機值填滿｜d｜/2個關鍵詞。

本文采用通用的對稱可搜索加密算法的安全模型，證明提出的算法滿足其安全性。

定理2 如果π為偽隨機置換函數，則增量式多關鍵字可搜索加密算法具有抗選擇關鍵字攻擊語義安全性 （semantic security against chosen keyword attack，CKA）。

證明：模擬輸出 ｛S＊，t＊｝的模擬器構造如下：初始化一個布隆過濾器B＊，隨機選擇rv｜d｜個位置P＊＝｛，…，｝設置為1 （注：文件大小｜d｜是已知的，因此最大可能的關鍵字數量為｜d｜/2）。初始化一個布隆過濾器S＊，設置一個哈希函數h＊，對每一個位置p＊∈，計算y＊＝h＊（id（d）），并將S＊的第 ｛，…，｝位設置為1。對于用戶的每次輸入W ＝ ｛w1，…，wm｝，對每一個不同的關鍵詞w∈W，不重復的隨機選擇2rv個位置 ｛，…，｝∈P＊建立映射關系。在任一次查詢中，對應于w∈W，從 ｛，…，｝中隨機選擇rv/m 個 數 據，…，｝，并 返 回 對 應 的 哈 希 結 果｛，…，｝，多組返回的模擬數據形成統一的t＊。

現在證明敵手無法分辨真實數據與模擬數據，即分辨｛S，t｝與 ｛S＊，t＊｝。由于敵手僅以negl（k）的概率獲取密鑰K，因此，偽隨機置換函數保證π（K，w）與隨機值不可分辨，即所有關鍵字的加密結果與隨機字符串不可分辨。因此，對任一關鍵字，布隆過濾器的2rv 個位置與隨機位置不可分辨。從上面的構造中可以看到，模擬器在模擬數據的過程中，所有計算過程與真實計算過程同步且一一對應 （即每個關鍵字對應一個隨機關鍵字），因此其最終運算結果無法分辨，即 ｛S，t｝與 ｛S＊，t＊｝無法分辨。

4 性能分析

為了驗證該算法的運行效率與實用性，我們將所有算法用C＋＋編碼，并編制模擬器模擬輸入文件數據。所有代碼在一臺具有2.6GHz CPU 和2GB內存的雙核PC機上運行。在程序中，π設置為AES加密算法。布隆過濾器的參數r＝64，v＝10。統一設置文件大小為2KB。統一設置關鍵字數量為文件大小的一半，即｜d｜/2。

為了與當前代表性的多關鍵字可搜索加密算法作比較，這里選取文獻 ［8］（R2014）與文獻 ［9］（R2012）提出的方案，分別作為矩陣式索引算法的代表與非矩陣式索引算法的代表。

更新一個文件時的性能情況如圖1所示。圖中可以看出，當有一個文件更新時，R2014與R2012 需要重新加密計算整個索引，而云端存儲的總文件數越大，重構時間越多。相比而言，由于本方案是增量式加密，因此更新一個文件只需要獨立加密該文件，更新獨立的可搜索結構，因此更新時間始終不變。此外，為了安全性 （構造索引需要用戶私鑰），該索引的重構需要在客戶端上進行，無法利用云服務器的并行處理能力。可見，增量式的方案更適用于當前經常更新文件的云存儲應用 （如個人網盤）。

對于錯判率而言，本方案的錯判率在r＝64時趨近于0（單文件的錯判率為3.3×10－19，因此1000個文件的整體錯判率 為3.3×10－16）；R2014錯判率始終大約為10%；R2012錯判率隨文件關鍵字數變化較大 （可近似為線性），當文件的關鍵字數大于40時，錯判率達到20%。可見，在實際應用中，由于本方案基于成熟的布隆過濾器為基礎，檢索的準確性得到了極大的提高。

圖1 更新一個文件時重建索引開銷

5 結束語

本文提出了一種安全的增量式多關鍵字可搜索加密方案，支持多關鍵字檢索的同時保護了用戶的查詢隱私，可以有效對抗統計分析攻擊。一方面，該方案通過犧牲存儲空間，換取支持隨時更新的增量式存儲，較同類算法更新效率大大提高，因此尤其適用于云存儲模式下用戶隨時更新文件的情況；另一方面，該方案以傳統成熟的布隆過濾器為基礎進行擴展，安全參數的設定使得錯判率幾乎為零，因此查詢的準確性較同類算法得到了更好的保障。

［1］SHEN Zhirong，XUE Wei，SHU Jiwu.Survey on the research and development of searchable encryption schemes［J］.Journal of Software，2014，25 （4）：880－895 （in Chinese）.［沈志榮，薛巍，舒繼武.可搜索加密機制研究與進展 ［J］.軟件學報，2014，25 （4）：880－895.］

［2］Li J，Wang Q，Wang C，et al.Fuzzy keyword search over encrypted data in cloud computing ［C］//INFOCOM.IEEE，2010：1－5.

［3］Chase M，Kamara S.Structured encryption and controlled disclosure［M］.Advances in Cryptology－ASIACRYPT.Springer Berlin Heidelberg，2010：577－594.

［4］Cash D，Jarecki S，Jutla C，et al.Highly－scalable searchable symmetric encryption with support for boolean queries ［M］.Advances in Cryptology.Springer Berlin Heidelberg，2013：353－373.

［5］Kamara S，Lauter K.Cryptographic Cloud Storage ［M］.Financial Cryptography and Data Security.Springer Berlin Heidelberg，2010：136－149.

［6］Park H A，Park J H，Lee D H.Pkis：Practical keyword index search on cloud datacenter［J］.Eurasip Journal on Wireless Communications and Networking，2011 （1）：1－16.

［7］Boneh D，Waters B.Conjunctive，subset，and range queries on encrypted data ［M］.Theory of Cryptography.Springer Berlin Heidelberg，2007：535－554.

［8］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，2014，25（1）：222－233.

［10］Kamara S，Papamanthou C，Roeder T.CS2：A searchable cryptographic cloud storage system ［R］.Microsoft Research，Tech ReportMsr－Tr－2011－58，2011.

［11］Zerr S，Demidova E，Olmedilla D，et al.Zerber：R－confidential indexing for distributed documents［C］//Proceedings of the 11th International Conference on Ex－tending Database Technology： Advances in Database Technology. ACM，2008：287－298.