張昌宏，陳 元，付 偉

（海軍工程大學(xué)信息安全系，武漢430033）

0 引言

隨著用戶數(shù)據(jù)的日益增長(zhǎng)，云存儲(chǔ)服務(wù)［1-2］得以發(fā)展并逐漸成為一項(xiàng)熱門的數(shù)據(jù)存儲(chǔ)技術(shù)。服務(wù)商通過(guò)整合網(wǎng)絡(luò)中的存儲(chǔ)資源，向用戶提供專門的數(shù)據(jù)存儲(chǔ)及訪問(wèn)服務(wù)。然而在云存儲(chǔ)服務(wù)提供商（CSP，cloud storage provider）［3］信任受限的條件下，用戶隱私敏感數(shù)據(jù)的安全性保護(hù)成為目前的研究熱點(diǎn)之一。

密文檢索技術(shù)［4-13］可將用戶的隱私敏感數(shù)據(jù)加密后再上傳至CSP，并支持授權(quán)用戶的檢索請(qǐng)求，在保證數(shù)據(jù)機(jī)密性的前提下，保持了可檢索性。同時(shí)，由于檢索操作可以直接在密文上進(jìn)行，而不用將CSP中所有的密文數(shù)據(jù)下載、解密之后再檢索，因此，可以極大地提高用戶和服務(wù)器的工作效率，并有效降低網(wǎng)絡(luò)消耗帶寬。

在傳統(tǒng)的明文檢索技術(shù)中，由于檢索用戶掌握的數(shù)據(jù)與真實(shí)數(shù)據(jù)之間存在著誤差，僅僅依靠精確匹配無(wú)法完成相應(yīng)的檢索功能，因此，支持模糊匹配是十分必要的。然而，在密文檢索中，即使明文數(shù)據(jù)之間存在較小的誤差，加密后密文之間的誤差會(huì)變得很大，因此，密文模糊檢索功能具有很大的挑戰(zhàn)性［13］。

本文通過(guò)分析傳統(tǒng)的明文模糊檢索技術(shù)，結(jié)合密文檢索的特點(diǎn)及要求，提出了一種安全且高效的密文模糊檢索方案。方案以關(guān)鍵詞的頻率為權(quán)值并引入Huffman樹形結(jié)構(gòu)及其編碼的思想構(gòu)建密文關(guān)鍵詞索引結(jié)構(gòu)，采用Bloom-Filter存儲(chǔ)關(guān)鍵詞的模糊集合，最后通過(guò)改進(jìn)的TF-IDF規(guī)則對(duì)檢索出的密文文檔進(jìn)行評(píng)分排序，以返回最符合用戶需求的Top-k結(jié)果。

1 相關(guān)研究

根據(jù)檢索匹配精度的不同，可以將密文檢索技術(shù)分為精確密文檢索［4-8］和模糊密文檢索［9-13］：

1）精確密文檢索技術(shù)。Song等人［4］最早提出基于對(duì)稱加密體制和偽隨機(jī)函數(shù)的可搜索加密方案，雖然證明了方案的安全性，但是由于性能與密文的長(zhǎng)度成正比，效率較低；Boneh等人［5］提出基于雙線性對(duì)和Hash函數(shù)的非對(duì)稱加密檢索方案，實(shí)現(xiàn)了明文的機(jī)密性和密文的可檢索性；Hwang等人［6］提出基于連接關(guān)鍵詞的多用戶非對(duì)稱密文檢索方案，方案所需的存儲(chǔ)空間較大；Wang等人［7］提出連接關(guān)鍵詞字域可變的密文檢索方案；Cao等人［8］提出支持多關(guān)鍵詞排序的隱私保護(hù)檢索方案，但在排序算法中并未考慮到關(guān)鍵詞頻率。以上方案均只適用于關(guān)鍵詞的精確匹配，不適用于模糊檢索。

