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

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

0 引 言

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

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

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

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

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

2 隨機(jī)布隆過濾器

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

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

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

2.2 隨機(jī)布隆過濾器

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

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

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

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

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

2.3 安全性證明

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 性能分析

為了驗(yàn)證該算法的運(yùn)行效率與實(shí)用性，我們將所有算法用C＋＋編碼，并編制模擬器模擬輸入文件數(shù)據(jù)。所有代碼在一臺(tái)具有2.6GHz CPU 和2GB內(nèi)存的雙核PC機(jī)上運(yùn)行。在程序中，π設(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)鍵字可搜索加密算法作比較，這里選取文獻(xiàn) ［8］（R2014）與文獻(xiàn) ［9］（R2012）提出的方案，分別作為矩陣式索引算法的代表與非矩陣式索引算法的代表。

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

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

圖1 更新一個(gè)文件時(shí)重建索引開銷

5 結(jié)束語(yǔ)

本文提出了一種安全的增量式多關(guān)鍵字可搜索加密方案，支持多關(guān)鍵字檢索的同時(shí)保護(hù)了用戶的查詢隱私，可以有效對(duì)抗統(tǒng)計(jì)分析攻擊。一方面，該方案通過犧牲存儲(chǔ)空間，換取支持隨時(shí)更新的增量式存儲(chǔ)，較同類算法更新效率大大提高，因此尤其適用于云存儲(chǔ)模式下用戶隨時(shí)更新文件的情況；另一方面，該方案以傳統(tǒng)成熟的布隆過濾器為基礎(chǔ)進(jìn)行擴(kuò)展，安全參數(shù)的設(shè)定使得錯(cuò)判率幾乎為零，因此查詢的準(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ī)制研究與進(jìn)展 ［J］.軟件學(xué)報(bào)，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.