支持?jǐn)?shù)據(jù)去重的可驗(yàn)證模糊多關(guān)鍵詞搜索方案*

魏國富, 葛新瑞, 于 佳,2,3

1.青島大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 青島266071

2.密碼科學(xué)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室, 北京100878

3.中國科學(xué)院信息工程研究所信息安全國家重點(diǎn)實(shí)驗(yàn)室, 北京100093

1 引言

隨著云計(jì)算的日益普及, 越來越多的用戶傾向于把自己的數(shù)據(jù)儲存在云服務(wù)器上, 以減少本地的儲存開銷和管理成本.EMC 的調(diào)查顯示, 云中 75% 的數(shù)據(jù)是重復(fù)的[1].一方面這會增加用戶的網(wǎng)絡(luò)帶寬成本, 另一方面也會浪費(fèi)云服務(wù)器的存儲資源.因此, 對云數(shù)據(jù)去重就顯得尤為重要.數(shù)據(jù)去重吸引了越來越多云服務(wù)器供應(yīng)商的注意力.數(shù)據(jù)去重[2–7](data deduplication) 是一項(xiàng)通過檢測并刪除重復(fù)數(shù)據(jù)以達(dá)到減少存儲資源浪費(fèi)的技術(shù).按數(shù)據(jù)處理時間, 數(shù)據(jù)去重可以分為在線去重(inline deduplication) 和后處理去重(post-process deduplication).在線去重指在數(shù)據(jù)存儲到存儲設(shè)備的同時進(jìn)行去重處理.后處理去重指在數(shù)據(jù)存儲到設(shè)備后統(tǒng)一進(jìn)行去重處理.在線去重相對來說使用更加廣泛, 該技術(shù)通過對比云服務(wù)器上存儲的數(shù)據(jù)和用戶計(jì)劃上傳的數(shù)據(jù), 檢測云服務(wù)器上是否已存在相同的文件, 如果目標(biāo)文件已存在, 云服務(wù)器則為當(dāng)前用戶分配目標(biāo)文件的權(quán)限, 若目標(biāo)文件不存在, 則允許當(dāng)前用戶上傳該文件.數(shù)據(jù)去重的提出大大的緩解了云服務(wù)器的存儲壓力.

數(shù)據(jù)存儲在云服務(wù)器后, 就脫離了用戶實(shí)際物理控制, 這可能會導(dǎo)致敏感數(shù)據(jù)的泄露.為了保護(hù)敏感數(shù)據(jù)的隱私性, 用戶在外包數(shù)據(jù)之前往往會對數(shù)據(jù)進(jìn)行加密, 數(shù)據(jù)以密文的形式存儲在云服務(wù)器上.雖然這可以保證數(shù)據(jù)的隱私性, 但也使得在密文文件上的搜索變的困難.為了解決這個問題, 可搜索加密[8–13](searchable encryption, SE) 的概念被提出了.為了實(shí)現(xiàn)在加密文件上的數(shù)據(jù)搜索, 用戶通常需要對文件提取關(guān)鍵詞, 并依據(jù)提取的關(guān)鍵詞為文件建立相應(yīng)的索引, 然后用戶將加密文件和索引一并上傳給云服務(wù)器.當(dāng)用戶想要搜索包含某些關(guān)鍵詞的文件時, 首先為關(guān)鍵詞生成搜索陷門, 然后上傳給云服務(wù)器.云服務(wù)器比較搜索陷門和索引信息, 返回給用戶所有相關(guān)的密文文件.用戶在接收到返回的密文文件后,利用私鑰解密密文得到相應(yīng)的明文文件.

在現(xiàn)實(shí)生活中, 當(dāng)用戶搜索包含某一關(guān)鍵詞的文件時, 可能會出現(xiàn)關(guān)鍵詞拼寫錯誤的問題.在這種情況下, 傳統(tǒng)的精確關(guān)鍵詞搜索方案[8–13]將無法返回用戶想要的文件.為了解決這個問題, 一些模糊關(guān)鍵詞搜索方案[14–20]被提出了.模糊搜索實(shí)現(xiàn)了在出現(xiàn)一定關(guān)鍵詞拼寫錯誤的情況下, 仍然最大程度上搜索到用戶最感興趣的文件.而目前已有的模糊關(guān)鍵詞搜索方案中大多假設(shè)了云服務(wù)器是誠實(shí)的, 不會返回錯誤文件給用戶.在云服務(wù)器可能出現(xiàn)錯誤的情況下, 驗(yàn)證返回文件的正確性就很有必要.與此同時, 在只能由數(shù)據(jù)所有者實(shí)現(xiàn)數(shù)據(jù)搜索的獨(dú)享場景中和由全部數(shù)據(jù)所有者共享數(shù)據(jù)的場景中, 在經(jīng)過長時間、大規(guī)模的使用云存儲服務(wù)后, 將不可避免地存在大量的冗余數(shù)據(jù).而云服務(wù)器和數(shù)據(jù)用戶作為可搜索加密方案的參與方, 要避免造成云服務(wù)器存儲資源和用戶網(wǎng)絡(luò)帶寬浪費(fèi)的行為.因此, 在可驗(yàn)證模糊關(guān)鍵詞搜索的基礎(chǔ)上是實(shí)現(xiàn)數(shù)據(jù)去重具有重要的實(shí)用價值.

