基于Bloom Filter的密文檢索改進方案

錢圣福 朱王小江

基于Bloom Filter的密文檢索改進方案

錢圣福 朱王小江

基于Bloom Filter傳統的密文檢索存在較大的誤檢率的問題，這嚴重影響了密文檢索結果的準確性，本文中，通過引入唯一向量，對Bloom Filter的基礎數據結構進行了改造，使其在不明顯增加索引大小的前提下，改善誤檢率。通過在創建索引和構造陷門的過程中引入非對稱加密機制，使得新算法能夠有效抵抗相似性統計分析攻擊，并且不會泄露任何用戶信息和檔案明文信息。通過一系列實驗對改進系統進行了安全性、效率等方面的對比，該系統在保證高檢索效率的同時，能夠達到較高的安全等級。

研究內容

密文檢索技術的核心在于保證數據安全性的前提下，對密文實現快速檢索，即實現密文對密文的檢索，涉及的核心技術主要包括索引的創建、更新、刪除、檢索，索引和文檔的安全性以及密鑰管理。1992年，Ostrovsky最早提出了這一問題的解決方案，1996年Goldreich和Ostrovsky又對這一方案進行了改進。2000年，此科研團隊又在原方案的基礎上提出了一種新的對稱加密可搜索方案SSKE。Dan Boneh提出了一種基于公鑰密碼系統的密文檢索機制（PEKS，Public Encryption with Keyword Search）。Yan－ Cheng Chang和Michael Mitzenmacher等人提出了一種基于安全索引的密文全文檢索方案，實現方法是在文檔加密前提取關鍵詞建立相應的安全索引，搜索時利用陷門對密文索引進行檢索查詢。這種方案能夠實現在不對存儲文檔進行解密的前提下對密文進行檢索。Dawn Xiao Song等人提出了一種實現密文對密文檢索的查詢方案，主要方法是利用序列加密算法對文檔進行處理，檢索時只需要將關鍵詞于密文文本中的加密詞語進行匹配即可實現檢索。Eu－Jin Goh等人提出了一種能夠一定程度上隱藏用戶訪問模式（Access Patterns）的對稱可搜索加密算法，此方案利用Bloom過濾器來構建密文索引，索引與加密文檔在語義上是完全無關的，并且檢索算法時間復雜度為O（1）。另外國內也在此領域做了不少研究工作。

本文主要工作如下：1）高效的安全索引結構。基于為隨機函數和布隆過濾器的密文檢索模型，針對理論架構和原方案較高的差錯率和較低的安全性進行改進，在保證安全性和檢索效率的同時，實現了檢索結果的零差錯反饋。2）密文檢索原型系統的設計與實現。設計并且實現了一個基于Bloom Filter安全索引的密文全文檢索的原型系統，并對該系統的重要組成部分給出了結構框圖。

基于Bloom Filter的密文檢索改進方案

索引構造過程改進

通過對GOH等人提出的基于BloomFilter的密文全文檢索方案的分析，對原方案的改進，引入一個加密向量，該向量的第i位置1，其余位置0，每一個加密向量對應文檔Di中的單詞Wi。改進后的索引構建流程如圖1所示。

陷門構造改進

傳統方案采取直接對關鍵詞進行散列化的方式生成關鍵詞陷門，關鍵詞W的陷門Tw直接使用密鑰Kpriv與明文W進行散列化后生成，這樣會使得不同文章中相同關鍵詞所生成的陷門完全相等，這樣就暴露了用戶的訪問模式（Access Patterns），即兩次搜索的關鍵字相同，這樣就使得索引面臨著相似性統計分析攻擊的危險，針對這一點，對陷門生成過程進行了改進。在S－INX中，陷門不僅僅跟密鑰和關鍵詞相關，還引入了關鍵字在對應文檔中的相對位置和頻率信息，改進的關鍵詞陷門生成過程如圖2所示。

如圖所示，S－INX的陷門引入了一個表征單詞唯一性的特征向量Zj。改造后的陷門實現了對用戶模式的隱藏，這時候屬于不同文檔的相同單詞所構造的陷門就不可能相同。由于索引每個文檔的一一對應，因此在檢索時需要對每一個索引進行查詢，后面會有詳盡的性能分析。

