一種可抵抗統計攻擊的安全索引

惠 榛 馮登國 張 敏 洪 澄

1(中國科學院軟件研究所可信計算與信息保證實驗室 北京 1000190)2(中國科學院大學 北京 100049)3 (計算機科學國家重點實驗室(中國科學院軟件研究所) 北京 100190) (huizhen@tca.iscas.ac.cn)

一種可抵抗統計攻擊的安全索引

惠 榛1,2馮登國1,3張 敏1洪 澄1

1(中國科學院軟件研究所可信計算與信息保證實驗室 北京 1000190)2(中國科學院大學 北京 100049)3(計算機科學國家重點實驗室(中國科學院軟件研究所) 北京 100190) (huizhen@tca.iscas.ac.cn)

現有的大部分可檢索加密方案建立的安全索引面臨著統計攻擊的威脅.為了抵抗統計攻擊，部分方案設計出關鍵詞文檔一一對應的陷門，以檢索時多次的陷門計算為代價保證安全性，但是這樣又導致檢索速度過于慢而無法接受.為此，研究了針對密文的安全檢索方案，在克服已有方案缺點的同時保證對于統計攻擊的安全性.該方案使用Bloom過濾器為文檔的關鍵詞構造索引.為了確保檢索效率，對于相同的關鍵詞構造唯一對應的陷門.通過增加偽造的文檔索引，并且在索引中進行插值來確保每個關鍵詞在文檔集合中出現的次數相似，從而達到語義安全并且能夠抵抗統計攻擊.在實現中，對索引進行倒排進一步提高檢索效率.證明了本方案的安全性，且采用實驗驗證了其有效性和高效性.

可檢索加密；統計泄露；倒排索引；Bloom過濾器；訪問模式

大數據時代的到來使得企業內部的數據管理面臨新的挑戰.面對爆炸式增長的數據，傳統的存儲和管理方法變得困難和低效.越來越多的新生業務選擇將他們的數據外包到數據服務提供商，減少存儲和管理開銷.但是這也給用戶帶來了新的安全和隱私保護問題——外包的數據中可能包含企業的財務狀況、人員記錄等等敏感信息.為了保護信息，特別是敏感信息的安全，常用的方式是將數據進行加密之后再外包存儲.

數據加密存儲能夠有效地保護數據安全，不過這會使對數據進行選擇性的查詢變得困難.如何對密文進行有效且安全的檢索，即可檢索加密(search-able encryption, SE)成為了研究的熱點問題.可檢索加密允許用戶將密文存儲到半可信不可信的服務器，并且提供關鍵詞匹配檢索，同時能夠滿足用戶的安全和隱私需求[1].針對這方面已有大量的研究工作，文獻[2-9]在安全性、高效性和可用性等不同立足點上給出了各自的解決方案.雖然解決方案眾多，但是他們的基本框架是類似的：用戶將文檔加密后存儲在服務器.同時，為了實現對于加密文檔的檢索，用戶需要構造一個能夠存儲在服務器的安全索引結構用來查找到包含指定關鍵詞的文檔.對于任意關鍵詞，用戶能夠構造合理的陷門，陷門將被用于檢索指定的關鍵詞.如果服務器不能夠調用陷門生成方法，也不能夠從索引中推理出關鍵詞信息，就能保證密文的安全.在實際中，存儲的數據不限于文檔，可以是視頻、音頻、圖像信息等，只要能夠提取出其中的關鍵字：如基于標題或者標簽.

大部分的方案保護了陷門和索引的安全，即攻擊者不能夠從中直接獲得關鍵詞或者明文的信息.然而，攻擊者仍然可以利用統計知識從索引的結構或者用戶的查詢(即用戶發送給服務器的檢索陷門)中獲知哪些文檔包含了某個關鍵詞.為了抵抗對索引本身靜態的統計分析攻擊，已有的方案有2種解決方法：1)第1種是為每個關鍵詞分別構造匹配不同文檔的獨立陷門,這種方法在查詢某一關鍵詞時，需要進行d(d為文檔總數)次的陷門構造和索引查詢；2)第2種只需要為關鍵詞構造1個陷門，但索引中采用類似鏈表的方式，依次計算獲取包含關鍵詞文檔.查詢時只需要依次構造陷門，但是需要多次的子陷門運算來獲得文檔.顯然，兩種方式的檢索的計算代價都比較大.此外，這些方案的訪問模式(access pattern)均容易受到動態的統計分析攻擊.訪問模式是指對于用戶的每次檢索，哪些文檔包含了查詢的關鍵詞.最近的研究中，Islam等人[8]提出了一種針對訪問模式的具體攻防方案.但是方案的構造不具一般性，實際上并沒有完全解決訪問模式的安全問題.