本文提出了一種支持?jǐn)?shù)據(jù)去重的可驗(yàn)證模糊多關(guān)鍵詞搜索方案, 方案實(shí)現(xiàn)了以下功能:

(1) 支持?jǐn)?shù)據(jù)去重的搜索.為了實(shí)現(xiàn)數(shù)據(jù)去重, 利用收斂加密算法對文件進(jìn)行加密, 加密文件的密鑰是明文文件的哈希值.這就使得不同用戶的相同文件得到的密文一致, 從而在數(shù)據(jù)去重的情況下,實(shí)現(xiàn)了安全搜索.

(2) 支持模糊多關(guān)鍵詞的搜索.利用局部敏感哈希函數(shù)相似的輸入會得到相似的輸出的特點(diǎn), 實(shí)現(xiàn)了關(guān)鍵詞的模糊搜索.根據(jù)TF-IDF (term frequency inverse document frequency) 規(guī)則計(jì)算關(guān)鍵詞在包含它的文件中的權(quán)重, 根據(jù)權(quán)重實(shí)現(xiàn)對搜索結(jié)果的排序.

(3) 支持搜索結(jié)果可驗(yàn)證的搜索.利用偽隨機(jī)函數(shù)和在MAC 作用下生成的驗(yàn)證標(biāo)簽構(gòu)造查找表.通過比對查找表中的驗(yàn)證標(biāo)簽, 實(shí)現(xiàn)對搜索結(jié)果的驗(yàn)證.

2 相關(guān)工作

數(shù)據(jù)去重方案.Bellare 等[3]提出了基于消息的加密 (MLE), 利用 MLE 實(shí)現(xiàn)了安全去重.然而, 利用MLE 實(shí)現(xiàn)數(shù)據(jù)去重容易遭受窮舉攻擊.同時, 在加密文件時會產(chǎn)生大量的密鑰導(dǎo)致出現(xiàn)密鑰管理問題.為了解決收斂密鑰管理問題, Li 等[4]提出了一種新的數(shù)據(jù)去重系統(tǒng), 該方案采用多服務(wù)器的方式分發(fā)密鑰.Stanek 等[5]提出了一種支持?jǐn)?shù)據(jù)去重的加密方案, 把所有數(shù)據(jù)分為流行數(shù)據(jù)和非流行數(shù)據(jù).為流行數(shù)據(jù)和非流行數(shù)據(jù)提供不同級別的安全性, 但此方案只能在非隱私的流行數(shù)據(jù)中實(shí)現(xiàn)數(shù)據(jù)去重, 無法實(shí)現(xiàn)全部數(shù)據(jù)去重.