2）模糊密文檢索技術(shù)。相比于精確密文檢索，模糊密文檢索的難度要更高。Park等人［9］提出基于橢圓曲線和Hamming距離的密文模糊檢索方案，安全性較高，但是效率較低；Li等人［10］提出基于通配符和編輯距離的模糊匹配模式，效率較低；Liu等人［11］提出基于字典的模糊集構(gòu)造檢索方案，將索引長(zhǎng)度降到最低，且效率較高；Wang等人［12］在文獻(xiàn)［10］的基礎(chǔ)上構(gòu)建了語(yǔ)義樹索引，提高了效率，但抵御統(tǒng)計(jì)分析攻擊能力不足。

Li等人［13］通過(guò)TF-IDF規(guī)則對(duì)關(guān)鍵詞進(jìn)行評(píng)分，并以此為權(quán)值構(gòu)建Huffman索引樹，基于通配符和編輯距離建立關(guān)鍵詞模糊集，在保證安全性的前提下，提高了密文模糊檢索的效率，但是方案不支持結(jié)果集的排序。

2 模型描述及設(shè)計(jì)目標(biāo)

本節(jié)主要對(duì)系統(tǒng)模型、敵手模型進(jìn)行描述，并對(duì)其提出相應(yīng)的設(shè)計(jì)目標(biāo)。

2.1 系統(tǒng)模型

圖1 密文模糊檢索模型

如圖1所示，密文模糊檢索模型主要由4個(gè)角色組成：數(shù)據(jù)擁有者（DO，Data Owner）、可信第三方（TTP，Trusted Third Party）、云存儲(chǔ)服務(wù)提供商（CSP，Cloud Storage Provider）和數(shù)據(jù)檢索者（DS，Data Searcher）。

1）DO：數(shù)據(jù)擁有者將隱私敏感數(shù)據(jù)及其關(guān)鍵詞發(fā)送給可信第三方，同時(shí)可以提出密文檢索請(qǐng)求；

2）TTP：可信第三方加密明文數(shù)據(jù)并根據(jù)DO提供的關(guān)鍵詞建立模糊檢索集及其索引，將加密后的索引及密文上傳至CSP；當(dāng)DO和DS提供檢索請(qǐng)求時(shí)，TTP會(huì)根據(jù)用戶提供的關(guān)鍵詞生成檢索陷門并發(fā)送給CSP；

3）CSP：向用戶提供數(shù)據(jù)存儲(chǔ)、下載及檢索服務(wù)；

4）DS：數(shù)據(jù)檢索者經(jīng)DO授權(quán)后可以提出密文檢索請(qǐng)求并獲取相應(yīng)的數(shù)據(jù)信息。

2.2 敵手模型描述

本文將CSP視為“忠實(shí)但好奇”的半可信敵手模型。一方面，CSP能夠忠實(shí)履行與用戶之間的服務(wù)等級(jí)協(xié)定（SLA，Service Level Agreement）［14］，向其提供穩(wěn)定的數(shù)據(jù)上傳、下載及檢索等服務(wù)；另一方面，CSP出于好奇會(huì)對(duì)用戶的訪問(wèn)行為和記錄進(jìn)行分析，因此，用戶隱私敏感信息存在著一定的安全性威脅。

2.3 設(shè)計(jì)目標(biāo)

模型的設(shè)計(jì)目標(biāo)主要有以下3個(gè)方面：

1）安全。保證用戶隱私敏感數(shù)據(jù)的安全性，包括明文、關(guān)鍵詞索引及陷門和檢索過(guò)程的安全性；

2）高效。符合綠色計(jì)算的要求，既要減小存儲(chǔ)空間，又要保證密文檢索的效率；這里所說(shuō)的存儲(chǔ)空間主要是指關(guān)鍵詞索引所占的存儲(chǔ)空間；

3）可靠。系統(tǒng)能夠給用戶提供可靠的數(shù)據(jù)存儲(chǔ)和密文檢索服務(wù)。

3 安全密文模糊檢索方案