本文從效率和抵抗統計攻擊2方面考慮來構造索引，提出一種基于Bloom過濾器的可檢索加密的方案：將索引進行整體考慮，采用倒排[10]減少檢索計算代價，同時通過構造偽索引填充來保證索引的安全性.由于Bloom過濾器[11]可用于檢測元素是否屬于集合，而且其空間效率和查詢時間都優于一般算法，常常被用于檢索技術之中.Bloom過濾器對集合采用一個位串表示，并支持元素的Hash查找，既能表示集合，支持集合元素查詢，又能有效地過濾掉不屬于集合的元素.因此本文采用Bloom過濾器而非直接加密關鍵詞的方式構造索引.倒排索引技術具有實現相對簡單、查詢速度快以及支持同義詞查詢等擴展功能的優點，被廣泛應用.將索引整體考慮，就可以形成Bloom過濾器的倒排形式，進一步提升檢索效率.本文主要貢獻如下：

1) 分析了索引整體構建的統計分析安全問題.

2) 設計了一種安全且高效的安全索引，能夠滿足可檢索加密的一般安全要求，同時抵抗統計分析攻擊.

3) 在真實數據上驗證了方案的可行性和高效性.

1 相關工作

檢索加密數據的問題已經得到廣泛的研究，大多數的工作著重于加強安全性以及優化效率.由Goldreich等人[12]和Ostrovsky[13]提出的不經意RAM不會向第三方泄露任何的信息，是解決此問題的一種經典方法.然而，這種方案的實際可行性有待解決，因為它們需要對數多項式時間的計算代價和交互代價.研究者通過降低安全性要求，提高效率和可行性，提出了一系列的可檢索加密方案.可檢索加密最早由Song等人[14]提出的，到目前已經過了10余年的研究.在文獻[14]中，作者明確指出他們的方案會遭受統計攻擊，對于加密的文檔會泄露有價值的信息.但是，并沒有對該問題進行更近一步的討論.

Goh[2]的Z-IDX方案首先給出了索引安全的形式化定義，描述了安全模型即抵抗選擇關鍵詞攻擊的語義安全(IND-CKA)以及更強的IND-CKA2.同時，文章考慮到統計攻擊的問題，利用雙重Hash來構造Bloom過濾器，在第2次計算時加入文檔標識符.這樣使得相同關鍵對應的Bloom過濾器不相同，使得敵手不可比較.這也導致了在檢索某個關鍵詞時，需要計算其相對于每一個文檔的陷門，降低了檢索的效率.Chang等人[4]提出的安全定義與IND-CKA2相似，但是要求陷門也不會泄露任何的信息.Kurosawa等人[5]考慮了安全中除了隱私之前的另一個方面：可靠性，也就是要求服務器不能刪除或修改用戶的索引和密文信息.并且證明了隱私性和可靠性等價于通用可組合安全(UC安全).Li等人[9]提出了一種弱化第三方的可檢索加密方案,允許多個用戶之間進行加密文檔的共享,而非對擁有唯一屬主的文檔進行檢索.上述的方案都是使用對稱密鑰加密的數據，因此也被稱作可檢索對稱加密(SSE).此外有工作研究了公鑰的情況.Boneh等人[15]提出了支持關鍵詞檢索的公鑰加密(PEKS)，該方案的陷門生成函數是概率算法.

除了不經意RAM等理論性方法之外，上述實際可行的可檢索加密方案都會泄露訪問模式信息，面臨遭受統計分析統計的威脅.Islam等人[8]對于可檢索加密的訪問模式泄露問題進行了研究，給出了一種針對訪問模式信息泄露的攻擊以及一種解決方案.但是其安全目標只是為了保護“兩次搜索結果的交集”這一隱私信息，不能完全解決訪問模式問題.為此，需要提出一種更具一般性的攻擊模型，并針對性地設計安全索引.

2 問題描述

2.1 統計分析攻擊

由于索引信息和明文信息的統計特征密切相關，這就為攻擊者分析索引推理出明文提供了可能性.對于推理攻擊可以用不同的方式進行建模，文獻[16]給出了常用的模型，假設攻擊者知道關鍵詞在明文中的分布.從而，攻擊者可以推理出明文內容，即某個關鍵詞是否存在于特定的文檔，這將為攻擊者定位攻擊目標提供便利.統計分析攻擊可以依據靜態的索引進行，也可以依據動態的檢索結果，即訪問模式進行.兩者的區別在于，前者可直接依據索引直接分析包含某個關鍵詞的信息，而后者需要監控查詢過程，從檢索結果分析包含某個關鍵詞的信息，然而兩者的分析方法都是相同的.