關(guān)鍵詞搜索方案.Song 等[8]第一次提出了可搜索對稱加密方案, 該方案采用了特殊的兩層加密方法, 通過順序掃描的方式搜索整個文件集合.但每次搜索必須掃描整個文件集合才能得到完整的搜索結(jié)果.Goh 等[9]提出了基于布隆過濾器構(gòu)建索引的關(guān)鍵詞搜索方案.對每個文件生成對應(yīng)的Bloom filter, 把文件中包含的關(guān)鍵詞通過哈希函數(shù)插入到布隆過濾器的對應(yīng)位置中.但由于布隆過濾器自身的特性, 所以搜索結(jié)果與真實(shí)值有一定差異.Curtmola 等[10]提出了兩個高效的基于倒排索引的關(guān)鍵詞搜索方案.同時給出了非適應(yīng)性和適應(yīng)性的定義.但提出的方案無法察覺云服務(wù)器欺騙的行為.這些方案支持多用戶搜索并實(shí)現(xiàn)了亞線性搜索.Wang 等[11]根據(jù)關(guān)鍵詞頻率提出了一個支持結(jié)果排序的關(guān)鍵詞搜索方案.以上方案均應(yīng)用于單關(guān)鍵詞搜索場景中.單關(guān)鍵詞搜索由于缺乏搜索精度導(dǎo)致返回的文件較多, 這會增加用戶的存儲和計(jì)算負(fù)擔(dān), 降低用戶的操作體驗(yàn).為了使用戶能夠高效的檢索數(shù)據(jù), 多關(guān)鍵詞搜索方案被提出了.例如, Cao 等[12]提出了一個隱私保護(hù)的多關(guān)鍵詞排序搜索方案.此方案采用內(nèi)積匹配相似性規(guī)則來測量文件與查詢關(guān)鍵詞之間的相似度.但此方案只適用于小規(guī)模數(shù)據(jù)集, 對中等規(guī)模以上數(shù)據(jù)集效率不高.Sun等[13]利用向量空間模型[21]和 MDB 樹提出了一個多關(guān)鍵詞排序搜索方案.Ding 等[22]提出了一個隱私保護(hù)的多關(guān)鍵詞搜索方案.此方案采用樹形結(jié)構(gòu)構(gòu)建索引并設(shè)計(jì)了一個隨機(jī)遍歷算法, 即使是相同的查詢關(guān)鍵詞也會產(chǎn)生不同的訪問路徑.但由二叉樹本身特性的限制, 索引樹的結(jié)構(gòu)較為復(fù)雜, 搜索時間耗費(fèi)較高.Peng 等[23]提出了一個支持多數(shù)據(jù)所有者場景的多關(guān)鍵詞排序搜索方案.方案中采用樹形結(jié)構(gòu)索引和TF-IDF 模型.通過整合每個數(shù)據(jù)所有者擁有的加密的基于樹的索引, 能夠在云服務(wù)器不知道索引內(nèi)容的情況下提高查詢效率.

模糊關(guān)鍵詞搜索方案.Li 等[15]提出了一個模糊關(guān)鍵詞搜索方案.此方案使用編輯距離來測量兩個關(guān)鍵詞之間的相似程度, 利用通配符技術(shù)來構(gòu)建模糊關(guān)鍵詞集.此方案雖然可以實(shí)現(xiàn)對關(guān)鍵詞的模糊搜索, 但是存儲的數(shù)據(jù)量較大.Kuzu 等[16]提出了一個模糊關(guān)鍵詞搜索方案.利用基于 Jaccard 距離的MinHash 技術(shù)實(shí)現(xiàn)模糊關(guān)鍵詞搜索.Fu 等[14]提出了一個多關(guān)鍵詞模糊排序搜索方案.此方案利用關(guān)鍵詞轉(zhuǎn)換和局部敏感哈希函數(shù)等技術(shù)實(shí)現(xiàn)了快速、高效的可搜索加密方案.但是方案中在對關(guān)鍵詞轉(zhuǎn)換時會產(chǎn)生亂序問題, 使得搜索結(jié)果存在一定的誤差.Wang 等[17]提出了一個支持范圍查詢的模糊關(guān)鍵詞搜索方案.此方案利用保序加密和局部敏感哈希函數(shù)等技術(shù)構(gòu)建索引.

可驗(yàn)證搜索方案.Chai 等[24]首次提出了一個可驗(yàn)證關(guān)鍵詞搜索方案.此方案使用基于哈希的索引樹, 要求服務(wù)器將檢索路徑的哈希序列作為證據(jù)一并返回給用戶, 用戶可根據(jù)證據(jù)對搜索結(jié)果進(jìn)行完整性和正確性驗(yàn)證.Kurosawa 等[25]首次提出了 UC-secure 模型下的可驗(yàn)證對稱加密方案, 能夠驗(yàn)證搜索結(jié)果是否被篡改.但此方案需要大量的計(jì)算開銷和存儲空間, 驗(yàn)證過程的計(jì)算開銷與文件數(shù)量是線性關(guān)系.Sun 等[26]提出了一個基于雙線性映射累加器樹的可驗(yàn)證連接關(guān)鍵詞搜索方案.但由于使用雙線性映射累加器, 所以驗(yàn)證過程的時間耗費(fèi)較大.Jiang 等[18]提出了一個可驗(yàn)證的多關(guān)鍵詞排序搜索方案, 利用一個特殊的數(shù)據(jù)結(jié)構(gòu)QSet 實(shí)現(xiàn)關(guān)鍵詞排序搜索.Ge 等[19]提出了一個可驗(yàn)證關(guān)鍵詞模糊搜索方案, 利用MAC 可驗(yàn)證機(jī)制來驗(yàn)證搜索結(jié)果的正確性.Zhu 等[20]提出了一個滿足UC-security 的可驗(yàn)證動態(tài)模糊關(guān)鍵詞搜索方案, 同方案 [26]類似, 由于使用基于公鑰密碼體制的 RSA 累加器, 所以驗(yàn)證過程的時間耗費(fèi)較大.Zhu 等[27]在單一數(shù)據(jù)所有者多數(shù)據(jù)用戶的場景下提出了一個可驗(yàn)證的搜索方案.此方案可以為可搜索對稱加密方案提供可驗(yàn)證性.方案中利用Merkle Patricia Tree (MPT) 和Incremental Hash 構(gòu)建了支持?jǐn)?shù)據(jù)更新的驗(yàn)證索引.