檢索過程的改進

通過對原方案的分析研究，當接到查詢關鍵字W的時候，首先生成陷門，然后將其散列化后與Bloom Filter中的相應數據位進行比對，如果所有位置上的值都是“1”，則表示該關鍵字在索引中，如果有一個位置是“0”，就表示該關鍵字不在索引中。這種算法使得索引容易遭受到相似度分析。

圖1 S－INX的索引構建方案

當查詢請求為關鍵字y1時，首先按照改進陷門構建方案生成對應陷門，接著對y1生成特征向量v1，然后根據對y1生成的Bloom Filter位置值，對相應位置的特征向量鏈表做∩操作，如果結果為v1，則說明y1在索引中，也即關鍵詞w在文章D中，結果為空則表明該索引不含有關鍵詞w。當查詢請求為關鍵字y1時，首先按照改進陷門構建方案生成對應陷門，接著對y1生成特征向量v1，然后根據對y1生成的Bloom Filter位置值，對相應位置的特征向量鏈表做∩操作，如果結果為v1，則說明y1在索引中，也即關鍵詞w在文章D中，結果為空則表明該索引不含有關鍵詞w。

高效的安全索引結構設計與實現

具有高安全性和良好檢索性能的索引結構是密文檢索系統的核心部分。為了滿足這樣的要求，實現索引與文檔加密方式按需動態配置，此原型系統將索引和文檔的加密過程分開、獨立進行，索引數據和文檔的安全性完全取決于所選擇的加密算法的安全性。索引結構本身的安全性又對索引中存儲的數據的安全性至關重要，因而索引的安全性在密文檢索模型整體安全性上位置突出，需要加強保護。

S－INX安全索引結構的設計

S－INX索引文件的主要結構如圖3。本系統的索引文件主要由4個部分組成：con文件，in文件，doc文件，seg文件。這四個文件包含了與索引處理有關的所有必要信息。其中，con文件存儲的是整個索引文件的核心部分，包含了與創建索引有關的所有關鍵信息，包括用于偽隨機函數的安全參數，它是體現所生成的哈希值散列性的關鍵，對于減少過濾器中鏈表長度有直接作用，還包括索引所含文檔數，doc文件長度，in文件長度，其中的文檔seg號，將文檔和對應索引一一對應起來，是能夠進行正確索引的關鍵，對其他三個文件的長度現在也在相應參數中一一體現；seg文件負責存放被索引后的文件的內容，包含了文檔所有域的內容。由于索引文件大小的限制，在應用中會對seg文件進行分塊，此文件所包含的域權值、域是否標識化是影響索引準確率的關鍵因素，可以根據實際需要動態調整。Doc文件負責文檔內容的存儲，包括文檔的唯一識別ID，這是索引與文檔對應以及返回檢索結果的關鍵參數，文檔所包含的域數也指明了文檔能夠被分割的最大域數的限制，因為過多的域數會導致檢索效率的直線下降。in文件存儲了Bloom Filter的相關數據結構，是執行構建索引和檢索匹配操作的關鍵，對應各個文檔所關聯的Bloom Filter內容。單個Bloom Filter數據結構是一個存儲鏈表的數組。當接收到一個查詢請求時，根據con文件中的BF在in文件中的相對偏移量找到對應的Bloom Filter數組，執行∩操作。

S－INX結構實現

圖2 S－INX的陷門構建過程

圖3 S－INX索引文件結構

S－INX結構的實現包括三個接口和一個實現類，包括inxINT，fileReadINT，anaINT，以及inxIMPL，第一個接口完成索引上傳和更新等與索引有關的功能，第二個結構實現對文檔的讀操作，第三個結構實現按照分析規則對文檔內容進行提取，它有幾個實現類，以針對不同的文件格式，包括docxIMPL，csvIMPL，txtIMPL，pdfIMPL，這里僅列出主要文件的實現類，可以根據實際需要添加其他的文件讀取實現類。當用戶將需要建立安全索引的文檔進行上傳操作時，fileReadINT接口負責提取文檔信息，包括文檔ID，文檔內容等。然后調用normalize（）方法對所有格式文檔進行統一化處理，并生成統一格式的對象Document。接著inxINT調用其中的Index（）方法對生成的Document對象進行索引生成。在進行索引創建的時候，需要調用anaINT對文檔進行分詞，這里的采用Lucene的文檔分析器執行相應操作，分析規則和分析語言可以根據實際需要動態調整，其中的analysis（）主要負責分詞工作。