ATKstats(D,q,θ):

1) 令U={i|i∈{1,2,…,t},|fq-fwi|≤θ};

2) 返回Gq={wi|i∈U}.

攻擊的效果取決于關鍵詞的詞頻分布，Gq表示與q詞頻相同或者相近(相差不超過θ)的關鍵詞集合，1|Gq|為攻擊準確率.與查詢q詞頻相同或者相近的關鍵詞越少，則集合G越小，攻擊效果越好；反之，當所有關鍵詞頻率都在范圍θ內時，ATKstats等同于隨機猜測，此時攻擊失效，此時攻擊準確率為1t.

定義1.ATKstats攻擊優勢.對于查詢q的ATKstats攻擊優勢為：M(q)=1|Gq|-1t,如果M(q)是可忽略的，那么ATKstats攻擊無效.

文檔關鍵詞的詞頻已被證實符合Zipf法則[17]——單詞的頻次f與其頻率排名r成反比.那么，對于高頻詞，其攻擊返回集合G較小；對于低頻次，其攻擊返回集G較大.也就是說對于高頻詞，ATKstats攻擊準確率可接近100%；對于低頻詞，攻擊準確率降低，但是仍然能夠有效減少需要攻擊的文檔數目.

為了說明統計分析攻擊，考慮如表1和表2所示的例子.表1表示用戶的文檔及其分別包含的關鍵詞.表2為對這個文檔所構建的最簡單的密文索引.該索引對所有的關鍵詞進行加密，用戶檢索時，提交所要檢索的關鍵詞密文(即陷門)到服務器，服務器返回所有包含該關鍵詞的文檔.

Table 1 Keywords of Each Document表1 每個文檔的關鍵詞

Table 2 Encrypted Keywords of Each Document表2 每個文檔加密后的關鍵詞

然而，密文索引有明顯的統計特征.如果攻擊者明確知道文檔索引的明文，或關鍵詞在文檔中的出現次數，他將很容易推測出密文所對應的明文關鍵詞，從而定位到感興趣的文檔.在這個上例中，攻擊者可以直接推斷出κ為w11對應的檢索陷門，且以50%的概率推測出α，ζ分別對應于w21，w22.此時，攻擊優勢分別為：

2.2 研究目標

現有的密文檢索方案，為了抵抗統計分析攻擊，對于不同的文檔會采用不同的密鑰或者加入標志信息構造索引，如圖1(a)所示.Goh[2]構造的Z-IDX方案，在構建索引時，需要經過2輪的偽隨機置換，并且在第2輪的置換中加入文檔標志，生成最后的索引.Cash等人[7]的Π2lev方案，在索引構造時利用了一個計數器，通過累加來區分不同的關鍵詞文檔對應關系.此類方案構造的索引不再泄露這種統計信息，但是在檢索時，需要為關鍵詞計算|D|個不同的陷門，增加了檢索代價.在文獻[7]中對于q的查詢，需要進行fq次解密操作；在文獻[2]中對于任意關鍵詞的檢索，都需要進行|D|次Bloom過濾器查詢操作.因此，我們的研究目標是抵抗統計分析攻擊，同時提高檢索效率，將檢索過程中的計算次數降低為常數級別.

我們的方案構造了一種直接的關鍵詞到陷門的映射，如圖1(b)所示.該陷門對于所有文檔的索引同等適用，從而可以進一步整合單個文檔的索引，提高檢索效率.

Fig. 1 Relations of keywords, documents, trapdoorsand results圖1 關鍵詞、文檔、陷門和檢索結果的關系

3 安全需求

本節討論可檢索加密方案的安全需求，將其分為2部分：可檢索加密的基本安全需求和抵抗統計分析攻擊的δ-安全性.首先，介紹需要用到的符號.

3.1 可證明安全

可證明安全是可檢索加密的基本要求,現有的絕大多數方案采用對選擇密鑰攻擊的語義安全[2-4,9]作為索引方案的安全定義，這要求對于索引具有不可區分性.這里，我們考慮同樣的安全需求，利用對選擇關鍵詞攻擊的不可區分性IND-CKA來證明方案對于選擇關鍵詞攻擊的語義安全.

定義2. IND-CKA.IND-CKA是挑戰者C和攻擊者A之間的游戲，由如下4個過程組成：

1) 設置. 攻擊者A選擇一個文檔集合{D1,D2,…,Dd}并且從挑戰者C獲取對應的索引.

2) 查詢. A可以向C查詢關鍵詞x，獲得對應的陷門Tx，利用陷門，A可以搜索包含x的文檔索引.