3 問題描述

3.1 系統(tǒng)模型

圖1 系統(tǒng)模型Figure 1 System model

如圖1 所示.系統(tǒng)模型中包含三個實(shí)體: 數(shù)據(jù)所有者, 數(shù)據(jù)用戶, 云服務(wù)器.數(shù)據(jù)所有者擁有一個文件集合, 為了保護(hù)數(shù)據(jù)隱私性, 需要將文件進(jìn)行加密.然后構(gòu)建安全索引和查找表, 再把密文文件、安全索引和查找表一同上傳給云服務(wù)器.數(shù)據(jù)用戶是擁有數(shù)據(jù)所有者分享的私鑰的一組用戶.當(dāng)要搜索包含某些關(guān)鍵詞的文件時, 首先根據(jù)關(guān)鍵詞生成陷門, 然后把陷門上傳給云服務(wù)器.云服務(wù)器在接收到授權(quán)用戶的陷門后, 根據(jù)安全索引進(jìn)行搜索, 然后返回搜索結(jié)果給授權(quán)用戶.授權(quán)用戶在接收到云服務(wù)器返回的加密文件和驗(yàn)證標(biāo)簽后, 對結(jié)果進(jìn)行驗(yàn)證, 若驗(yàn)證通過, 則接受文件, 否則, 則拒絕接受.

3.2 設(shè)計(jì)目標(biāo)

提出的方案滿足以下要求:

(1) 支持?jǐn)?shù)據(jù)去重.當(dāng)用戶想要上傳文件時, 云服務(wù)器對該文件進(jìn)行去重檢測, 若云服務(wù)器未儲存該文件, 則允許該文件上傳; 否則通知用戶該文件已存在, 并為當(dāng)前用戶分配該文件的訪問權(quán)限.

(2) 支持多關(guān)鍵詞模糊搜索.當(dāng)用戶出現(xiàn)關(guān)鍵詞拼寫錯誤時, 云服務(wù)器仍然能夠返回用戶最感興趣的文件.

(3) 支持對搜索結(jié)果的驗(yàn)證.當(dāng)云服務(wù)器返回不正確的結(jié)果, 在用戶對搜索結(jié)果驗(yàn)證時能夠識別出來.

(4) 支持隱私性保護(hù).在用戶上傳加密文件和安全索引后, 云服務(wù)器不能從加密文件和安全索引中得到關(guān)于明文文件和關(guān)鍵詞的信息.

4 預(yù)備知識

4.1 符號描述

方案用到的一些符號標(biāo)記如表1 所示.

4.2 相關(guān)度函數(shù)

在支持排序的可搜索加密方案中, TF-IDF 規(guī)則被廣泛用于衡量文件與關(guān)鍵詞之間的相關(guān)度.詞頻TF 表示一個給定關(guān)鍵詞在某一文件中出現(xiàn)的次數(shù), 一個關(guān)鍵詞的TF 值越大, 代表這個關(guān)鍵詞在這個文件中越重要; 逆向文檔頻率IDF 用來衡量一個關(guān)鍵詞的普遍重要性, 是通過將文件總數(shù)除以包含此關(guān)鍵詞的文件數(shù)獲得的.一個關(guān)鍵詞的IDF 值越大, 代表這個關(guān)鍵詞越重要.

表1 符號描述Table 1 Symbol description

以下是相關(guān)度函數(shù)中用到的一些標(biāo)識:

?fi,j- 關(guān)鍵詞wi在文件fj中出現(xiàn)的次數(shù);

? |fj| - 文件fj中關(guān)鍵詞的個數(shù);

?F(wi) - 包含關(guān)鍵詞wi的文件集合;

? |F(wi)| - 包含關(guān)鍵詞wi的文件數(shù);

? TFi,j- 關(guān)鍵詞wi在文件fj中的 TF 值;