通過(guò)分析傳統(tǒng)的明文模糊檢索技術(shù)，并結(jié)合密文檢索的特點(diǎn)及要求，本節(jié)提出了一種安全且高效的密文模糊檢索方案。為提高檢索效率，方案以關(guān)鍵詞的頻率為權(quán)值構(gòu)建Huffman樹并將其作為密文關(guān)鍵詞索引；通過(guò)Bloom-Filter存儲(chǔ)關(guān)鍵詞的模糊集合，既能夠減少存儲(chǔ)空間又可以實(shí)現(xiàn)快速匹配；最后通過(guò)改進(jìn)的TF-IDF規(guī)則對(duì)檢索出的密文文檔進(jìn)行評(píng)分排序以返回最符合用戶需求的Top-K結(jié)果。

3.1 預(yù)備知識(shí)

3.1.1 Huffman樹及其編碼

Huffman樹又被稱為最優(yōu)二叉樹，是一種帶權(quán)路徑長(zhǎng)度最小的樹形結(jié)構(gòu)。由于權(quán)值越大的節(jié)點(diǎn)深度越小，訪問(wèn)路徑也越短，因此，將其應(yīng)用于索引結(jié)構(gòu)構(gòu)建方案中會(huì)極大地提高檢索效率。以權(quán)值分別為1、2、3、4、5的節(jié)點(diǎn)為例，Huffman樹的構(gòu)造過(guò)程如下：

1）將這5個(gè)權(quán)值節(jié)點(diǎn)作為5棵只有根節(jié)點(diǎn)的二叉樹，左右子樹均為空；

2）選取權(quán)值最小的兩棵二叉樹即1、2節(jié)點(diǎn)，將其作為左右子樹構(gòu)造成一棵新二叉樹，其權(quán)值為左右子樹節(jié)點(diǎn)的權(quán)值之和即3；

3）刪除已用的1、2節(jié)點(diǎn)，并將新構(gòu)造的3節(jié)點(diǎn)作為一棵新的二叉樹；

4）重復(fù)2）和3），直至用完所有的權(quán)值節(jié)點(diǎn)，最終構(gòu)造成Huffman樹。

對(duì)Huffman樹進(jìn)行二進(jìn)制編碼時(shí)通常用0表示左分支、1表示右分支，則圖2中1～5節(jié)點(diǎn)的編碼分別為010、011、00、10、11。

3.1.2 Bloom-Filter（布隆過(guò)濾器）

圖2 Huffman樹形結(jié)構(gòu)

圖3 Bloom-Filter存儲(chǔ)及檢索示意圖

如圖3所示，根據(jù)判定原則，y1極有可能屬于集合S，但也存在誤判的情況；y2不屬于S；雖然y3對(duì)應(yīng)的值全為1，但是位置不對(duì)，因此，也不屬于S，而是假陽(yáng)性元素［13，15］。

3.1.3 TF-IDF規(guī)則

TF-IDF規(guī)則是一種基于權(quán)值的評(píng)分排序機(jī)制。在整個(gè)文檔集中，關(guān)鍵詞與指定文檔的關(guān)聯(lián)程度與該關(guān)鍵詞在指定文檔中的頻率成正比，與該關(guān)鍵詞檢索命令中的文檔數(shù)成反比。針對(duì)關(guān)鍵詞wi，文檔Fi的評(píng)分為：

其中，TF指關(guān)鍵詞wi在指定文檔Fi中的詞頻；指文檔Fi在整個(gè)文檔集中的頻率，N表示文檔總數(shù)，DF表示關(guān)鍵詞wi命中的文檔數(shù)。

3.2 基于Huffman樹和Bloom-Filter的安全密文模糊檢索方案

方案主要分為關(guān)鍵詞模糊集生成、Huffman樹形索引結(jié)構(gòu)構(gòu)建、陷門生成及檢索和密文文檔排序4個(gè)部分。

3.2.1 關(guān)鍵詞模糊集生成

對(duì)字符串的操作通常有字符刪除、插入和替換3種，本文采用基于通配符和編輯距離的關(guān)鍵詞模糊集生成方法。其中，通配符“*”表示對(duì)關(guān)鍵詞任一位置上的操作，編輯距離D（w，w'）表示由關(guān)鍵詞w生成模糊關(guān)鍵詞w'的最小字符操作次數(shù)，Sw，D表示對(duì)關(guān)鍵詞w至多操作D次得到的關(guān)鍵詞模糊集合。