4) 應答. 最終，A輸出b′代表其對b的猜測.稱A贏得該游戲，如果b′=b.A贏得該游戲的優勢為AdvA=|Pr[b=b′]-12|,即A的猜測概率與隨機猜測的差.稱A以ε-優勢贏得游戲，如果AdvA≥ε.

IND-CKA是可檢索加密方案基本的安全需求.

3.2δ-安全

由2.1節對于統計分析攻擊的描述可知，統計分析攻擊得以實現的根本原因是關鍵詞詞頻分布不相同.從而，消除索引中關鍵詞的詞頻差異是抵抗統計分析攻擊的一種有效方法.

定義3.δ-安全.從索引中獲知的文檔關鍵詞的詞頻相差都不超過δ∈，并且服從相同的分布D.

定理1. 滿足δ-安全的索引能夠抵抗攻擊推理攻擊.

證明. 由定義3可知，在滿足δ-安全的索引中，對于任意查詢q，q與其他所有關鍵詞的詞頻差距|fwi-fq|≤δ.而且由于所有關鍵詞詞頻分布相同，攻擊者需要令θ≥δ，才能確保q對應的關鍵詞出現在G中.此時，對任意查詢q的攻擊優勢均為M(q)=1t-1t=0.因此，滿足δ-安全的索引能夠抵抗統計分析攻擊.

證畢.

4 索引方案構造

為了提高查詢效率，同時滿足通用安全需求并且能夠抵抗統計分析攻擊，本文提出了一種基于Bloom過濾器的倒排索引方案.

4.1 Bloom過濾器

Bloom過濾器[11]用1個m位數組表示包含有n個元素的集合S={s1,s2,…,sn}.開始階段，數組的所有元素都被初始化為0.Bloom過濾器使用k個獨立的Hash函數h1,h2,…,hk，其中hi:{0,1}*→[1,m],i∈[1,k]，對于每一個元素s∈S，在數組中的h1(s),h2(s),…,hk(s)這些位置的值都被置為1.同一個位置可以被置1多次，然而只需要注意第1次.為了判定元素a是否屬于集合S，需要檢查h1(a),h2(a),…,hk(a)這些位置的值.如果所有的值都為1，那么就認為a是該集合的成員.然而，這種方式存在著誤判，即實際上不是集合S成員的元素a會被判定為屬于該集合.導致出現誤判的原因是：a對應的每一個位置都可能被其他元素而不是a本身置1.另一方面，如果有一個位置的值是0，那么a一定不是集合S的成員.

4.2 符 號

智慧課堂作為新型的教學模式和教學手段，以培養具有高智能和創造力的素質型、技能型人才為目標，依賴于數據挖掘、虛擬現實、人工智能分析等技術，實施學情診斷分析和資源智能推送，開展“云+端”學習活動與支持服務，進行學習過程記錄與多元智能評價的新型教學模式。[1]本研究依托安徽省級質量工程智慧課堂試點項目，開展了基于超星學習通的智慧課堂研究和實踐，應用于高職高專汽車類“汽車裝飾與美容”課程的教學改革中，探索適應社會和企業需求的新型課程教學模式和人才培養手段。

為方便說明，現將索引構造中用到的符號定義如下：

D表示系統中的全部文檔，即有d個元素的文檔集D={D1,D2,…,Dd}，其中Di=Wi，Wi?{0,1}*為關鍵詞的集合.規定n=|Wi|，即從每個文檔中抽取n個關鍵詞.

BF表示m位長的2元向量，即Bloom過濾器.

SK表示用戶私鑰，包含k個私鑰，SK={sk1,sk2,…,skk}.

D(w)表示包含關鍵詞w的文檔集合.

BF1&BF2表示2個BF按位與運算.

4.3 基本方案構造：SE-1

方案SE-1包括5個概率多項式時間算法：Keygen(m,k)，BuildIndex(D,SK)，Trapdoor(w,SK)，SearchIndex(Tw,ID)和Filter(R,FList).

算法1.Keygen(m,k).

給定參數m和k.

算法2.BuildIndex(D,SK).

給定文檔集合D，密鑰SK={sk1,sk2,…,skk}.

1) 構造文檔對應的Bloom過濾器

對于Di(1≤i≤d)中的每一個關鍵詞wij，計算陷門(y1=h(wij,sk1),y2=h(wij,sk2),…,yk=h(wij,skk))，將其對應的Bloom過濾器BFi,對應位置置1.

2) 構造填充的Bloom過濾器

① 計算關鍵詞頻次f1=|D(wr1)|,f2=|D(wr2)|,…,ft=|D(wrt)|.

