李宇溪 周福才 徐 劍 徐紫楓

(東北大學(xué)軟件學(xué)院 沈陽 110819)

密文搜索是指當(dāng)數(shù)據(jù)以加密形式存儲(chǔ)在設(shè)備中時(shí)，在確保數(shù)據(jù)安全的前提下檢索數(shù)據(jù)的技術(shù).因?yàn)閿?shù)據(jù)加密后會(huì)嚴(yán)重影響用戶數(shù)據(jù)的可用性，因此如何在保證用戶隱私和數(shù)據(jù)安全性的前提下，確保密文數(shù)據(jù)的可用性，就成為了密文搜索領(lǐng)域的重要研究?jī)?nèi)容.總體來說，密文搜索主要包括兩大實(shí)體：用戶和服務(wù)器.以及2個(gè)步驟：初始化階段和搜索階段.在初始化階段，用戶在客戶端加密文件集合與索引數(shù)據(jù)結(jié)構(gòu)，并上傳給服務(wù)器加密后的文件集合和一個(gè)加密索引；在搜索階段，用戶想要服務(wù)器返回包括某關(guān)鍵字的所有文件.為了執(zhí)行這一請(qǐng)求，用戶發(fā)送一個(gè)令牌，這一令牌能夠封裝這一搜索請(qǐng)求，并且不會(huì)泄露任何關(guān)于關(guān)鍵字的信息.服務(wù)器收到用戶發(fā)送的令牌后，用這個(gè)令牌以及加密索引，通過某種方式返回符合搜索條件的加密文件.

當(dāng)前，密文搜索方案大都基于單服務(wù)器模型，用戶將密文數(shù)據(jù)存儲(chǔ)在單個(gè)云服務(wù)提供商中.受限于預(yù)計(jì)算量較大、交互輪數(shù)較多等實(shí)際缺陷，云服務(wù)器只能進(jìn)行簡(jiǎn)單的搜索請(qǐng)求，大大影響了密文搜索方案的可用性.這種情況下云服務(wù)器不能在完全在保證用戶數(shù)據(jù)隱私的前提下，對(duì)密文搜索功能進(jìn)行豐富完善，使其真正投入企業(yè)級(jí)大規(guī)模應(yīng)用收到了限制.實(shí)際情況下，云服務(wù)提供商并不僅限于單個(gè)實(shí)體，可能協(xié)同服務(wù)提供商同時(shí)提供服務(wù).多服務(wù)器模型在近幾年很多相關(guān)工作已被廣泛使用[1-3].由于云服務(wù)提供商之間存在一定的競(jìng)爭(zhēng)關(guān)系，因而不會(huì)為了短期利益而勾結(jié)在一起攻擊用戶隱私數(shù)據(jù).在現(xiàn)實(shí)的應(yīng)用場(chǎng)景中，協(xié)同云服務(wù)通常由大公司來提供，例如亞馬遜、微軟和谷歌等這些公司不會(huì)因?yàn)樯虡I(yè)利益來與云存儲(chǔ)服務(wù)器工商進(jìn)行合謀，這不僅會(huì)破壞他們的聲譽(yù)，從長(zhǎng)遠(yuǎn)角度來看也會(huì)影響其商業(yè)利潤(rùn)和公司發(fā)展.

然而，很多情況下，粗粒度的返回全部搜索結(jié)果并不能滿足用戶的需求.在數(shù)據(jù)量較大的情況下，用戶在進(jìn)行多關(guān)鍵字搜索時(shí)，不僅需要獲得匹配到的文件，與此同時(shí)希望服務(wù)器根據(jù)其與搜索關(guān)鍵字的相關(guān)度，對(duì)搜索的文件進(jìn)行排序，從而更有效地得到想要的結(jié)果.然而，多數(shù)密文搜索方案都是將匹配到關(guān)鍵字搜索條件的全部搜索結(jié)果返回給用戶，并沒有搜索結(jié)果進(jìn)行篩選或排序，尤其是在多關(guān)鍵字搜索場(chǎng)景下.雖然現(xiàn)在已有相關(guān)工作試圖解決支持排序的密文搜索問題，但其基于較高的系統(tǒng)模型假設(shè)(例如,引入可信第三方)或較低的安全目標(biāo)(例如,允許服務(wù)器獲得關(guān)鍵詞信息)或由于通過服務(wù)器重加密或其他復(fù)雜運(yùn)算而導(dǎo)致效率較低.因此，完善現(xiàn)有的支持結(jié)果排序的密文搜索機(jī)制,是未來需要研究的一個(gè)重要方向.

針對(duì)上述問題，并結(jié)合實(shí)際應(yīng)用場(chǎng)景中對(duì)多關(guān)鍵字密文搜索的可用性需求及安全性需求，面向雙服務(wù)器模型，提出了支持相關(guān)度排序的多關(guān)鍵字密文搜索方案，在能夠保證安全高效地實(shí)現(xiàn)密文搜索的同時(shí)，滿足對(duì)于搜索結(jié)果的排序.

1) 方案基于TF-IDF加權(quán)技術(shù)并融合同態(tài)加密體制，構(gòu)建包含相關(guān)度權(quán)值的關(guān)鍵字安全索引，優(yōu)化搜索過程中服務(wù)器計(jì)算代價(jià)并降低了存儲(chǔ)復(fù)雜度.方案利用TF-IDF加權(quán)規(guī)則來計(jì)算關(guān)鍵字與文件之間的相關(guān)度權(quán)值，并利用Paillier同態(tài)加密算法將其加密，使得服務(wù)器在搜索過程中，無需對(duì)令牌及密文進(jìn)行解密的前提下能夠?qū)?quán)值密文進(jìn)行相加，從而獲得多關(guān)鍵字權(quán)值密文之和，滿足多關(guān)鍵字搜索請(qǐng)求下對(duì)結(jié)果的排序.

2) 構(gòu)建安全可信的協(xié)同處理機(jī)制實(shí)現(xiàn)對(duì)于搜索結(jié)果安全排序.方案構(gòu)建2個(gè)不可共謀的服務(wù)器S和coS來共同扮演服務(wù)提供者的角色.其中S負(fù)責(zé)存儲(chǔ)密文和索引信息，coS負(fù)責(zé)協(xié)助S來進(jìn)行搜索結(jié)果排序工作.方案引入兩方安全密文比較協(xié)議，在不向協(xié)同服務(wù)器泄露搜索模式與訪問模式的前提下，實(shí)現(xiàn)對(duì)于搜索結(jié)果的高效排序.與單服務(wù)器模型相比，降低了用戶與服務(wù)器之間通信代價(jià)的同時(shí)，減少了向服務(wù)器泄露的消息.

3) 在安全性方面，在誠(chéng)實(shí)并好奇的半可信場(chǎng)景下給出MES-RR方案的安全模型，并依據(jù)所提出的安全模型對(duì)該方案的安全性進(jìn)行嚴(yán)格證明，證明方案在隨機(jī)語言模型下能夠抵抗敵手自適應(yīng)選擇關(guān)鍵字攻擊，滿足IND-CKA2安全性.性能分析表明，與以往的支持搜索結(jié)果排序的多關(guān)鍵字密文搜索方案相比，本方案大大降低了用戶存儲(chǔ)代價(jià)和訪問交互次數(shù)，適用于實(shí)際的云存儲(chǔ)環(huán)境.

1 相關(guān)工作

1.1 通用密文搜索方案