? IDFi- 關(guān)鍵詞wi在文件集合中的 IDF 值.

wi在文件fj中的TF 值、IDF 值、相關(guān)度函數(shù)分別被定義為

4.3 布隆過濾器

布隆過濾器 (Bloom filter, BF)[9]是一種空間效率高的數(shù)據(jù)結(jié)構(gòu).它能夠判斷一個元素是否屬于某個集合.它利用一個m位的數(shù)組表示一個集合, 數(shù)組的所有位初始化為 0.若要把一個給定的集合S={a1,a2,··· ,an} 插入到布隆過濾器中, 可以利用l個獨(dú)立哈希函數(shù)H={hi|hi:S→m,1 ≤i≤l},分別對集合中的每個元素進(jìn)行l(wèi)次哈希映射, 把布隆過濾器中映射到的位置置為1.當(dāng)檢測一個元素q是否屬于集合S時, 通過計(jì)算l個哈希值得到l個布隆過濾器中的對應(yīng)位置, 若任意一位為0, 則q不屬于集合S; 否則, 認(rèn)為q屬于集合S.一個m位數(shù)組的布隆過濾器誤識率近似為時, 最優(yōu)誤識率為

4.4 局部敏感哈希函數(shù)

局部敏感哈希函數(shù)(locality-sensitive Hashing, LSH) 是在一種高維空間中求解近似或精確近鄰搜索(near neighbor search) 的算法.對于兩個相隔一定距離的相似輸入, LSH 函數(shù)能夠高概率得到相似的輸出.若一個哈希函數(shù)族H中任意兩個點(diǎn)x,y滿足:

? 若d(x,y)≤r1; Pr[h(x)=h(y)]≥p1;

? 若d(x,y)≥r1; Pr[h(x)=h(y)]≤p1;稱這個哈希函數(shù)族為(r1,r2,p1,p2)-sensitive.其中d(x,y) 表示點(diǎn)x和點(diǎn)y之間的距離.

方案中使用的是P-stable LSH 函數(shù)族.

? 當(dāng)p=1, 符合柯西分布, 定義為密度函數(shù)

? 當(dāng)p=2, 符合高斯分布, 定義為密度函數(shù)

P-stable LSH 函數(shù)定義為

其中a是一個d維的向量,b∈[0,w]是一個實(shí)數(shù), 對一個函數(shù)族來說,w是固定常數(shù).

4.5 關(guān)鍵詞轉(zhuǎn)換

因?yàn)榫植棵舾泄：瘮?shù)以向量作為輸入, 所以方案中使用向量表示關(guān)鍵詞, 通過一元模型把關(guān)鍵詞轉(zhuǎn)換成向量的形式.具體步驟如下:

(1) 關(guān)鍵詞轉(zhuǎn)換成一元模型.例如, 關(guān)鍵詞 “secure” 的一元模型表示是 {s1,e1,c1,u1,r1,e2}.s1表示關(guān)鍵詞中的第一個s,e2表示關(guān)鍵詞中的第二個e.

(2) 關(guān)鍵詞插入到對應(yīng)的關(guān)鍵詞向量中.對每個關(guān)鍵詞生成一個160 位長的向量, 其中26×5=130位表示字母, 剩余 30 位表示數(shù)字和符號.一個給定關(guān)鍵詞的每一個字母對應(yīng)在向量中的位置置為1.

4.6 收斂加密

收斂加密(convergent encryption)[6]可以在數(shù)據(jù)去重中提供數(shù)據(jù)機(jī)密性.它的特征是利用明文文件的哈希值作為文件加密的密鑰.文件加密密鑰也被稱為收斂密鑰.當(dāng)上傳文件時, 會利用文件生成驗(yàn)證標(biāo)簽, 上傳給云服務(wù)器用于數(shù)據(jù)去重檢測.若兩個文件相同, 則對應(yīng)的驗(yàn)證標(biāo)簽也會相同.一個收斂加密方案由以下四部分算法構(gòu)成:

? 密鑰生成算法: KeyGen(M) →K.輸入明文文件M, 輸出收斂密鑰K.一般使用哈希函數(shù)H1(M)=K來生成收斂密鑰;

? 文件加密算法: Enc(K,M)→C.輸入明文文件M和收斂密鑰K, 輸出密文文件C;

? 文件解密算法: Dec(K,C)→M.利用密文文件C和收斂密鑰K解密得到明文文件M;

? 標(biāo)簽生成算法: 利用另一哈希函數(shù)H2生成用于去重檢測的驗(yàn)證標(biāo)簽.