3.2.2 Huffman樹形索引結(jié)構(gòu)構(gòu)建

方案以關(guān)鍵詞頻率為權(quán)值構(gòu)建Huffman樹形索引結(jié)構(gòu)，并通過(guò)高效的Bloom-Filter實(shí)現(xiàn)模糊集的存儲(chǔ)和檢索。

2）TTP將這n個(gè)帶權(quán)節(jié)點(diǎn)構(gòu)造成一棵Huffman樹；

3）如圖4所示，根據(jù)關(guān)鍵詞模糊集編輯距離的不同，將Sw，D分為相應(yīng)的集合，如當(dāng)D=3時(shí)，Sw，3分別為Sw_1、Sw_2、Sw_3。分別對(duì)集合進(jìn)行加密，然后映射到布隆過(guò)濾器BFw_1、BFw_2、BFw_3中，并將過(guò)濾器作為索引樹的葉子節(jié)點(diǎn)。

圖4 索引樹的葉子節(jié)點(diǎn)

4）如圖5所示，TTP構(gòu)建Huffman樹形索引結(jié)構(gòu)，并將其和加密后的密文文檔上傳至CSP。其中，1-3節(jié)點(diǎn)存儲(chǔ)加密后的關(guān)鍵詞，Bloom-Filter存儲(chǔ)加密后的模糊關(guān)鍵詞，兩者均指向密文文檔。

圖5 Huffman樹形索引結(jié)構(gòu)

3.2.3 陷門生成及檢索

3.2.4 密文文檔排序

為給用戶提供最符合需求的Top-k個(gè)結(jié)果，本文采用改進(jìn)的TF-IDF規(guī)則給檢索出的密文文檔評(píng)分排序。文檔排序不僅需要考慮關(guān)鍵詞與指定文檔的關(guān)聯(lián)程度，更要考慮與模糊關(guān)鍵詞的編輯距離，而且后者所占的權(quán)重比較大。因此，改進(jìn)后的TF-IDF規(guī)則為：

4 方案分析

本節(jié)主要就方案的安全性、復(fù)雜度以及Bloom-Filter的誤判率和假陽(yáng)性進(jìn)行分析，并通過(guò)實(shí)驗(yàn)測(cè)試進(jìn)行性能對(duì)比分析。

4.1 安全性分析

方案安全性主要考慮用戶隱私敏感信息、索引結(jié)構(gòu)以及檢索過(guò)程的安全性。

4.1.1 用戶信息及索引安全在本文方案中，用戶隱私敏感信息和關(guān)鍵詞都是采用經(jīng)典的密碼學(xué)對(duì)稱算法——AES算法來(lái)實(shí)現(xiàn)加解密，因此，在保證密鑰長(zhǎng)度合適的前提下，方案是安全可靠的。關(guān)鍵詞模糊集在加密之后通過(guò)Bloom-Filter來(lái)存儲(chǔ)，而過(guò)濾器通過(guò)一組獨(dú)立同分布的Hash函數(shù)進(jìn)行映射，在理論上具有不可逆性，因此，攻擊者無(wú)法對(duì)其進(jìn)行破譯。

4.1.2 檢索安全

4.2 復(fù)雜度分析

4.3 Bloom-Filter誤判率及假陽(yáng)性分析

在Bloom-Filter的數(shù)據(jù)存儲(chǔ)及檢索中，存在著誤判和假陽(yáng)性的情況。

4.3.1 Bloom-Filter誤判率分析

由于Hash函數(shù)不是一一映射，可能存在多對(duì)一的關(guān)系，因此，當(dāng)Bloom-Filter的某一位設(shè)置為1后，其值不再改變，再次判定時(shí)可能存在誤判的情況。只有設(shè)置較長(zhǎng)的Bloom-Filter向量才能減少這種碰撞，使誤判率較低，但是相應(yīng)的存儲(chǔ)空間也會(huì)增大。