密文搜索由Song等人在2000年首次提出[4]，作者使用了一個(gè)特殊的2層的加密構(gòu)造，將明文文件劃分為“單詞”并對(duì)其分別加密，通過對(duì)整個(gè)密文文件掃描和密文單詞進(jìn)行比對(duì)，就可確認(rèn)關(guān)鍵詞是否存在，甚至統(tǒng)計(jì)其出現(xiàn)的次數(shù)，然而這導(dǎo)致了搜索復(fù)雜度較高，與文件集合的大小呈線性關(guān)系.之后，密文搜索方案按照實(shí)體不同分為對(duì)稱和非對(duì)稱2種應(yīng)用場(chǎng)景.在對(duì)稱場(chǎng)景中，數(shù)據(jù)擁有者加密自己的數(shù)據(jù).加密的數(shù)據(jù)和對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)被存儲(chǔ)在服務(wù)器中，只有數(shù)據(jù)擁有者以及被數(shù)據(jù)擁有者認(rèn)證的用戶才能夠?qū)ζ溥M(jìn)行搜索.Curtmola等人在2006年對(duì)對(duì)稱場(chǎng)景的密文搜索模型進(jìn)行了形式化定義，并基于倒排索引提出了一個(gè)高效的構(gòu)建方案[5]，方案只需常數(shù)級(jí)時(shí)間即可完成搜索操作，然而，執(zhí)行文件的添加或刪除操作需要重新構(gòu)建索引，時(shí)間開銷較大.除此之外，他們提出了基于廣播加密技術(shù)的多用戶密文搜索構(gòu)造思想，即使只有單一數(shù)據(jù)擁有者，仍然可以允許任意被授權(quán)的用戶，通過向數(shù)據(jù)擁有者請(qǐng)求搜索令牌，來向服務(wù)器發(fā)送搜索請(qǐng)求.另一個(gè)對(duì)稱場(chǎng)景的經(jīng)典方案是Kamara等人在2012年提出的支持搜索結(jié)果完整性驗(yàn)證的密文搜索方案[6]，方案利用基于雙線性映射累加器和擴(kuò)展歐幾里德算法的集合證明理論，實(shí)現(xiàn)對(duì)于搜索結(jié)果的離線驗(yàn)證.Boneh等人在2004年首次提出非對(duì)稱場(chǎng)景的密文搜索方案[7]，并且他們的創(chuàng)新性思想為后來很對(duì)研究成果提供了啟發(fā).在非對(duì)稱場(chǎng)景中，數(shù)據(jù)擁有者將數(shù)據(jù)加密并上傳至服務(wù)器，任何擁有解密密鑰的用戶可以執(zhí)行搜索請(qǐng)求(例如郵件服務(wù)器場(chǎng)景).

在很多情況下，用戶想要搜索包含多個(gè)關(guān)鍵字信息的文件，基于此需求，Golle等人首先提出了多關(guān)鍵字密文搜索機(jī)制并給出了具體構(gòu)造方案[8]，但是方案中搜索令牌的大小與加密文件數(shù)呈線性關(guān)系，用戶計(jì)算代價(jià)過高.Cash等人在2013年提出了第一個(gè)面向任意結(jié)構(gòu)化數(shù)據(jù)的支持交集的密文搜索方案[9]，并證明方案滿足IND-CKA2安全性.2014年，Cash等人提出了一個(gè)支持連接詞查詢的高效密文搜索方案[10]，方案針對(duì)數(shù)據(jù)集中關(guān)鍵字的出現(xiàn)頻率設(shè)計(jì)3層安全索引結(jié)構(gòu)，使搜索過程更具有靈活性，更適合大數(shù)據(jù)場(chǎng)景.2017年，Wang等人提出了面相多關(guān)鍵字的模糊密文搜索方案[11]，方案不需要提前設(shè)置索引存儲(chǔ)空間，從而大大降低了方案的搜索復(fù)雜度.

1.2 支持排序的密文搜索方案

在通用密文搜索方案中，用戶必須解密所有返回的搜索結(jié)果,才能得到所需文件.然而，在數(shù)據(jù)量較大的情況下，查詢結(jié)果中可能僅僅有極少部分為用戶所需文件.支持排序的密文搜索方案可以按照關(guān)鍵詞與文件的相關(guān)度對(duì)搜索結(jié)果進(jìn)行排序，并返回最相關(guān)的文件來優(yōu)化搜索結(jié)果，用戶只需根據(jù)排序結(jié)果解密少量加密文件即可獲得所需文件，這能在一定程度上降低網(wǎng)絡(luò)負(fù)載并且增強(qiáng)系統(tǒng)可用性.

早期支持排序的密文搜索方案[12-14]大多利用保序加密方法(order-preserving encryption， OPE)實(shí)現(xiàn)了針對(duì)單關(guān)鍵字密文搜索結(jié)果的排序.用戶在上傳文件之前，使用OPE對(duì)關(guān)鍵字相關(guān)性分?jǐn)?shù)加密,搜索過程中服務(wù)器根據(jù)每個(gè)文件對(duì)搜索關(guān)鍵字相關(guān)性分?jǐn)?shù)的密文結(jié)果進(jìn)行排序,并將經(jīng)過排序后的前k個(gè)文件返回給用戶.這種方法的優(yōu)點(diǎn)是,在每次搜索的過程中,用戶可以得到在特定相關(guān)度權(quán)衡模型下對(duì)該關(guān)鍵字最為相關(guān)的文件,節(jié)省了帶寬和因?yàn)榻饷軒淼挠?jì)算開銷,但是服務(wù)器也掌握了每個(gè)文件對(duì)于某個(gè)關(guān)鍵字相關(guān)性程度的信息.

Cao等人在2014年首次提出支持搜索結(jié)果排序的多關(guān)鍵字密文搜索方案[15]，方案中基于內(nèi)積相似性(inner product similarity， IPS)來計(jì)算每個(gè)文件中匹配到的關(guān)鍵字的數(shù)量，以此來計(jì)算文件權(quán)值并對(duì)文件進(jìn)行排序.內(nèi)積相似性中文件的權(quán)值與每個(gè)文件中匹配的關(guān)鍵字的個(gè)數(shù)相關(guān).但是僅僅依賴IPS技術(shù)，使得方案沒有考慮關(guān)鍵字對(duì)于整個(gè)文件集合的重要性等信息.TF-IDF加權(quán)技術(shù)為信息檢索領(lǐng)域常用來評(píng)估某個(gè)關(guān)鍵詞對(duì)于一個(gè)文件集或一個(gè)語料庫(kù)中的其中一份文件的重要程度的方法.許多支持排序的密文搜索方案基于TF-IDF加權(quán)技術(shù)來實(shí)現(xiàn)：Strizhov等人在2014年融合TF-IDF加權(quán)技術(shù)和IPS設(shè)計(jì)了新型密文搜索排序方案[16]，為了防止服務(wù)器獲取相關(guān)度信息，方案中假設(shè)服務(wù)器僅僅執(zhí)行搜索功能，并不能對(duì)結(jié)果進(jìn)行排序，服務(wù)器將搜索到的全部文件返回給用戶，用戶在本地基于相關(guān)度權(quán)值對(duì)搜索結(jié)果進(jìn)行排序.方案的不足之處在于，為了實(shí)現(xiàn)排序，相關(guān)度由全同態(tài)加密方案進(jìn)行加密，使得構(gòu)建索引階段時(shí)間復(fù)雜度較高，而且方案不支持文件動(dòng)態(tài)更新.同年，Sun等人利用余弦度量技術(shù)設(shè)計(jì)一個(gè)支持排序的可驗(yàn)證密文搜索方案[17].他們的方案能夠在稍稍犧牲搜索準(zhǔn)確度的前提下，提高搜索效率.Zhang等人提出了一個(gè)多數(shù)據(jù)擁有者模型下的支持排序的密文搜索方案[18].不同的數(shù)據(jù)擁有者利用不同的私鑰來加密文件和關(guān)鍵字，經(jīng)過認(rèn)證的用戶能夠在不知道擁有者私鑰的前提下發(fā)起查詢.2015年，F(xiàn)u等人提出了支持并行搜索的可排序密文搜索方案[19]，方案利用向量空間模型構(gòu)造索引，模型中將每一個(gè)TF-IDF權(quán)值轉(zhuǎn)化成2個(gè)隨機(jī)向量搜索過程中將搜索向量轉(zhuǎn)化成矩陣乘積形式，并且計(jì)算搜索向量與數(shù)據(jù)庫(kù)中所有密文文件向量的點(diǎn)相似度來判定相關(guān)性.