5 方案描述

5.1 算法描述

方案的核心過程如圖2 所示.首先假定一個對稱加密算法ε= {Gen,Enc,Dec}, 其中 Gen 為密鑰生成算法, Enc 為加密算法, Dec 為解密算法.

? 密鑰生成輸入一個安全參數(shù)m, 生成一個隨機(jī)的(m+m′) 位向量S, 兩個(m+m′)×(m+m′) 的可逆矩陣M1和M2, 其中m′位為虛擬值; MAC 密鑰k; 偽隨機(jī)變換函數(shù)密鑰rk; 加密收斂密鑰的密鑰ck.利用對稱加密算法中ε.Gen 生成對稱密鑰sk.輸出密鑰集合SK={S,M1,M2,k,rk,ck,sk}.

? 構(gòu)建索引

從P-stable LSH 函數(shù)族H= {h: {0,1}160→ {0,1}m} 中選定l個獨(dú)立 LSH 函數(shù).為文件fj,j=1,2,··· ,n構(gòu)建一個m位的布隆過濾器I:

(1) 從文件fj提取關(guān)鍵詞集Wfj={w1,w2,···},wi∈ 0,1160.

(2) 對關(guān)鍵詞集中的每個關(guān)鍵詞wi, 通過hj∈H,1 ≤j≤l插入關(guān)鍵詞權(quán)重 TF-IDF 值到相應(yīng)布隆過濾器I中.

圖2 方案的核心過程Figure 2 Core process of scheme

(3) 把布隆過濾器擴(kuò)展到 (m+m′) 位, 在剩余的m′位中插入隨機(jī)數(shù)αi,i=1,··· ,m′.

(4) 加密索引I.根據(jù)以下步驟把向量I分成兩個向量I′和I′′:

(a) 若sj∈S且sj為 1, 對每個元素ij∈I, 令否則, 選擇兩個隨機(jī)數(shù)和其中j=1,··· ,(m+m′).

(b) 用可逆矩陣M1和M2加密 {I′,I′′} 生成安全索引

(5) 構(gòu)建查找表T.查找表的構(gòu)造形式如圖3 所示.關(guān)鍵詞域?yàn)殛P(guān)鍵詞wi的模糊關(guān)鍵詞集的偽隨機(jī)變換, 其中模糊詞集是根據(jù)方案[15]中的構(gòu)造方法, 在編輯距離為1 的情況下構(gòu)造得到的.標(biāo)簽域?yàn)棣胕和 MACk(wi,vi) 的串聯(lián)值, 其中γi=ε.Encsk(vi),vi為關(guān)鍵詞wi在每個文件中是否出現(xiàn)的向量.若vi,j為1, 則表示第j個文件包含關(guān)鍵詞wi; 若為0, 則表示第j個文件不包含關(guān)鍵詞wi.

圖3 查找表 TFigure 3 Look-up table T

最后, 把所有文件的安全索引和查找表T上傳給云服務(wù)器.

? 文件上傳

在索引上傳完成后, 數(shù)據(jù)所有者開始上傳文件集合, 對文件集合中的每個文件f, 根據(jù)收斂加密方案的標(biāo)簽生成算法, 計(jì)算出上傳文件的去重驗(yàn)證標(biāo)簽ηf=H2(f) 上傳給云服務(wù)器用于數(shù)據(jù)去重檢測:

– 若云服務(wù)器上已經(jīng)存儲了該驗(yàn)證標(biāo)簽, 則通知用戶檢測結(jié)果并為其分配訪問權(quán)限.

– 若云服務(wù)器上沒有存儲該驗(yàn)證標(biāo)簽, 說明文件是首次上傳, 則存儲該驗(yàn)證標(biāo)簽并由用戶計(jì)算

出文件的收斂密鑰Kf=H1(f), 然后加密文件f得到密文c=EncKf(f) 和加密收斂密鑰Kf得到cKf=Encck(Kf).最后, 上傳密文c和收斂密鑰密文cKf給云服務(wù)器.

? 生成陷門

(1) 假設(shè)查詢關(guān)鍵詞集合Wq={w1,··· ,wt}, 為其生成一個m位的布隆過濾器.對于查詢關(guān)鍵詞wi,i=1,··· ,t, 在經(jīng)過關(guān)鍵詞轉(zhuǎn)換后, 通過相同的l個 LSH 函數(shù)hj∈H, 1 ≤j≤l, 插入到布隆過濾器中, 得到查詢向量Q.

(2) 把布隆過濾器擴(kuò)展到 (m+m′) 位, 在剩余的m′位中插入βj,j= 1,··· ,m′, 其中βj∈R{0,1}.

