一種可抵抗統(tǒng)計攻擊的安全索引

惠 榛 馮登國 張 敏 洪 澄

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

一種可抵抗統(tǒng)計攻擊的安全索引

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

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

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

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

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

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

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

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

1) 分析了索引整體構(gòu)建的統(tǒng)計分析安全問題.

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

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

1 相關(guān)工作

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

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

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

2 問題描述

2.1 統(tǒng)計分析攻擊

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

ATKstats(D,q,θ):

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

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

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

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

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

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

Table 1 Keywords of Each Document表1 每個文檔的關(guān)鍵詞

Table 2 Encrypted Keywords of Each Document表2 每個文檔加密后的關(guān)鍵詞

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

2.2 研究目標(biāo)

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

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

Fig. 1 Relations of keywords, documents, trapdoorsand results圖1 關(guān)鍵詞、文檔、陷門和檢索結(jié)果的關(guān)系

3 安全需求

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

3.1 可證明安全

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

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

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

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

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

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

3.2δ-安全

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

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

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

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

證畢.

4 索引方案構(gòu)造

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

4.1 Bloom過濾器

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

4.2 符 號

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

為方便說明，現(xiàn)將索引構(gòu)造中用到的符號定義如下：

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

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

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

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

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

4.3 基本方案構(gòu)造：SE-1

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

算法1.Keygen(m,k).

給定參數(shù)m和k.

算法2.BuildIndex(D,SK).

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

1) 構(gòu)造文檔對應(yīng)的Bloom過濾器

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

2) 構(gòu)造填充的Bloom過濾器

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

③ 初始化計數(shù)器.對于S中的每一個BFi，構(gòu)造計數(shù)器ctr[BFi]=n.

④ 插值和填充Bloom過濾器.

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

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

若|S|

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

對于i=1,2,…,c，更新計數(shù)器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) 構(gòu)建倒排索引ID

算法3.Trapdoor(w,SK).

給定關(guān)鍵詞w和密鑰{sk1,sk2,…,skk}.

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

算法4.SearchIndex(Tw,ID).

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

算法5.Filter(R,FList).

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

計算真實文檔finalR=RFList.

4.4 安全分析

本節(jié)分析方案是否滿足對于選擇關(guān)鍵詞攻擊的不可區(qū)分性以及是否δ-安全.

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

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

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

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

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

情況1. 當(dāng)f為偽隨機函數(shù).此時A′完全模擬了IND-CKA游戲中的挑戰(zhàn)者，那么由A的定義可知

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

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

綜上，

證畢.

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

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

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

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

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的關(guān)鍵詞作為輸入構(gòu)造；2) 使用不屬于W的關(guān)鍵詞作為輸入構(gòu)造.然而，二者最終都是選擇了n個屬于{0,1}*的值作為輸入.因此輸出結(jié)果同樣可表示為：

證畢.

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

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

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

證畢.

4.5 改進方案構(gòu)造SE-2

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

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

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

SE-2的構(gòu)造與SE-1十分相似，區(qū)別只出現(xiàn)在構(gòu)造索引算法的填充部分.不失一般性，假設(shè)t整除α，記b=tα.將詞頻排序的關(guān)鍵詞按詞頻從大到小依次分為b段，則每段共有α個關(guān)鍵詞.對于第j段中的關(guān)鍵詞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)，F(xiàn)ilter(R,FList) 與SE-1完全相同，下面給出BuildIndex(D,SK,α)算法.

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

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

1) 構(gòu)造文檔對應(yīng)的Bloom過濾器

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

2) 構(gòu)造填充的Bloom過濾器

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

③ 初始化計數(shù)器.對于S中的每一個BF，構(gòu)造計數(shù)器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))，需要填充的個數(shù)c=f(j-1)α-fw.

若|S|

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

對于i=1,2,…,c，更新計數(shù)器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) 構(gòu)建倒排索引ID

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

5 實驗結(jié)果與性能分析

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

5.1 統(tǒng)計分析攻擊效果實驗

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

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

Fig. 2 Querying results圖2 檢索結(jié)果

Fig. 3 Query performance圖3 查詢性能

5.2 性能實驗

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

6 總 結(jié)

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

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

[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)(李暉, 孫文海, 李鳳華, 等. 公共云存儲服務(wù)數(shù)據(jù)安全及隱私保護技術(shù)綜述[J]. 計算機研究與發(fā)展, 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)(李真, 蔣瀚, 趙明昊. 一個自主授權(quán)的多用戶可搜索加密方案[J]. 計算機研究與發(fā)展, 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

國家自然科學(xué)基金重點項目(61230005);國家自然科學(xué)基金項目(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