③ 初始化計數器.對于S中的每一個BFi，構造計數器ctr[BFi]=n.

④ 插值和填充Bloom過濾器.

(i) 對于每一個w∈W:

計算其陷門(y1=f(w,sk1),y2=f(w,sk2),…,yk=f(w,skk))，以及需要填充的個數c=f1-fw;

若|S|

從S中隨機選擇c個BF，即BFs1,BFs2,…,BFs c，將每個BF的對應位置置1;

對于i=1,2,…,c，更新計數器ctr[BFs i]←ctr[BFs i]-1;若ctr[BFs i]=0，將BFs i從S移至V.

(ii) 若|S|≠0，對于每個BF∈S:

將BF從S移至V.

(iii) 令l←|V|.

3) 構建倒排索引ID

算法3.Trapdoor(w,SK).

給定關鍵詞w和密鑰{sk1,sk2,…,skk}.

計算關鍵詞w的陷門為Tw=(y1=f(w,sk1),y2=f(w,sk2),…,yk=f(w,skk)),Tw∈{0,1}k lb m.

算法4.SearchIndex(Tw,ID).

給定檢索關鍵詞w的陷門Tw=(y1,y2,…,yk)以及文檔的倒排索引ID.

算法5.Filter(R,FList).

給定查詢結果集R和填充記錄列表FList.

計算真實文檔finalR=RFList.

4.4 安全分析

本節分析方案是否滿足對于選擇關鍵詞攻擊的不可區分性以及是否δ-安全.

定理2. 索引方案SE-1滿足IND-CKA，如果f是一個偽隨機函數.

假設SE-1不是對于選擇關鍵詞攻擊語義安全的，那么，存在算法A能夠在多項式時間內以ε-優勢贏得游戲.我們構造另一個算法A′，該算法將算法A當作子算法來判斷函數f是偽隨機函數或是隨機函數.在調用BuildIndex和Trapdoor算法時，A′詢問預言機Of得到未知函數f:{0,1}*→{0,1}m.A′利用A的步驟如下：

查詢. 收到A對于關鍵詞x的查詢之后，A′運行Trapdoor算法，返回陷門Tx.

應答. 最終，A輸出b′代表其對b的猜測.稱A贏得該游戲，如果b′=b.A′輸出0，表示其猜測f為偽隨機函數；否則，A′輸出1.

下面，我們證明A′能夠以大于ε的優勢判斷f為偽隨機函數或者隨機函數.

情況1. 當f為偽隨機函數.此時A′完全模擬了IND-CKA游戲中的挑戰者，那么由A的定義可知

情況2. 當f為隨機函數，首先證明分析中只需要考慮挑戰涉及的2個關鍵詞集合.也就是S*中其他的元素不會泄露關于挑戰集合的信息.f作為一個隨機函數，因此對于A來說在索引中關聯同一個關鍵詞的編碼是不可行的，否則A能預測一個隨機函數的輸出.根據這個推論，加上對于選擇集合D0,D1的限制，以及發起挑戰之后的查詢限制，從A的角度，對于關鍵詞z∈D0,D1，其陷門和S*中其他關鍵詞的陷門是相互獨立的.即A從S*的其他元素中不能學習到關于D0,D1的知識.

假設D0,D1包含2個關鍵詞x,y并且x∈D0,y∈D1.假設A以優勢θ>0猜對b.那就是說，給定f(z)，A能夠以優勢θ>0判斷z=x或z=y.即A能夠以優勢θ>0區分隨機函數的輸出.然而這是不可能的.A最多只能以12的概率猜對b.由此可見

綜上，

證畢.

下面討論SE-1對于統計分析攻擊的安全性，需要分2步進行.首先需要證明填充的索引項和由文檔生成的索引項是不可區分的.在此基礎之上，證明方案是δ-安全性的，即能夠抵抗統計分析攻擊.

定義4. 文檔索引與填充索引不可區分性.若文檔索引和填充索引都具有良好的隨機性，則它們不可取分.

定理3. SE-1具有文檔索引與填充索引不可區分性.

證明. 從構造方式可知，SE-1的文檔索引和填充索引不可區分.對任意文檔索引，其構造看作是n×k個偽隨機函數的聯合輸出，即

F(w1,w2,…wn,sk1,sk2,…,skk)=
f(w1,sk1)‖f(w1,sk2)‖…‖f(w1,skk)‖…
‖f(wn,sk1)‖f(wn,sk2)‖…‖f(wn,skk),

顯然這個輸出也是偽隨機的.

對于任意的填充索引，有2種情況：1) 未使用不屬于W的關鍵詞作為輸入構造；2) 使用不屬于W的關鍵詞作為輸入構造.然而，二者最終都是選擇了n個屬于{0,1}*的值作為輸入.因此輸出結果同樣可表示為：