Orencik等人在2016年提出了支持排序的多關(guān)鍵字密文搜索方案[20]，他們利用位置敏感Hash函數(shù)(location sensetive Hash， LSH)來聚類相似文件.然而，LSH適用于相似性搜索但是不能提供精確排序.同文獻(xiàn)[15]類似，他們的排序機(jī)制僅僅依賴文件中關(guān)鍵字的出現(xiàn)頻率，導(dǎo)致搜索準(zhǔn)確性較差，具有一定誤差.同年，Xia等人提出了基于樹結(jié)構(gòu)的動(dòng)態(tài)多關(guān)鍵字密文搜索方案[21]，論文利用向量空間模型構(gòu)建樹型索引結(jié)構(gòu)，并利用深度優(yōu)先搜索方案進(jìn)行關(guān)鍵字搜索.2017年，Song等人提出支持全文檢索的密文搜索方案[22]，他們使用布隆過濾器(bloom filter)作為加密索引，并且提出了索引關(guān)鍵字熵的概念來計(jì)算搜索令牌中關(guān)鍵字和文件的相關(guān)度.同年，Shen等人提出了一個(gè)基于RSA和ElGamal加密算法的相關(guān)度排序方案[23].方案利用高階聚類索引(hierarchical clustering index)構(gòu)造索引結(jié)構(gòu)來提高搜索效率.為了提高安全性，方案中權(quán)值的計(jì)算由服務(wù)器執(zhí)行，結(jié)果的排序由用戶執(zhí)行，大大提高了搜索效率.在上述方案中，當(dāng)文件集合的大小呈指數(shù)增長(zhǎng)時(shí)，搜索時(shí)間也成線性增長(zhǎng).

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

2.1 同態(tài)密碼體制

本方案的構(gòu)建基于同態(tài)密碼體制，主要應(yīng)用Paillier[24]以及Goldwasser-Micali(GM)加密方法[25].上述2個(gè)方法均支持加法同態(tài)性，即給定2個(gè)密文Enc(m1)和Enc(m2)，應(yīng)用加同態(tài)操作可以得到2個(gè)明文相加之后的密文Enc(m1+m2).

詳細(xì)來講，Paillier同態(tài)加密算法由3個(gè)函數(shù)組成：

1)P.Gen(1k).輸入安全參數(shù)1k，隨機(jī)選擇2個(gè)k位素?cái)?shù)P和Q，并置N=PQ.隨機(jī)選擇一個(gè)數(shù)g，滿足gcd(L(gλ(N)modN2),N)=1，其中函數(shù)L(u)=(u-1)/N，λ(N)=lcm(P-1,Q-1)，選擇一個(gè)隨機(jī)數(shù)a∈R令h=aNmodN2，可知h在模N2下的階為λ(N).加密系統(tǒng)公鑰PKP為(N,g,h)，私鑰SKP為(P,Q).

2)P.EncPKP(m).輸入消息m∈N，選擇隨機(jī)數(shù)r∈N，計(jì)算密文[m]=gmhrmodN2.

3)P.DecSKP([m]).輸入密文c∈計(jì)算明文m=(L([m]λ(N)modN2)/L(gλ(N)modN2)) modN.

除此之外，Lipmaa等人在2005年提出Paillier雙重加密的方法[26]，設(shè)‖m‖為雙重加密之后的密文，其中明文m1滿足m∈N2，則Paillier雙重加密系統(tǒng)滿足如下性質(zhì)：‖[m1]‖[m2]=‖[m1][m2]‖=‖[m1+m2]‖.

同樣，GM加密算法包含3個(gè)函數(shù)：

1)GM.Gen(1k).輸入安全參數(shù)1k，選擇2個(gè)隨機(jī)k-bit素?cái)?shù)P和Q，并置N=PQ.選取模n的一個(gè)二次非剩余δ∈滿足雅可比符號(hào)公鑰PKGM=(δ,n)，私鑰是SKGM=(P,Q).

2)GM.EncPKGM(m).輸入消息m∈(0,1)，選擇隨機(jī)數(shù)r∈N，計(jì)算密文‖m‖=r2δmmodn.

3)GM.DecSKGM(‖m‖).輸入密文‖m‖∈計(jì)算明文

GM算法的明文空間為1位，并且[m]指的是一位比特值m利用GM方法加密之后的密文.GM的密鑰對(duì)表示為KGM=(PKGM,SKGM).GM方法的同態(tài)性表示為‖m1‖‖m2‖=‖m1⊕m2‖.

2.2 TF-IDF加權(quán)技術(shù)

為了能夠?qū)崿F(xiàn)搜索結(jié)果的相關(guān)度排序，本文使用TF-IDF加權(quán)技術(shù)[27]來計(jì)算某次搜索請(qǐng)求中匹配文件的相關(guān)度權(quán)值.TF-IDF加權(quán)技術(shù)是一種用于信息檢索與數(shù)據(jù)挖掘的常用加權(quán)技術(shù)，用以評(píng)估某個(gè)關(guān)鍵詞對(duì)于一個(gè)文件集或一個(gè)語料庫(kù)中的其中一份文件的重要程度.TF-IDF加權(quán)技術(shù)主要基于2個(gè)獨(dú)立的參數(shù)：詞頻(term frequency， TF)以及逆向文件頻率(inverse document frequency， IDF).

定義1. 詞頻.詞頻指的是某一個(gè)給定的關(guān)鍵字ti在某個(gè)文件d中出現(xiàn)的頻率，可表示為

(1)

定義2. 逆向文件頻率.逆向文件頻率是一個(gè)詞語在整個(gè)文件集中的普遍重要性的度量，可表示為

(2)

其中|D|表示總文件數(shù)目，j表示含有關(guān)鍵字ti的文件數(shù)目.本文采用式(3)來權(quán)衡關(guān)鍵字ti在文件d中的相關(guān)度：

(3)

2.3 兩方安全密文比較協(xié)議

本文利用文獻(xiàn)[28]中的兩方安全密文比較協(xié)議來作為方案排序協(xié)議構(gòu)建模塊.協(xié)議的交互雙方中一方持有2個(gè)利用Paillier加密方案加密的密文，其需要在不解密的情況下比較2個(gè)密文對(duì)應(yīng)的明文值的大小.協(xié)議要求在比較過程中不泄露任何關(guān)于明文的信息.現(xiàn)如今的方法中不存在有效的方案使其能夠在上述調(diào)前的情況下比較2個(gè)密文的大小.因此，需要另一方與其配合進(jìn)行比較協(xié)議.

詳細(xì)來說，假設(shè)A和B為交互雙方，其中A擁有密文[a]←P.EncPKP(a)和[b]←P.EncPKP(b)，B擁有私鑰SKP.比較協(xié)議的目標(biāo)是在不向任意一方揭示a,b明文的情況下，判定2個(gè)長(zhǎng)度為l位的數(shù)值a,b的大小.協(xié)議主要思想是計(jì)算2l+b-a(l+1)并驗(yàn)證第l+1位比特值來判定a,b的大小.如果等于1，則a≤b，否則a>b.協(xié)議結(jié)束之后，A得到比較結(jié)果的密文，而B不會(huì)得到任何有用信息.方案在誠(chéng)實(shí)并好奇敵手模型下被證明滿足語義安全.

2.4 Batcher排序網(wǎng)絡(luò)

Batcher排序網(wǎng)絡(luò)[29]能夠?qū)⒁粋€(gè)包含N個(gè)元素的數(shù)組進(jìn)行高效排序，可看作是一個(gè)具有O((logN)2)個(gè)連貫層級(jí)的排序算法，每個(gè)層級(jí)要比較O(N)對(duì)元素.具體來說，如圖1所示，設(shè)Ai是第i層的序列，其中Ai{j}為序列Ai的第j個(gè)元素.每一個(gè)層級(jí)i輸入Ai，輸出Ai+1，其中i層被指定需要排序的元素對(duì)在Ai+1中的是有序的.例如A2{1}和A2{2}包含有序的A1{1}和A1{2}，A2{3}和A2{4}包含有序的A1{3}和A1{4}.pairi表示層級(jí)i中需要排序的元素對(duì)集合，pairi.next表示下一個(gè)需要排序的元素對(duì)集合.

