增量式多關(guān)鍵字可搜索加密算法

彭凝多，羅光春，秦 科，李春虎，馬致遠(yuǎn)

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

0 引 言

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

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

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

1 相關(guān)符號與數(shù)學(xué)基礎(chǔ)

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

2 隨機布隆過濾器

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

2.1 傳統(tǒng)布隆過濾器

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

2.2 隨機布隆過濾器

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

定義1 隨機布隆過濾器為3個多項式時間算法的集合：①B←Build（S）：構(gòu)造過濾器。輸入集合S＝ ｛s1，…，sn｝。輸出具有l(wèi)比特的比特串B；②A←Trans（X）：構(gòu)造過濾器輸入數(shù)據(jù)。輸入需測試的數(shù)據(jù)X＝ ｛x1，…，xm｝。輸出轉(zhuǎn)換結(jié)果A。在同樣輸入條件下，輸出具有隨機性；③b←Test（A，B）：測試數(shù)據(jù)。輸入測試數(shù)據(jù)X 對應(yīng)的轉(zhuǎn)換結(jié)果A，目標(biāo)集合S 對應(yīng)的比特串B。如果X∈S 則輸出b＝1，否則輸出b＝0。

過濾器的具體構(gòu)造在算法1中給出。

若以傳統(tǒng)的最優(yōu)解為標(biāo)準(zhǔn)，對于每一個元素而言，錯判率最高為1/2r（該值在m＝v時取得），最低為1/2rv（該值在m＝1時取得）。因此，對于整體而言，錯判率最高為1－ （1－1/2r）v（該值在m＝v 時取得）。最高錯判率作為一個參數(shù)選擇的重要指標(biāo)，根據(jù)應(yīng)用的需求進行設(shè)定。

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

2.3 安全性證明

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

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

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

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

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

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

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

3 增量式多關(guān)鍵字可搜索加密算法

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

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

其中，文檔唯一標(biāo)識符id（d）可由服務(wù)器提供。接下來討論該方案的具體構(gòu)造。

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

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

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

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

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

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

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

4 性能分析

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

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

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

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

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

5 結(jié)束語

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

［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］.軟件學(xué)報，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.