4.3.2 Bloom-Filter假陽(yáng)性分析

4.4 實(shí)驗(yàn)測(cè)試及性能分析

為對(duì)本文方案進(jìn)行性能分析，選取1 000篇IEEE數(shù)據(jù)庫(kù)中計(jì)算機(jī)專業(yè)相關(guān)的英文論文作為測(cè)試文檔，大小約為700 MB。選取50個(gè)高頻且重復(fù)前綴較少的關(guān)鍵詞，平均長(zhǎng)度為7.5，最大編輯距離設(shè)定為3。實(shí)驗(yàn)平臺(tái)配置在一臺(tái)處理器為Intel（R）Core（TM）i5-2450M 2.50 GHz，RAM 4 GB的PC機(jī)上。本節(jié)主要在索引構(gòu)建時(shí)間、索引規(guī)模、模糊檢索效率方面與文獻(xiàn)［13］方案進(jìn)行性能對(duì)比分析。

4.4.1 索引構(gòu)建時(shí)間

圖6 索引構(gòu)建時(shí)間

如圖6所示，在本文方案和文獻(xiàn)［13］方案中，索引構(gòu)建時(shí)間都隨著測(cè)試文檔數(shù)量的增加呈線性增加；由于本文方案以關(guān)鍵詞頻率為權(quán)值構(gòu)建索引樹，而文獻(xiàn)［13］方案基于TFIDF規(guī)則對(duì)關(guān)鍵詞進(jìn)行評(píng)分，并以此為權(quán)值構(gòu)建索引樹，因此，與文獻(xiàn)［13］方案相比，本文方案的索引構(gòu)建時(shí)間較少。

4.4.2索引規(guī)模

如下頁(yè)圖7所示，在本文的測(cè)試環(huán)境下，方案的索引規(guī)模為MB級(jí)，符合云存儲(chǔ)環(huán)境的要求。由于本文方案與文獻(xiàn)［13］方案都以關(guān)鍵詞信息構(gòu)建Huffman索引樹，其索引規(guī)模相當(dāng)。

4.4.3模糊檢索效率

由于本文方案與文獻(xiàn)［13］方案都是對(duì)索引樹進(jìn)行遍歷查詢來(lái)實(shí)現(xiàn)模糊檢索，因此，基于關(guān)鍵詞信息的索引樹生成之后，測(cè)試文檔數(shù)量對(duì)模糊檢索效率的影響會(huì)比較小，而檢索請(qǐng)求數(shù)量對(duì)效率會(huì)產(chǎn)生線性的影響；由于方案對(duì)檢索請(qǐng)求的處理方式不同，文獻(xiàn)［13］方案中增加了DS的檢索關(guān)鍵詞加密和TTP的解密過(guò)程，因此，本文方案的模糊檢索效率提高了約10%。

圖7 索引規(guī)模

圖8 模糊檢索效率

5 結(jié)論

隨著軍事數(shù)據(jù)獲取方法的不斷發(fā)展，數(shù)據(jù)總量日益增長(zhǎng)，這對(duì)涉密信息的安全性和檢索高效性提出了更高的要求［16］。本文通過(guò)分析傳統(tǒng)的明文模糊檢索技術(shù)，并結(jié)合密文檢索的特點(diǎn)及要求，提出了一種安全且高效的密文模糊檢索方案。方案以關(guān)鍵詞的頻率為權(quán)值構(gòu)建Huffman樹形密文關(guān)鍵詞索引結(jié)構(gòu)，并通過(guò)Bloom-Filter存儲(chǔ)關(guān)鍵詞的模糊集合，最后通過(guò)改進(jìn)的TF-IDF規(guī)則對(duì)檢索出的密文文檔進(jìn)行評(píng)分排序，以返回最符合用戶需求的Top-k結(jié)果。本文方案主要滿足單用戶的需求，對(duì)于多用戶需求的密文模糊檢索，將是下一步的主要研究重點(diǎn)。