Fig. 1 An illustration of Batcher sort procession圖1 Batcher排序?qū)嵗?/p>

圖1為Batcher排序網(wǎng)絡(luò)實(shí)例，輸入序列A1={3,6,7,1,2,9,5,8}，首先將序列分為前半部分和后半部分，2個(gè)子序列同時(shí)進(jìn)行奇偶排序，最終得到A4={1,3,6,7,2,5,9,8}.隨后，對(duì)整個(gè)序列進(jìn)行奇偶?xì)w并，得到A6={1,3,2,5,6,7,8,9}，最后將相鄰元素進(jìn)行鄰近排序，得到最終的排序之后的序列A7={1,2,3,5,6,7,8,9}.本文利用Batcher排序網(wǎng)絡(luò)來實(shí)現(xiàn)搜索結(jié)果排序.

3 MES-RR方案

MES-RR由3類實(shí)體構(gòu)成：用戶U、云存儲(chǔ)服務(wù)器S以及協(xié)同服務(wù)器coS.其中，用戶U為數(shù)據(jù)擁有者，云存儲(chǔ)服務(wù)器S為向用戶提供數(shù)據(jù)存儲(chǔ)服務(wù)，根據(jù)用戶特搜索定請(qǐng)求完成對(duì)應(yīng)的搜索操作，協(xié)同服務(wù)器coS為輔助服務(wù)器，協(xié)助云存儲(chǔ)服務(wù)器S完成多關(guān)鍵字搜索結(jié)果的排序.

在本場(chǎng)景中，數(shù)據(jù)以文件的形式進(jìn)行組織，每個(gè)文件都帶有若干個(gè)對(duì)應(yīng)的關(guān)鍵字.使用“令牌”來描述用戶的請(qǐng)求.例如，在進(jìn)行搜索時(shí)，用戶U首先生成一個(gè)搜索令牌，并發(fā)送給服務(wù)器S.服務(wù)器S使用該令牌作為輸入來執(zhí)行搜索算法.隨后服務(wù)器S在協(xié)同服務(wù)器coS的協(xié)助下完成搜索結(jié)果的排序.由于方案只關(guān)注文件的標(biāo)識(shí)和關(guān)鍵字索引，因此文件的類型與大小不會(huì)對(duì)性能產(chǎn)生影響.

3.1 方案模型

由圖2可以看出，方案主要包含4個(gè)階段：文件預(yù)處理階段、搜索令牌生成階段、搜索排序階段以及搜索結(jié)果返回階段.用戶U將文件和索引加密后，外包至服務(wù)器S端進(jìn)行存儲(chǔ)，用戶U選擇若干關(guān)鍵字進(jìn)行集合搜索時(shí)，根據(jù)關(guān)鍵字集合生成對(duì)應(yīng)的搜索令牌發(fā)送給服務(wù)器S，服務(wù)器S在加密索引上執(zhí)行搜索操作，得到每個(gè)關(guān)鍵字對(duì)應(yīng)的密文集合，對(duì)密文集合進(jìn)行對(duì)應(yīng)的集合操作，并與協(xié)同服務(wù)器coS共同進(jìn)行搜索結(jié)果排序.隨后服務(wù)器S將排序后的搜索結(jié)果返回給用戶，用戶可以根據(jù)該搜索結(jié)果來選擇相應(yīng)的文件.

Fig. 2 Scheme architecture圖2 方案架構(gòu)

3.1.1 形式化定義

MES -RR由6個(gè)多項(xiàng)式時(shí)間算法或協(xié)議組成，即MES-RR=(KeyGen,Setup,SrchToken,Search,Sort,Dec)，具體描述如下：

1) 密鑰生成算法(K,SK,PK)←KeyGen(1k).由用戶U執(zhí)行，生成用戶對(duì)稱密鑰K以及公私鑰PK,SK.

2) 初始化算法(γ,c)←Setup(K,PK,F).由用戶U執(zhí)行，用于初始化安全索引結(jié)構(gòu)并對(duì)要上傳的數(shù)據(jù)進(jìn)行加密.算法輸入密鑰K,PK和數(shù)據(jù)文件集合F，輸出加密索引γ和密文文件集合C.

3) 搜索令牌生成算法τ←SrchToken(K,W).由用戶U執(zhí)行，用于生成搜索令牌τ.算法輸入密鑰K和關(guān)鍵字集合W，輸出搜索令牌τ.

4) 搜索算法IW←Search(γ,T).服務(wù)器S執(zhí)行，用于實(shí)現(xiàn)搜索.算法輸入加密索引γ和搜索令牌τ，輸出文件標(biāo)識(shí)集合IW.

3.1.2 安全模型

與經(jīng)典的密文搜索方案的安全模型不同，MES-RR的安全模型中包括2個(gè)不合謀的服務(wù)器：服務(wù)器S以及協(xié)同服務(wù)器coS，均為滿足“誠(chéng)實(shí)但好奇”模型的半可信實(shí)體，即具有可以分析用戶的搜索過程的能力，但是不會(huì)試圖共謀來獲取用戶數(shù)據(jù).服務(wù)器S會(huì)誠(chéng)實(shí)地為用戶提供文件存儲(chǔ)服務(wù)，并且不會(huì)主動(dòng)更改或損壞用戶的數(shù)據(jù)，但可能試圖查看、分析或使用用戶的數(shù)據(jù)、索引和令牌信息；協(xié)同服務(wù)器coS配備了用于保存密鑰的密碼處理器，僅僅進(jìn)行輔助工作，不會(huì)獲得任何有用數(shù)據(jù)，并且2個(gè)服務(wù)器之間不會(huì)共謀.具體來說，在MES-RR安全模型中，S得到加密的文件集合以及安全索引的情況下，響應(yīng)用戶發(fā)送的搜索請(qǐng)求，并通過的coS的協(xié)助，對(duì)搜索結(jié)果按照相關(guān)度進(jìn)行排序，并返回給用戶.在上述過程中，S能夠?qū)W習(xí)到文件的個(gè)數(shù)以及在倒排索引中關(guān)鍵詞的個(gè)數(shù)，以及在多項(xiàng)式次搜索過程中用戶的每一次搜索令牌信息.coS只能學(xué)習(xí)到文件的個(gè)數(shù)以及用戶進(jìn)行搜索請(qǐng)求的時(shí)間.然而，coS不會(huì)得到任何有關(guān)搜索內(nèi)容的信息.

文獻(xiàn)[5]曾提到，目前已知的大多數(shù)高效的密文搜索方案均或多或少泄露了用戶的私有信息，諸如用戶的搜索模式訪問模式等.因此在本方案中，將方案在執(zhí)行的過程中用戶向服務(wù)器所泄露的信息抽象成一組泄露函數(shù)L1,L2和L3來描述在方案執(zhí)行期間向服務(wù)器S和協(xié)同服務(wù)器coS泄露的信息，分別代表初始化過程，搜索過程以及排序協(xié)議中泄漏的信息.并在這些泄露函數(shù)存在的條件下給出安全性的定義.其主要目標(biāo)是證明，所有具有多項(xiàng)式時(shí)間計(jì)算能力(probabilistic polynomial-time, PPT)的敵手都無法從數(shù)據(jù)和查詢中獲取到任何信息，除了在泄露函數(shù)中所刻畫的之外.以下為方案的安全性定義.

定義3. IND-CKA2安全性.設(shè)AS和Ac oS為2個(gè)自適應(yīng)敵手，分別代表方案中的服務(wù)器S與協(xié)同服務(wù)器coS，自適應(yīng)表示敵手可以根據(jù)之前的質(zhì)詢結(jié)果來發(fā)起新的質(zhì)詢.view為敵手在實(shí)驗(yàn)過程中所能夠收集到的所有信息.Sim1和Sim2為2個(gè)具有多項(xiàng)式時(shí)間計(jì)算能力的模擬器，L1,L2和L3為方案向AS和Ac oS泄露的信息構(gòu)成的泄漏函數(shù).