證畢.

定理4. 索引方案SE-1具有δ-安全性.

證明. 由填充算法可知，對于任意w∈W，有f個索引包含該關鍵詞.考慮到Bloom過濾器的誤判率，可知，在剩下的d+l-f個索引中，可能出現誤判的情況，導致關鍵詞w的詞頻增加.已知在一個Bloom過濾器中，誤判率為：

fp=[1-(1m)kn]k≈(1-e-knm)k，那么w被誤判為屬于原本不包含它的索引的概率為：

證畢.

4.5 改進方案構造SE-2

SE-1的構造能夠有效地提供索引的安全性，同時保證檢索的效率.然而，將所有關鍵詞都填充到與詞頻最高的關鍵詞一樣的數目，會增加索引的存儲代價.同時，這樣的安全性也過于嚴格.考慮到Zipf法則描述的詞頻曲線，可知，對于低詞頻部分的關鍵詞，攻擊的優勢已經可以很小，可以忽略，容易被攻擊的只是高詞頻部分的關鍵詞.因此對于SE-1在構建索引的改進主要在于對關鍵詞進行選擇性填充，從而降低存儲代價.我們需要能夠保證抵抗統計分析攻擊的更加寬松的安全定義.

定義5. (α,δ)-安全.從索引中獲知的任意文檔關鍵詞，至少存在一個大小為α∈[1,t]且包含該關鍵詞的集合，使得它們詞頻都在某個的δ∈區間內，并且服從相同的分布D.

顯然，滿足(α,δ)-安全的索引也能夠抵抗統計分析攻擊.由于此時，對任意查詢q的攻擊優勢最大為M(q)=1α-1t.只要α足夠大，則攻擊優勢可以忽略.

SE-2的構造與SE-1十分相似，區別只出現在構造索引算法的填充部分.不失一般性，假設t整除α，記b=tα.將詞頻排序的關鍵詞按詞頻從大到小依次分為b段，則每段共有α個關鍵詞.對于第j段中的關鍵詞wji，需要在cj=fji-fjα+1,j∈[0,b-1]個Bloom過濾器中進行填充.填充的具體方法與SE-1相同.

方案SE-2由5個概率多項式時間算法組成:Keygen(m,k)，BuildIndex(D,SK)，Trapdoor(w,SK)，SearchIndex(Tw,ID)和Filter(R,FList).其中，Keygen(m,k)，Trapdoor(w,SK)，SearchIndex(Tw,ID)，Filter(R,FList) 與SE-1完全相同，下面給出BuildIndex(D,SK,α)算法.

算法6.BuildIndex(D,SK,α).

給定文檔集合D，密鑰SK={sk1,sk2,…,skk}，安全參數α.

1) 構造文檔對應的Bloom過濾器

對于Di(1≤i≤d)中的每一個關鍵詞wij，計算該關鍵詞的陷門(y1=h(wij,sk1),y2=h(wij,sk2),…,yk=h(wij,skk))，將其對應的Bloom過濾器BFi對應位置置1.

2) 構造填充的Bloom過濾器

① 計算關鍵詞頻次f1=|D(wr1)|,f2=|D(wr2)|,…,ft=|D(wrt)|.

③ 初始化計數器.對于S中的每一個BF，構造計數器ctr=n.

④ 將W按頻次高低分為b=tα個集合W1,W2,…,Wb.

(i) 對于每一個w∈Wj,j∈[1,b]:

計算其陷門(y1=f(w,sk1),y2=f(w,sk2),…,yk=(w,skk))，需要填充的個數c=f(j-1)α-fw.

若|S|

從S中隨機選擇c個BF，即BFs1,BFs2,…,BFs c，將每個BF的對應位置置1.

對于i=1,2,…,c，更新計數器ctr[BFs i]←ctr[BFs i]-1;如果ctr[BFs i]=0， 將BFs i從S移至V.

(ii) 若|S|≠0，對于每個BF∈S:

將BF從S移至V.

(iii) 令l←|V|.

3) 構建倒排索引ID

SE-2與SE-1一樣滿足IND-CKA安全.由構造可知，SE-2滿足(α,δ)-安全，因此能夠抵抗統計分析攻擊.相比于SE-1，SE-2有效地減少了索引的存儲空間.

5 實驗結果與性能分析

實驗選取了來自新浪網的公開新聞數據，其中包括了100萬條新聞的文檔數據.實驗在有1個Master Node 和5個Slave Nodes的Hadoop Hbase實驗集群上進行.

5.1 統計分析攻擊效果實驗