系統實現及分析

系統架構

圖4 密文檢索系統架構

整個系統共分為四個組成部分：1）文檔分析；2）構建安全索引；3）文檔加密；4）檢索查詢。明文文檔經過結構化處理以及經解釋器分詞以后，然后使用用戶的密鑰對文檔進行加密并將加密后的文檔上傳至云服務器；分詞完成后，對關鍵詞進行過濾，去掉重復的單詞以及停用詞，使用剩下的不重復詞語生成陷門并構建索引，將陷門上傳至服務器；檢索時，用戶先用自己的密鑰對關鍵詞進行加密生成陷門以后，將陷門傳送至服務器以便索引，并遵循訪問控制等控制機制的限制獲取密文文檔存儲位置信息。這其中為整個系統安全保駕護航的就是密鑰管理模塊。該模塊提供文檔加密、索引建立、檢索查詢過程的密鑰生成、銷毀及管理服務。

系統IO性能測試

主要測試對文檔長度對系統輸入輸出能力的影響，實驗樣本為不同字節長度的文檔，為了反應文件格式對IO性能的影響，選取了三種不同的文檔類型，包括DOCx格式的文檔，PDF格式的文檔，TXT格式的文檔以及RTF格式的文檔，文檔長度選取了七個值，1KB、32KB、128KB、512KB、1MB、8MB、32MB，這樣的取值是文檔大小形成了類均勻分布，能夠很好的反應文檔長度與系統輸入、輸出性能的關系。測試的主要指標有文檔分析所耗時間、構建索引所耗時間、加密文檔所耗時間、解密文檔所耗時間，并給出了對實驗結果的分析。DOCx文件、PDF文件和RTF三種格式的文件在各項參數的表現都比較平均，也就是說，這三種文件格式對系統輸入、輸出性能的影響不是很明顯，相比而言RTF文件格式對系統性能影響最小，系統的所耗時間隨著文件字節長度的增加而增加。從加密文件耗時和解密文件耗時來看，RTF格式文件由于其文件格式簡單，頭文件信息較少，因而在加、解密所耗時間這一指標上表現最好，TXT文件次之，其次是PDF文件，而DOCx文件由于其除去文檔內容以外的控制信息較多，因而其文件格式對加解密這一項性能指標影響較大。由于文件分析采用的Lucene中文分詞器CnTokenizer采用二元覆蓋方式實現中文分詞，因而TXT這種格式性不強的文件在文件分析階段所耗的時間最多。綜合所有性能指標來看，RTF文件對系統的輸入、輸出性能影響最小。

安全索引檢索誤檢率性能測試

針對原方案Z－IDX高誤檢率的問題，本實驗旨在對比測試傳統倒排索引、Z－IDX、S－INX三種方案檢索返回結果的正確率，本測試選取了10個常用漢語詞語，文件集合為包含了10000個中文文檔的大型文件集，格式均為TXT，主要測試結果為輸入相應關鍵詞返回的正確結果的情況，具體實驗數據如表1所示。

表1 不同索引結構誤檢率性能測試

實驗結果表明，本文所改進的方案S－INX已經能夠實現檢索結果零誤檢。

結語

本文著眼于當前云存儲技術在發展中遇到的一系列亟待解決的安全問題，設計并實現了一個基于布隆過濾器的安全索引密文全文檢索原型系統，改進了基于布隆過濾器的安全索引構建方案，設計并實現了基于安全索引的密文全文檢索原型系統，對改進模型的性能進行了實驗分析。結果表明，改進方案S－INX在檢索大型文檔集合時效率和準確率都在對比方案中獲得較大提升。

錢圣福1朱王小江2

1.北京市第一六一中學；2.北京電子科技學院

錢圣福，男，北京市第一六一中學；朱王小江，男，碩士，北京電子科技學院。

10.3969/j.issn.1001-8972.2016.09.018