我們稱MES-RR方案滿足IND-CKA2安全性，當(dāng)且僅當(dāng)用戶不能區(qū)分與其交互的為真實(shí)的敵手還是模擬器，即當(dāng)且僅當(dāng)以下2個(gè)條件成立：

3.2 MES-RR詳細(xì)設(shè)計(jì)

本節(jié)給出了MES-RR的具體構(gòu)建方案.在MES-RR中，文件集合F和倒排索引δ為初始輸入.與文件索引不同的是，倒排索引是一種以關(guān)鍵字為起始的索引結(jié)構(gòu).每個(gè)關(guān)鍵字后面都存在一組包含該關(guān)鍵字的文件集合.方案中用到了多種數(shù)據(jù)結(jié)構(gòu)，如鏈表L、數(shù)組A和查找表T.值得說明的是，方案中所用到的查找表T是一種以key/value對(duì)為基本元素的數(shù)據(jù)結(jié)構(gòu)，其元素的形式為(σ,v)，其中σ表示鍵，v表示對(duì)應(yīng)于鍵σ的值.記號(hào)T[σ]表示在查找表T中鍵σ所對(duì)應(yīng)的元素值，T[σ]=v表示將鍵σ的元素值置為v.記號(hào)#T表示查找表T中的元素個(gè)數(shù).

初始化階段用戶生成用于加密文件以及生成安全索引結(jié)構(gòu)使用的密鑰K，以及Paillier同態(tài)加密算法的公私鑰(PKP,SKP)和GM加密算法的公私鑰(PKGM,SKGM).隨后將用戶的批量文件加密并生成加密索引，隨后將密文文件C，加密索引γ以及公鑰(PKP,PKGM)一同上傳至服務(wù)器S，并將密鑰對(duì)(PKP,SKP)和(PKGM,SKGM)利用密鑰分發(fā)算法分享給協(xié)同服務(wù)器coS.

隨后用戶構(gòu)建文件索引結(jié)構(gòu)，首先從他的文件集F中提取到所有的關(guān)鍵字集合W，計(jì)算每個(gè)關(guān)鍵字w在文件集F中針對(duì)所有文件的tf-idf相關(guān)度權(quán)值，并生成倒排索引δ，δ中每個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)長(zhǎng)度為N的數(shù)組Fw，數(shù)組Fw中的位置d中的元素代表了關(guān)鍵字w在文件d中相關(guān)度權(quán)值，如果權(quán)值為0則表示關(guān)鍵字w不存在文件d中.

δ中列的個(gè)數(shù)為M(w中關(guān)鍵字的個(gè)數(shù))行數(shù)為N(F中文件的個(gè)數(shù)).為了滿足后續(xù)密碼學(xué)運(yùn)算，用戶將每一個(gè)相關(guān)度權(quán)值映射到一個(gè)空間為Zn的整數(shù)值score之中，并將其用Paillier進(jìn)行加密(明文空間為Zn).因?yàn)镻aillier密文具有不可區(qū)分性，所以倒排索引δ不泄露任何關(guān)于關(guān)鍵字的文件個(gè)數(shù)的信息.隨后，用戶根據(jù)倒排索引δ構(gòu)造安全索引γ，安全索引γ包含2個(gè)數(shù)據(jù)結(jié)構(gòu)：查找表T以及搜索數(shù)組A.查找表T包含了系統(tǒng)中的所有關(guān)鍵字，同時(shí)表中的每個(gè)關(guān)鍵字都指向搜索數(shù)組中的一個(gè)鏈表.而在搜索數(shù)組A中，元素是以“文件/關(guān)鍵字”對(duì)的形式出現(xiàn)的，每個(gè)元素都是一個(gè)唯一的“文件/關(guān)鍵字”對(duì)，并通過以關(guān)鍵字為引導(dǎo)的鏈表進(jìn)行組織具體來說，令F,G和P為3個(gè)偽隨機(jī)函數(shù)，H為Hash函數(shù).K=(K1,K2,K3)為用戶生成的對(duì)稱密鑰.針對(duì)用戶的文件集合F和倒排索引δ，對(duì)其中的每個(gè)關(guān)鍵字w構(gòu)建一個(gè)鏈表Lw.每個(gè)鏈表都由#Fw個(gè)節(jié)點(diǎn)(N1,N2,…,N#fw)構(gòu)成，并且存儲(chǔ)在搜索數(shù)組A中的隨機(jī)位置.定義節(jié)點(diǎn)Ni的結(jié)構(gòu)為Ni=(idi,[scorei],addr(Ni+1)⊕H(PK3(w),ri),ri)，其中idi為文件fi的唯一標(biāo)識(shí)，文件中包含對(duì)應(yīng)的關(guān)鍵字，[scorei]是關(guān)鍵字w在文件fi中的相關(guān)度權(quán)值的Paillier密文：[scorei]←P.EncPKp(scorei).addr(N)表示節(jié)點(diǎn)N在數(shù)組A中的位置.鏈表Lw中的所有節(jié)點(diǎn)都使用H(PK3(w),ri)進(jìn)行異或加密，其中ri為儲(chǔ)存在節(jié)點(diǎn)中的隨機(jī)值，K3為偽隨機(jī)函數(shù)P的密鑰.數(shù)組A中未使用的節(jié)點(diǎn)都隨機(jī)利用0或1進(jìn)行填充.