從數據集中抽取了10萬條新聞記錄作為文檔進行實驗.將關鍵詞按照出現頻次進行排序，用對應的序號表示關鍵詞.10萬個文檔包含了74 702個不同的關鍵詞，詞頻最高的關鍵詞為出現4 184次的“中國”，詞頻最低的關鍵詞為出現1次的“生產國”等共27 987個不同的關鍵詞.圖2(a)為文檔中提取的關鍵詞頻率曲線：橫軸是關鍵詞頻排名，縱軸表示對應關鍵詞出現的頻次，這個信息也是攻擊者所能夠知道的背景知識.可以看出，高詞頻部分的關鍵詞比較少，并且相鄰的兩個關鍵詞之間頻次的差距較大.低詞頻部分的關鍵詞數目較多，而且相鄰的關鍵詞之間頻次差距不大且相等.

實驗對比了Z-IDX方案和SE-1，SE-2方案，分別遍歷了所有的關鍵詞，記錄不同方案的返回集合表現出的詞頻分布特征.圖2(b)為Z-IDX方案的關鍵詞詞頻統計信息，可以看出，該曲線和圖2(a)中的曲線幾乎完全重合.這意味著，對于高頻部分的詞攻擊幾乎能以100%的概率推測；對于低頻部分的關鍵詞，猜測的準的概率仍然較低.圖2(c)為SE-1方案的關鍵詞詞頻統計信息，可以看出，每個關鍵詞出現的頻次很接近，都在4 200左右，此時統計分析攻擊的效果和隨機猜測效果一樣.圖2(d)為SE-2方案的關鍵詞詞頻統計信息，實驗選擇α=1 000，可以看出低頻詞部分差異較小，前10 000個高頻詞出現頻率幾乎相同.此時相比SE-1方案，節省了近45的索引存儲空間.

Fig. 2 Querying results圖2 檢索結果

Fig. 3 Query performance圖3 查詢性能

5.2 性能實驗

性能實驗是在大小為20萬、70萬和100萬的3個不同的新聞文檔的數據集上分別進行的.針對3個不同的數據集，分別建立Z-IDX和SE-1，選擇相同的關鍵詞，在2個索引中分別檢索,測試檢索用時.文檔大小對查詢的影響，如圖3所示.隨著文檔集的增加，Z-IDX和SE-1索引檢索用時都會增長.從圖3中可以看出，隨著文檔集大小的增加，使用Z-IDX檢索用時的增加比使用SE-1索引檢索用時的增加要快.由此可以推斷，SE-1索引在文檔集較大時，有更好的檢索優勢，也更加適合處理海量數據.

6 總 結

用戶外包數據往往包含了敏感信息，為了保護數據,通常會將數據加密之后再進行外包.為了實現對外包加密數據的檢索，需要構造安全的密文索引.本文分析該場景下索引的需求，提出了一種基于Bloom過濾器的安全索引：該索引利用Bloom過濾器減少索引空間占用；結合改進的倒排技術，該索引能夠提供較好的檢索效率；此外，利用索引的填充和過濾技術，在保證常數級檢索效率的同時確保了索引能夠抵抗統計分析攻擊.

在面對分布式存儲的數據時，文中的算法可以擴展到利用MapReduce實現，從而進一步提高索引的建立和檢索效率.這些是今后需要考慮的工作.

[1]Li Hui, Sun Wenhai, Li Fenghua, et al. Secure and privacy-preserving data storage service in public cloud [J]. Journal of Computer Research and Development, 2014, 51(7): 1397-1409 (in Chinese)(李暉, 孫文海, 李鳳華, 等. 公共云存儲服務數據安全及隱私保護技術綜述[J]. 計算機研究與發展, 2014, 51(7): 1397-1409)

[2]Goh E J. Secure indexes[EB/OL]. IACR Cryptology ePrint Archive, 2003 [2012-08-15]. http://eprint.iacr.org/2003/216

[3]Curtmola R, Garay J, Kamara S, et al. Searchable symmetric encryption: Improved definitions and efficient constructions [J]. Journal of Computer Security, 2011, 19(5): 895-934

[4]Chang Y C, Michael M. Privacy preserving keyword searches on remote encrypted data [C] //Proc of the 3rd Int Conf on Applied Cryptography and Network Security. Berlin: Springer, 2005: 442-455

[5]Kurosawa K, Yasuhiro O. UC-secure searchable symmetric encryption [C] //Proc of the 16th Int Conf on Financial Cryptography and Data Security.Berlin: Springer, 2012: 285-298

[6]Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption [C] //Proc of the 19th ACM Conf on Computer and Communications Security. New York: ACM, 2012: 965-976

