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

錢圣福 朱王小江

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

錢圣福 朱王小江

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

研究內(nèi)容

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

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

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

索引構造過程改進

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

陷門構造改進

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

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

檢索過程的改進

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

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

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

高效的安全索引結構設計與實現(xiàn)

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

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

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

S－INX結構實現(xiàn)

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

圖3 S－INX索引文件結構

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

系統(tǒng)實現(xiàn)及分析

系統(tǒng)架構

圖4 密文檢索系統(tǒng)架構

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

系統(tǒng)IO性能測試

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

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

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

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

實驗結果表明，本文所改進的方案S－INX已經(jīng)能夠?qū)崿F(xiàn)檢索結果零誤檢。

結語

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

錢圣福1朱王小江2

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

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

10.3969/j.issn.1001-8972.2016.09.018