對(duì)于每個(gè)關(guān)鍵字w，查找表T中的對(duì)應(yīng)元素以FK1(w)為鍵，以指向鏈表Lw頭節(jié)點(diǎn)的指針為值，其中K1為偽隨機(jī)函數(shù)的密鑰.指針使用GK2(w)進(jìn)行異或加密，其中K2是偽隨機(jī)函數(shù)G的密鑰.即：T[FK1(w)]=addr(N1)⊕GK2(w).值得說明的是，數(shù)組A和查找表T共同作為安全索引存儲(chǔ)至服務(wù)器S端.文件利用標(biāo)準(zhǔn)加密算法進(jìn)行加密，生成文件密文集合C={c1,c2,…,c#F}，同樣上傳至服務(wù)器S.

為了搜索某個(gè)關(guān)鍵字集合W={w1,w2,…,wn}，用戶需要首先生成一個(gè)搜索令牌τ并發(fā)送給服務(wù)器S.搜索令牌τ中包含了針對(duì)每個(gè)關(guān)鍵字wi的FK1(wi),GK2(wi)和PK3(wi)，即ti=(FK1(wi),GK2(wi),PK3(wi))，輸出搜索令牌τ=(t1,t2,…,tn).

對(duì)于每個(gè)關(guān)鍵字wi∈W，服務(wù)器S使用FK1(wi)作為鍵來在查找表T中找到加密的指針，然后使用GK2(w)來解密得到Lw的明文指針并定位到數(shù)組A中的節(jié)點(diǎn)，即α=T[t1]⊕t2=T[FK1(w)]⊕GK2(w)，其中α代表N1在A中的坐標(biāo)，最后使用PK3(w)和儲(chǔ)存在各自節(jié)點(diǎn)中的隨機(jī)值r來解密整個(gè)鏈表節(jié)點(diǎn)，即[idi,[scorei],addr(Ni+1)]=li⊕H(PK3(w),ri)，進(jìn)而得到針對(duì)關(guān)鍵字w的文件標(biāo)識(shí)符集合S={id1,[score1],id2,[score2],…,idm,[scorem]}.為了不在后續(xù)排序協(xié)議中泄露信息，服務(wù)器處理每個(gè)關(guān)鍵字wi對(duì)應(yīng)的搜索結(jié)果集合Si，最終得到所有關(guān)鍵字的集合{S1,S2，…,Sn}.對(duì)于集合中每個(gè)文件標(biāo)示符idj，對(duì)其對(duì)應(yīng)的全部關(guān)鍵字的權(quán)值密文[scorej]進(jìn)行累積相加，得到最終的權(quán)值ej，即因此交集為IW={id1,e1,id2,e2,…,idm,em}=S1∩S2∩…∩Sn，并集為IW={id1,ei d1,id2,ei d2,…,idm,ei dm}=S1∪S2∪…∪Sn.

圖3為搜索過程的示例.用戶想要搜索文件集中包含w1以及w3的文件，生成w1∪w3的搜索令牌τ=(t1,t2)，其中t1=(FK1(w1),GK2(w1),PK3(w1))，t2=(FK1(w3),GK2(w3),PK3(w3)).用戶將令牌發(fā)送給服務(wù)器S，服務(wù)器S以FK1(w1)為鍵，對(duì)應(yīng)到查找表T中加密的指針0⊕GK2(w1)，再利用GK2(w1)解密，得到搜索數(shù)組中鏈表的頭節(jié)點(diǎn)位置0的值l1，使用PK3(w1)和儲(chǔ)存在節(jié)點(diǎn)0中的隨機(jī)值r1來解密，得到(id2‖[score2]‖4)=l1⊕H(PK3(w1),r1)，即得到指向位置4的指針，繼續(xù)解密位置4，得到的指針指向了位置0，然后結(jié)束遍歷.對(duì)于w3服務(wù)器進(jìn)行相同的操作，最終所有包含關(guān)鍵字w1和w3的文件都可以被找到，提取出文件標(biāo)識(shí)符合和對(duì)應(yīng)權(quán)值密文，組成Sw1={id2,[score2]w1,id4,[score4]w1}，Sw3={id1,[score1]w3,id2,[score2]w3}然后服務(wù)器對(duì)于相同標(biāo)識(shí)符id2的權(quán)值密文進(jìn)行同態(tài)相加得到e2=[score2]w1⊕[score2]w3，從而得到最終搜索結(jié)果Iw1∩w3={id1,e1,id2,e2,id4,e4}.

搜索階段結(jié)束之后，服務(wù)器S得到搜索結(jié)果IW={id1,e1,id2,e2,…,idm,em}，即文件標(biāo)示符與對(duì)應(yīng)的相關(guān)度權(quán)值密文組成的二元組的集合.然而，由于權(quán)值由Paillier同態(tài)加密進(jìn)行加密，其隨機(jī)性導(dǎo)致密文并不會(huì)表達(dá)明文的順序，所以服務(wù)器S并不能通過權(quán)值的密文來得到排序之后的結(jié)果.為了實(shí)現(xiàn)結(jié)果排序，服務(wù)器S通過協(xié)同服務(wù)器coS的協(xié)助得到最終有序的搜索結(jié)果.然而，本文的安全模型定義不允許協(xié)同服務(wù)器coS獲得和文件有關(guān)的任何信息，因此為了不向其泄漏消息，在進(jìn)行協(xié)議之前服務(wù)器對(duì)IW進(jìn)行變換，將文件標(biāo)示符利用Paillier加密方法進(jìn)行加密，得到標(biāo)示符密文[idi]←P.EncPKp(idi)，并將[idi]替代集合中的idi，生成IW,1={[id1],e1,[id2],e2,…,[idm],em}.隨后服務(wù)器S與協(xié)同服務(wù)器coS對(duì)IW,1中的[idi],ei進(jìn)行兩兩比較并排序，排序以ei為主鍵.具體來說，對(duì)于Batcher排序網(wǎng)絡(luò)中每個(gè)層級(jí)i中pairsi對(duì)應(yīng)的每對(duì)元素([idx],ex,[idy],ey)，服務(wù)器S計(jì)算[z][2l]×[ex]×[ey]-1modn2(l>k)并對(duì)其進(jìn)行盲化處理：選擇r∈(0,1)l+k，計(jì)算[d][z]×[r] modn2，并發(fā)送[d]給coS.同樣，S與coS分別計(jì)算r′rmod 2l與d′←P.DecSKP[d] mod 2l，隨后雙方執(zhí)行DGK兩方安全比較協(xié)議[29]比較d′和r′的大小，DGK協(xié)議結(jié)束后，云存儲(chǔ)服務(wù)器得到比較結(jié)果的GM密文‖λ‖，滿足λ=1?d′≤r′.隨后，coS提取出d′的第l位比特值，記做dl，發(fā)送給S，同時(shí)，S提取出Ac oS的第l位比特值，記做計(jì)算‖v‖=‖dl‖×‖rl‖×‖λ‖，并與coS運(yùn)行比特重加密協(xié)議以及密文選擇協(xié)議[30]，得到重加密之后的排序好的圖4為協(xié)同排序過程示例.

Fig. 3 Searching procedure圖3 搜索過程

Fig. 4 Collaborated comparison procedure圖4 協(xié)同排序過程

3.3 詳細(xì)算法設(shè)計(jì)

本節(jié)詳細(xì)介紹MES-RR的算法與協(xié)議.在運(yùn)行之前應(yīng)該首先選擇確定所使用的公共參數(shù)，包括內(nèi)容：

選擇選擇偽隨機(jī)函數(shù):F{0,1}k×{0,1}*→{0,1}k、G:{0,1}k×{0,1}*→{0,1}*和P:{0,1}k×{0,1}*→{0,1}k；選擇Hash函數(shù):H{0,1}*→{0,1}*；選擇Paillier同態(tài)加密方法P=(P.Gen,P.Enc,P.Dec)以及GM加密方法GM=(GM.Gen,GM.Enc,GM.Dec).

3.3.1 密鑰生成算法

KeyGen(1k)→(SK,PK)由用戶U執(zhí)行，生成用戶密鑰以及加密算法公私鑰.主要步驟如下：

1) 調(diào)用P.Gen(1k)生成Paillier加密算法的公私鑰(PKP,SKp)；

2) 調(diào)用GM.Gen(1k)生成GM加密算法的公私鑰(PKGM,SKGM)；

3) 隨機(jī)選擇3個(gè)長(zhǎng)度為k位的數(shù)值K1,K2,K3；

4) 用戶U將生成的密鑰在本地進(jìn)行存儲(chǔ)，將(PKP,PKGM)發(fā)布給云存儲(chǔ)服務(wù)器S，并將(PKP,SKP,PKGM,SKGM)發(fā)送給協(xié)同服務(wù)器coS.

3.3.2 初始化算法

Setup(K,PK,F)→(γ,C)由用戶U執(zhí)行，用于生成安全索引結(jié)構(gòu)并對(duì)要上傳的數(shù)據(jù)進(jìn)行加密.創(chuàng)建有足夠空間的查找表T以及一個(gè)有足夠空間的搜索數(shù)組A.

1) 構(gòu)建倒排索引δ

從文件集F中提取關(guān)鍵字集合W，對(duì)于每個(gè)關(guān)鍵字wi∈W:

① 對(duì)于每個(gè)關(guān)鍵字wi∈W計(jì)算其在每個(gè)文件中的的TF-IDF相關(guān)度權(quán)值;

② 創(chuàng)建一個(gè)長(zhǎng)度為N的數(shù)組Fwi，將wi在文件r中權(quán)值插入數(shù)組Fwi中的位置d中.如果權(quán)值為0則表示這個(gè)關(guān)鍵字不存在文件d中.每個(gè)關(guān)鍵字后面都存在一組包含該關(guān)鍵字的文件集合;

③ 所有關(guān)鍵字的數(shù)組組成倒排索引δ，δ中列的個(gè)數(shù)為M(W中關(guān)鍵字的個(gè)數(shù))行數(shù)為N(F中文件的個(gè)數(shù)).

2) 構(gòu)建安全索引γ

創(chuàng)建有足夠空間的查找表T以及一個(gè)有足夠空間的搜索數(shù)組A.對(duì)于每個(gè)關(guān)鍵字w∈W：

① 將δ中每一個(gè)相關(guān)度權(quán)值映射到一個(gè)空間為Zn的整數(shù)值scorei之中，其中i為對(duì)應(yīng)的文件fi標(biāo)識(shí)，并將其用Paillier加密算法進(jìn)行加密(明文空間為Zn)，生成密文[scorei]←P.EncPKP(scorei)；

② 創(chuàng)建一個(gè)有#w個(gè)節(jié)點(diǎn)的鏈表Lw=(N1,N2,…,N#w)，節(jié)點(diǎn)的結(jié)構(gòu)定義為Ni=(idi,[scorei],addr(Ni+1)⊕H(PK3(w),ri),ri)，其中[scorei]是w在fi中的權(quán)值密文，ri為一個(gè)隨機(jī)的k位比特串，addrs(N#w+1)=addrs(N0)=0log #A.將鏈表中的節(jié)點(diǎn)存儲(chǔ)在搜索數(shù)組A的隨機(jī)位置；