(3) 加密查詢向量Q.根據(jù)以下步驟把向量Q分成兩個向量Q′和Q′′:

(a) 若sj∈S且sj為0, 對每個元素qj∈Q, 令否則, 選擇兩個隨機(jī)數(shù)和滿足其中j=1,··· ,(m+m′).

(b) 用可逆矩陣M1,M2加密 {Q′,Q′′} 生成

(4) 對查詢關(guān)鍵詞wi∈Wq,i=1,··· ,t, 做偽隨機(jī)變換生成φrk(wi), 然后插入集合?(Wq) 中.

? 搜索

內(nèi)積的結(jié)果由大到小排序, 并返回給用戶前k個文件的密文.

(2) 對于集合?(Wq) 中的每一個φ(wi),i=1,··· ,t, 搜索查找表T中的關(guān)鍵詞域, 并返回對應(yīng)的 vtag 給用戶.

? 驗(yàn)證搜索結(jié)果

用戶接收到搜索結(jié)果后做如下驗(yàn)證:

(1) 解析標(biāo)簽 vtagi,i=1,··· ,t得到γi和 MACk(wi,vi).

(a) 對 vtagi,i= 1,··· ,t計(jì)算ε.Decsk(γi) 得到vi, 再計(jì)算 MAC′k(wi,vi), 然后與MACk(wi,vi) 作比, 若相同則進(jìn)行下一步驗(yàn)證, 否則拒絕接收.

(b) 計(jì)算v=v1∧v2∧···∧vt, 然后查看返回的加密文件集合, 檢驗(yàn)v中對應(yīng)位置是否為1,若都為1 則進(jìn)行下一步驗(yàn)證, 否則拒絕接收.

(2) 解密收斂密鑰密文得到Kf= Decck(cKf), 解密文件密文得到f= DecKf(cf), 然后用戶計(jì)算并比較Kf和若相同則接收, 否則拒絕接收.

5.2 安全性分析

定理1提出的方案滿足已知密文模型下的安全性.

證明:在已知密文模型中, 敵手不能根據(jù)文件密文、加密索引和陷門推斷明文的信息.由于對稱加密的安全性, 概率多項(xiàng)式時間的敵手不能以超過的概率區(qū)分一個文件的密文C是由明文A或者B加密得到的.而索引和陷門的不可區(qū)分性是基于安全kNN 加密[28]的不可區(qū)分性和在索引、陷門分裂過程中插入的隨機(jī)數(shù).通過引入隨機(jī)數(shù), 相同的搜索請求將會生成不同的查詢向量, 使得搜索請求具有不可區(qū)分性, 并且最后得到的相關(guān)度分?jǐn)?shù)的分布也不同.因此, 查詢的不可鏈接性得到了很好的保證.方案 [14]中查詢向量擴(kuò)展到了 (m+1), 只增加了一位隨機(jī)數(shù).在提出的方案中, 隨機(jī)數(shù)位數(shù)擴(kuò)展m′位, 使得相同的關(guān)鍵詞搜索的結(jié)果更加具有不可區(qū)分性.最終計(jì)算結(jié)果如下:

其中IT·Q里包含真實(shí)值和隨機(jī)值

定理 2提出的方案滿足已知背景模型下的安全性.

證明:令 Sim 是一個模擬器, 其模擬出的 viewV′與云服務(wù)器產(chǎn)生的 view 不可區(qū)分.以下為模擬過程:

? Sim 隨機(jī)選擇一個加密向量S′∈{0,1}m+m′, 兩個可逆矩陣MAC 密鑰k′, 偽隨機(jī)變換函數(shù)密鑰 rk′, 并生成加密收斂密鑰的密鑰 ck′, 加密索引向量的密鑰 sk′.令 SK′=

(2) 對每個關(guān)鍵詞生成陷門BF′, 以及

? Sim 生成索引I(?′):

(5) 最后Sim 再對每個關(guān)鍵詞生成模糊詞集, 并對準(zhǔn)確關(guān)鍵詞生成索引向量, 構(gòu)造查找表T′.

定理 3提出的方案滿足可驗(yàn)證性.

證明:假設(shè)A 是一個多項(xiàng)式時間內(nèi)的敵手, 他能給出一個偽造的使得其能通過驗(yàn)證算法.如果存在一個這樣的 A, 那么它將有悖于 MAC、哈希函數(shù)H和對稱加密算法ε的安全性.假設(shè)包含查詢關(guān)鍵詞的文件個數(shù)大于等于k, 即 |C(W)| ≥k, (Cf,vtag) 是正確的查詢結(jié)果, 其中Cf={c1,··· ,ck},W= {w1,··· ,wt} 為t個查詢關(guān)鍵詞的集合, 需要證明敵手 A 無法偽造正確的查詢結(jié)果,即時, 有以下兩種情況需要考慮:

(2) 文件cj沒有返回給用戶.首先敵手隨機(jī)選擇一個關(guān)鍵詞wi∈W, 為其生成一個N-bit 的向量敵手令然后把剩余的位置0.把偽造的返回給用戶.由于MAC 可保證消息的不可偽造性, 偽造一個MAC 值使其通過驗(yàn)證的概率是可忽略的.而且對稱加密算法滿足選擇明文攻擊安全性, 在不知密鑰sk 的情況下是不能偽造出一個正確的加密消息的.

綜上所述, 不存在多項(xiàng)式時間內(nèi)的敵手能夠打破方案的可驗(yàn)證性, 因此所提方案滿足可驗(yàn)證性.

5.3 功能比較與效率分析

表2 為本文方案與文獻(xiàn)[14]和文獻(xiàn)[2]的方案在功能上比較的結(jié)果.從表中可以看出, 文獻(xiàn)[14]不能支持?jǐn)?shù)據(jù)去重以及對搜索結(jié)果的可驗(yàn)證, 文獻(xiàn)[2]支持?jǐn)?shù)據(jù)去重, 雖然可以支持可驗(yàn)證, 但是只能驗(yàn)證返回的文件內(nèi)容正確與否, 不能驗(yàn)證文件是否包含查詢關(guān)鍵詞.而提出的方案能夠支持多關(guān)鍵詞模糊搜索, 能對搜索結(jié)果進(jìn)行排序, 實(shí)現(xiàn)對云中數(shù)據(jù)的去重, 還能驗(yàn)證返回結(jié)果是否包含搜索關(guān)鍵詞以及文件是否被篡改.

表2 功能比較Table 2 Functionality comparison

如表3 所示, 本文方案與文獻(xiàn)[14]和文獻(xiàn)[2]的方案在索引建立、搜索和驗(yàn)證階段進(jìn)行了效率比較.

表3 效率分析Table 3 Efficiency analysis

其中,t為搜索關(guān)鍵詞的個數(shù),k為返回的文件個數(shù).方案中生成一個索引向量需要O(m+m′) 的時間, 向量分裂需要O(m+m′) 的時間, 矩陣相乘需要O((m+m′)2) 的時間, 所以索引建立時間復(fù)雜度為O(N(m+m′)2).由于所提方案中的索引能夠?qū)崿F(xiàn)對搜索結(jié)果的排序, 所以索引建立上要比方案[2]耗時, 而且建立索引是線下完成的, 只需建立一次.所提方案中云服務(wù)器執(zhí)行搜索操作的時間耗費(fèi)為O(N(m+m′)2).由于在每個文件中進(jìn)行搜索時需要對兩個(m+m′) 位的向量執(zhí)行內(nèi)積運(yùn)算, 所以每個文件搜索需要O((m+m′)2) 的時間.驗(yàn)證返回文件是否被篡改需要O(k) 的時間, 驗(yàn)證返回文件是否包含搜索關(guān)鍵詞需要O(2t) 的時間, 所以驗(yàn)證搜索結(jié)果需要O(2t+k) 的時間.由于方案 [2]不能驗(yàn)證返回文件是否包含搜索關(guān)鍵詞, 所以驗(yàn)證效率為O(k).

6 結(jié)束語

提出一個支持?jǐn)?shù)據(jù)去重, 對搜索結(jié)果可驗(yàn)證的模糊多關(guān)鍵詞搜索方案.為了降低云服務(wù)器上數(shù)據(jù)冗余和減少用戶的網(wǎng)絡(luò)帶寬開銷, 根據(jù)收斂加密實(shí)現(xiàn)對云服務(wù)器上加密數(shù)據(jù)去重; 為了解決用戶搜索時出現(xiàn)的關(guān)鍵詞錯誤拼寫等問題, 利用局部敏感哈希函數(shù)實(shí)現(xiàn)對關(guān)鍵詞搜索的模糊處理; 為了驗(yàn)證搜索結(jié)果的正確性, 利用消息驗(yàn)證碼和偽隨機(jī)函數(shù)生成驗(yàn)證標(biāo)簽, 保證搜索結(jié)果的真實(shí)性.安全性分析和功能比較、效率分析顯示所提方案是安全、高效的.