[7]Cash D, Jaeger J, Jarecki S, et al. Dynamic searchable encryption in very large databases: Data structures and implementation [C] //Proc of NDSS’2014. Reston, Virginia: The Internet Society, 2014 [2015-10-01]. http://www.internetsociety.org/access-pattern-disclosure-searchable-encry ption-ramification-attack-and-mitigation

[8]Islam M S, Kuzu M, Kantarcioglu M. Access pattern disclosure on searchable encryption: Ramification, attack and mitigation [C] //Proc of NDSS’2012. Reston, Virginia: The Internet Society, 2012 [2015-10-01]. http://www.internet society.org/doc/dynamic-searchable-encryption-very-large-data bases-data-structures-and-implementation

[9]Li Zhen, Jiang Han, Zhao Minghao. A discretionary searchable encryption scheme in multi-user settings [J]. Journal of Computer Research and Development, 2015, 52(10): 2313-2322 (in Chinese)(李真, 蔣瀚, 趙明昊. 一個自主授權的多用戶可搜索加密方案[J]. 計算機研究與發展, 2015, 52(10): 2313-2322)

[10]Zobel J, Moffat A. Inverted files for test search engines [J]. ACM Computing Surveys, 2006, 28(2): No.6

[11]Bloom B. Space/time trade-offs in Hash coding with allowable errors [J]. Communications of the ACM, 1970, 13(7): 422-426

[12]Goldreich O, Ostrovsky R. Software protection and simulation on oblivious RAMs [J]. Journal of the ACM, 1996, 43(3): 431-473

[13]Ostrovsky R. Efficient computation on oblivious RAMs [C] //Proc of the 22nd Annual ACM Symp on Theory of Computing. New York: ACM, 1990: 514-523

[14]Song D X, Wagner D, Perrig A. Practical techniques for searches on encrypted data [C] //Proc of IEEE S&P’2000. Piscataway, NJ: IEEE, 2000: 44-55

[15]Boneh D, Di Crescenzo G, Ostrovsky G, et al. Public key encryption with keyword search [C] //Proc of EUROCRYPT’2004. Berlin: Springer, 2004: 506-522

[16]Damiani E, Vimercati S D C D, Jajodia S, et al. Balancing confidentiality and efficiency in untrusted relational DBMSs [C] //Proc of the 10th ACM Conf on Computer and Communications Security. New York: ACM, 2003: 93-102

[17]Zipf G K. Human behavior and the principle of least effort [J]. Journal of Clinical Psychology, 1949, 6(3): 306-306

Hui Zhen, born in 1987. PhD candidate. His main research interests include accesss control and data protection.

Feng Dengguo, born in 1965.Professor and PhD supervisor. His main research interests include cryptography and information security.

Zhang Min, born in 1975. PhD and senior engineer. Her main research interests include theories and techniques about trusted computing and database security.

Hong Cheng, born in 1985. PhD and associate professor. His main research interests include outsourcing database security.

A Secure Index Against Statistical Analysis Attacks

Hui Zhen1,2, Feng Dengguo1,3, Zhang Min1, and Hong Cheng1

1(LaboratoryofTrustedComputingandInformationAssurance,InstituteofSoftware,ChineseAcademyofSciences,Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)3(StateKeyLaboratoryofComputerScience(InstituteofSoftware,ChineseAcademyofSciences),Beijing100190)

Most of current searchable encryption schemes suffer from the threat of statistical analysis attacks. Some related works design their keyworddocument trapdoors in a one-to-one method to avoid the threat, but it could lead to a severe overhead in searching cost. In the present paper, we design an efficient secure index to defend against a kind of statistical analysis attack. This scheme uses a Bloom filter to build indexes for each document. In order to save searching cost, one unique trapdoor is built for one word. To satisfy the security requirement, this scheme treats indexes of all documents as a matrix, and then adopts forged indexes and interpolation to make sure the frequencies of different words are closed and all indexes in the matrix are indistinguishable between each other. As a result, a particular word in the matrix cannot be recognized, thus the statistical analysis attack is resisted. In implementation, this scheme uses inverted indexes to further improve querying performance. The scheme is proved to be semantic security. Experimental results show that the querying performance of our scheme is double of Z-IDX at large dataset and words cannot be recognized based on their frequencies.

searchable encryption (SE); statistical leakage; inverted index; Bloom filter; access pattern

2015-08-13；

2016-10-10

國家自然科學基金重點項目(61230005);國家自然科學基金項目(61402456) This work was supported by the Key Program of the National Natural Science Foundation of China (61230005) and the National Natural Science Foundation of China (61402456).

TP309.2