③ 通過以下方式將鏈表Lw的頭節(jié)點(diǎn)的地址儲(chǔ)存在查找表T中：T[FK1(w)]=addr(N1)⊕GK2(w).

算法輸出γ=(A,T)為加密索引，C=(c1,c2,…,c#F)為密文集合.

3.3.3 搜索令牌生成算法

SrchToken(K,W)→τ由用戶執(zhí)行，用于用戶在搜索時(shí)生成搜索令牌.主要步驟如下：

1) 輸入對(duì)稱密鑰K和待搜索關(guān)鍵字集合W,對(duì)于每一個(gè)待搜索關(guān)鍵字wi∈W，計(jì)算ti=(FK1(wi),GK2(wi),PK3(wi))；

2) 輸出搜索令牌τ=(t1,t2,…,tn).

3.3.4 搜索算法

Search(γ,C,τ)→IW由服務(wù)器S執(zhí)行，用于實(shí)現(xiàn)搜索.對(duì)與搜索令牌中每一個(gè)ti∈τ，依次按以下步驟：

1) 計(jì)算α=T[t1]⊕t2=T[FK1(w)]⊕GK2(w)，找到關(guān)鍵字鏈表Lw的頭結(jié)點(diǎn)N1的坐標(biāo)，其中α代表N1在A中的坐標(biāo)值；

2) 查找節(jié)點(diǎn)N1=A[α1]，使用t3解密該節(jié)點(diǎn)，例如N1?(l1,r1)，計(jì)算id1,[score1],addr(N2)=l1⊕H(τ3,r1);

對(duì)于j≥2，重復(fù)2)中過程，直至αj+1為0.

3) 將得到的結(jié)果記為Si={id1,[score1],id2,[score2],…,idm,[scorem]}；

4) 針對(duì)集合關(guān)鍵字布爾搜索模式，處理每個(gè)關(guān)鍵字令牌對(duì)應(yīng)的搜索結(jié)果集合Si：

3.3.5 排序協(xié)議

1) 服務(wù)器將IW中的每個(gè)文件標(biāo)示符idi進(jìn)行加密，得到[idi]←P.EncPKP(idi)；

2) 生成IW,1={[id1],e1,[id2],e2,…,[idm],em}；

3) 服務(wù)器S與協(xié)同服務(wù)器coS利用Batcher排序網(wǎng)絡(luò)對(duì)IW,1中的ei進(jìn)行兩兩比較并排序，具體來說，對(duì)于每個(gè)層級(jí)i(總層級(jí)為(lbm)2，且1≤i≤(lbm)2-1)順序執(zhí)行以下步驟：

① 標(biāo)記IW,1的pairsi為([idx],ex,[idy],ey)：

Ⅰ.S計(jì)算[z][2l]·[ex]·[ey]-1modn2(l>k);

Ⅱ. 選擇r∈(0,1)l+k，并計(jì)算r′rmod 2l，計(jì)算并發(fā)送[d][z]·[r] modn2，給代理服務(wù)器coS;

Ⅲ.coS運(yùn)行P.Dec算法解密[d]→d,并計(jì)算d′dmod 2l;

Ⅳ. 利用DGK協(xié)議，S與coS聯(lián)合計(jì)算GM密文‖λ‖，滿足λ=1?d′≤r′;

Ⅴ.coS用GM加密方案加密dl并發(fā)送‖dl‖給S;

Ⅵ.S加密rl并計(jì)算‖v‖=‖dl‖×‖rl‖×‖λ‖;

Ⅶ.S與coS運(yùn)行比特重加密協(xié)議與密文選擇協(xié)議[23]，得到有序的pairsi:([idx],ex′,[idy],ey′);

Ⅷ.S將得到的重加密之后的有序([idx],ex′,[idy],ey′)存入Bathcer排序網(wǎng)絡(luò)中層級(jí)i+1的序列IW,i+1對(duì)應(yīng)位置.

② 將IW,1在層級(jí)i的下一組元素繼續(xù)執(zhí)行步驟(1)，直到IW,1完成層級(jí)i的比較.

3.3.6 解密算法

3.4 安全性分析

本節(jié)首先對(duì)本文提出的MSE-RR方案的安全性進(jìn)行概述，然后對(duì)其所具有的安全性進(jìn)行詳細(xì)的數(shù)學(xué)證明.

在接下來的內(nèi)容中，首先分析在方案的執(zhí)行過程中有哪些信息泄露給了用戶，然后給出泄露函數(shù)的形式化定義.

1) 初始化.定義安全索引γ=(T,A)和密文集合C，在初始化階段，服務(wù)器S可以獲知數(shù)組A的大小、T中的集合[id(w)]w∈W和每個(gè)文件[|f|]f∈F的長(zhǎng)度.將這些信息記為L(zhǎng)1，即：L1=(#A,[id(w)]w∈W,[|f|]f∈F).

2) 搜索.在多項(xiàng)式次搜索操作中，方案向服務(wù)器S泄露了搜索令牌中關(guān)鍵字w∈W的標(biāo)識(shí)id(w)，每個(gè)關(guān)鍵字標(biāo)識(shí)id(w)和包含關(guān)鍵字w的文件標(biāo)識(shí)之間的關(guān)聯(lián)，以及用戶的搜索歷史.具體來說，設(shè)Q為nq次多關(guān)鍵字搜索的搜索令牌集合Q={q1,q2,…,qnq}，lmax表示在集合Q中長(zhǎng)度最長(zhǎng)的搜索令牌，nq次搜索之后的搜索歷史可表示為一個(gè)二進(jìn)制四階的矩陣Qnq×nq×lmax×lmax.將這些信息記為L(zhǎng)2，即：

L2=([id(f)]f∈Fw,id(w),Qnq×nq×lmax×lmax)w∈W.

現(xiàn)在利用定理來證明方案在泄漏函數(shù)(L1,L2,L3)存在的情況下，在隨機(jī)語言模式下具有IND-CKA2安全性.

定理1. 若Paillier,GM加密方案是CPA安全的，F(xiàn)，G和P為偽隨機(jī)函數(shù)，并且DGK協(xié)議在隨機(jī)模型下可證明安全，則本文所提出的方案在隨機(jī)預(yù)言模型下針對(duì)自適應(yīng)敵手AS與Ac oS攻擊是安全的，即滿足IND-CKA2安全性.

證明. 在隨機(jī)語言模型下構(gòu)造2個(gè)模擬器Sim1和Sim2，能夠在僅獲得泄露函數(shù)中包括的內(nèi)容中的情況下，在理想游戲中通過模擬敵手AS與Ac oS的行為生成相應(yīng)的模擬值來與用戶U進(jìn)行交互.安全目標(biāo)是這些模擬值應(yīng)該和真實(shí)游戲中的相對(duì)應(yīng)的值具有不可區(qū)分性.

在進(jìn)行每次密文比較協(xié)議時(shí)，AS的view可表示為viewAs=(ex,ey,l,PKQR,PKP,r;‖λ‖,[zl]).給定(ex,ey,l,PKQR,PKP)，我們能夠構(gòu)建出一個(gè)能夠模擬AS的Sim1：

同理，Ac oS的view可表示為viewAc oS=(SKGM,SKP,‖z‖,‖λ‖)，其中SKGM是GM方案的私鑰，SKP是Paillier加密方案的私鑰.

給定(SKGM,SKP,‖z‖,[λ])，我們能夠構(gòu)建出一個(gè)能夠模擬Ac oS的Sim2：

由于Sim1和Sim2能夠從泄漏函數(shù)L3中獲取需要排序的文件的個(gè)數(shù)m，所以Sim1和Sim2能夠模擬每次密文比較協(xié)議中的AS與Ac oS，進(jìn)而模擬(logm)2層Bathcer排序網(wǎng)絡(luò).所以，給定泄漏函數(shù)L3的信息，Sim1和Sim2能夠像真實(shí)AS與Ac oS一樣應(yīng)答用戶的質(zhì)詢，不同的是其使用的是模擬值.

綜上所述，對(duì)于敵手AS，存在一個(gè)多項(xiàng)式時(shí)間的模擬器Sim1滿足2個(gè)分布式計(jì)算不可區(qū)分性：

對(duì)于敵手Ac oS，存在一個(gè)多項(xiàng)式時(shí)間的模擬器Sim2滿足2個(gè)分布式計(jì)算不可區(qū)分性：

因此，本文MES-RR方案在隨機(jī)預(yù)言模型下針對(duì)自適應(yīng)選擇關(guān)鍵字攻擊是安全的，即滿足IND-CKA2安全性.

證畢.

3.5 性能分析

本節(jié)將MES-RR方案與現(xiàn)有具有代表性的支持排序的多關(guān)鍵字密文搜索方案[15-16,20]進(jìn)行了比較.在本文中評(píng)估的指標(biāo)有以下6種：同態(tài)技術(shù)、搜索結(jié)果的準(zhǔn)確性(Accuracy)、排序機(jī)制(Rank Method)、用戶生成搜索令牌的時(shí)間復(fù)雜度ComU，服務(wù)器生成最終搜索結(jié)果的時(shí)間復(fù)雜度ComS以及安全性等.表1中IPS(inner scalar product)表示內(nèi)積相似性，N指的是文件個(gè)數(shù)，M指的是文件集合中關(guān)鍵字的個(gè)數(shù)，指的是搜索關(guān)鍵字個(gè)數(shù)，CKA-1和 CKA-2分別指指選擇關(guān)鍵字安全性和自適應(yīng)性選擇密文攻擊安全.時(shí)間復(fù)雜度均為漸進(jìn)的.

Table 1 Schemes Comparison表1 性能對(duì)比

搜索結(jié)果準(zhǔn)確性方面，由于文獻(xiàn)[15]中的方案僅僅基于內(nèi)積相似性來計(jì)算每個(gè)文件中匹配到的關(guān)鍵字的數(shù)量，以此來計(jì)算文件權(quán)值并對(duì)文件進(jìn)行排序.然而，因?yàn)檫@種方法失去了關(guān)鍵詞對(duì)于文件的重要性這一信息，所以結(jié)果具有一定的誤報(bào)率.文獻(xiàn)[20]中的方案基于位置敏感Hash函數(shù)來聚類相似文件.然而，LSH適用于相似性搜索但是同樣不能提供精確排序.本方案利用TF-IDF加權(quán)規(guī)則來計(jì)算關(guān)鍵字文件相關(guān)度權(quán)值，實(shí)現(xiàn)對(duì)于關(guān)鍵字的精確排序.

安全性方面，文獻(xiàn)[15]利用了啟發(fā)式方法來隱藏搜索模式和訪問模式，所以安全性不在比較范圍之內(nèi).文獻(xiàn)[16]基于全同態(tài)加密構(gòu)建搜索索引，安全性較高，方案假設(shè)一個(gè)單獨(dú)的服務(wù)器僅僅執(zhí)行搜索功能，并不能對(duì)結(jié)果進(jìn)行排序，服務(wù)器找到需要的密文文件以及權(quán)值，將其全部返回給用戶，用戶在本地基于TF-IDF進(jìn)行對(duì)搜索結(jié)果排序.文獻(xiàn)[20]中引入2個(gè)不共謀服務(wù)器模型，但是服務(wù)器之間的交互過程中，其中一個(gè)服務(wù)器能夠訪問每一個(gè)搜索結(jié)果的明文，這對(duì)于用戶的數(shù)據(jù)安全以及搜索模式和訪問模式造成了極大的威脅，存在信息泄露的隱患，安全性較弱.本方案基于同態(tài)加密算法對(duì)相關(guān)度權(quán)值進(jìn)行加密，使得服務(wù)器無需解密即可對(duì)權(quán)值密文進(jìn)行計(jì)算，從而在不獲取額外信息的前提下對(duì)搜索結(jié)果進(jìn)行排序.除此之外，本文方案中協(xié)同服務(wù)器僅僅在排序過程中起到了協(xié)助作用，在交互過程中得到的全部是密文，并不會(huì)得到任何有關(guān)搜索模式和用戶真實(shí)數(shù)據(jù)相關(guān)的信息,安全性方面較高.

效率方面，文獻(xiàn)[15]的搜索階段中時(shí)間復(fù)雜度為O(M2)，搜索令牌的大小O(M)，與文件集合關(guān)鍵字個(gè)數(shù)呈線性關(guān)系.為了響應(yīng)查詢請(qǐng)求，服務(wù)器需要進(jìn)行O(NM2)次計(jì)算，其中N是文件集中文件個(gè)數(shù).文獻(xiàn)[16]中為了實(shí)現(xiàn)排序，頻率信息由全同態(tài)加密方法進(jìn)行加密，導(dǎo)致服務(wù)期計(jì)算代價(jià)為O(qN+M2)，效率較其他方案相比較差，且方案不支持動(dòng)態(tài)更新.文獻(xiàn)[20]中的協(xié)同服務(wù)器中存儲(chǔ)復(fù)雜度是與文件集呈線性關(guān)系，存儲(chǔ)代價(jià)稍高.本方案中搜索過程中需要2個(gè)服務(wù)器進(jìn)行兩方安全交互計(jì)算，導(dǎo)致服務(wù)器的搜索復(fù)雜度為O(N(lbN)2)，略高于其他方案，但是本方案中用戶生成長(zhǎng)度為q的搜索令牌僅僅需要常數(shù)級(jí)O(q)的時(shí)間復(fù)雜度，與集合中文件數(shù)量和關(guān)鍵字?jǐn)?shù)量無關(guān)，與其他方案相比客戶端計(jì)算代價(jià)較低.在如今分布式云存儲(chǔ)環(huán)境下，如何降低客戶端存儲(chǔ)與計(jì)算代價(jià)為首要考慮問題，所以本方案在效率更適用于實(shí)際云存儲(chǔ)部署需求.

4 總 結(jié)

本文對(duì)多關(guān)鍵字密文搜索和搜索結(jié)果排序方法展開研究，提出一種雙服務(wù)器模型下支持相關(guān)度排序的多關(guān)鍵字密文搜索方案，在能夠保證高效地實(shí)現(xiàn)多關(guān)鍵字密文搜索的同時(shí)，實(shí)現(xiàn)對(duì)于搜索結(jié)果的排序.方案基于TF/IDF加權(quán)技術(shù)以及Paillier同態(tài)加密算法，構(gòu)建關(guān)鍵字相關(guān)度安全索引，優(yōu)化計(jì)算代價(jià)并降低了存儲(chǔ)復(fù)雜度；方案設(shè)計(jì)雙服務(wù)器模型，引入安全可信的協(xié)同服務(wù)器處理機(jī)制來構(gòu)造安全排序協(xié)議，在不向協(xié)同服務(wù)器泄露搜索模式與訪問模式的前提下，實(shí)現(xiàn)對(duì)于搜索結(jié)果的高效排序.在安全性方面，本文在誠(chéng)實(shí)與好奇的威脅場(chǎng)景下，構(gòu)建方案的安全模型，并對(duì)該方案的安全性進(jìn)行嚴(yán)格分析，結(jié)果表明在結(jié)果表明在有限泄漏函數(shù)存在的情況下，方案能夠在隨機(jī)語言模型下具有語義安全性.性能分析表明，與以往的支持搜索結(jié)果排序的多關(guān)鍵字密文搜索方案相比，本方案大大降低了存儲(chǔ)代價(jià)和訪問交互次數(shù)，適用于實(shí)際的云存儲(chǔ)環(huán)境.未來工作包括對(duì)提出的方案部署進(jìn)真實(shí)云環(huán)境進(jìn)行部署試驗(yàn)并在服務(wù)器交互次數(shù)和計(jì)算代價(jià)方面進(jìn)行進(jìn)一步提高.