支持可驗(yàn)證的密文模糊關(guān)鍵字檢索方案

姜 嬌，蔡林沁，韋鵬程，李 莉，3

1.重慶郵電大學(xué) 自動化學(xué)院，重慶400065

2.重慶第二師范學(xué)院 數(shù)學(xué)與信息工程學(xué)院，重慶400065

3.四川大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，成都610065

1 引言

如今，云計(jì)算作為一種具有廣闊應(yīng)用前景的計(jì)算模型，為人們提供了可伸縮的計(jì)算資源、高質(zhì)量的按需服務(wù)以及無處不在的網(wǎng)絡(luò)訪問。由于其方便性和靈活性，越來越多的數(shù)據(jù)所有者傾向于將數(shù)據(jù)存儲到云服務(wù)器中，以減少本地服務(wù)器上的存儲空間和管理開銷。同時(shí)數(shù)據(jù)所有者需要檢查數(shù)據(jù)是否正確存儲在云上[1-3]。此外，惡意云服務(wù)器或未授權(quán)用戶（如黑客）可能知道云數(shù)據(jù)，從而導(dǎo)致所有者的私人數(shù)據(jù)泄露。例如，2019 年，酒店連鎖巨頭喜達(dá)屋母公司萬豪國際酒店被黑客攻擊，導(dǎo)致超過500 萬個未加密的護(hù)照號碼和大約860 萬個加密信用卡號碼被盜。因此，保護(hù)云數(shù)據(jù)的隱私迫在眉睫。

為了保護(hù)數(shù)據(jù)隱私和避免未經(jīng)授權(quán)的訪問，數(shù)據(jù)在外包之前必須進(jìn)行加密。這使得傳統(tǒng)基于明文關(guān)鍵詞的搜索在云服務(wù)中不可用。如何能夠保護(hù)數(shù)據(jù)隱私的同時(shí)實(shí)現(xiàn)對加密云數(shù)據(jù)的搜索服務(wù)是至關(guān)重要的?？紤]到云端的海量數(shù)據(jù)和龐大的用戶群，如何同時(shí)達(dá)到高性能和系統(tǒng)可用性的要求是個極具挑戰(zhàn)的問題。一個簡單解決方法，是數(shù)據(jù)用戶從云服務(wù)器下載所有密文，然后在本地解密。然而，它將帶來巨大的網(wǎng)絡(luò)帶寬、存儲空間和計(jì)算開銷，實(shí)際上是不可行的。另一種可能的方法，是用戶向云服務(wù)器提供解密密鑰和查詢關(guān)鍵字，云服務(wù)器解密密文并對明文執(zhí)行搜索操作。顯然，這種方式會將數(shù)據(jù)暴露給云服務(wù)器，這是不可能的。為了解決這一問題，許多可搜索加密（SE）方案[4-13]被提出。SE允許數(shù)據(jù)用戶通過基于關(guān)鍵字的搜索有選擇地檢索存儲在云服務(wù)器上的加密文檔。

到目前為止，這些方案的絕大多數(shù)都假設(shè)云服務(wù)器是誠實(shí)但好奇的。但在真實(shí)的場景中，云服務(wù)器并非一直都是誠實(shí)的。為了節(jié)約計(jì)算開銷可能會返回?zé)o效的搜索結(jié)果。因此，用戶有必要對搜索結(jié)果進(jìn)行驗(yàn)證。文獻(xiàn)[14]方案提出了一種UC安全的可驗(yàn)證的對稱可搜索加密方案。該方案首先通過引入隱私和可靠性的概念，確定了可驗(yàn)證SSE 方案對主動對手的安全性。驗(yàn)證的計(jì)算成本與文檔數(shù)量成線性關(guān)系，且該方案只能支持精確的關(guān)鍵字搜索。因此需要設(shè)計(jì)一種支持模糊關(guān)鍵字搜索的方案。文獻(xiàn)[15]方案首先提出了基于加密云數(shù)據(jù)的模糊關(guān)鍵字搜索方案。在該方案中，利用編輯距離來量化關(guān)鍵詞的相似度。但該方案不考慮搜索結(jié)果的驗(yàn)證問題。文獻(xiàn)[16]方案提出了第一種可驗(yàn)證的模糊關(guān)鍵字搜索方案，該方案不僅能夠?qū)用軘?shù)據(jù)進(jìn)行模糊關(guān)鍵字搜索，而且能保護(hù)關(guān)鍵字的隱私性和搜索結(jié)果的可驗(yàn)證性。文獻(xiàn)[17]方案提出了一種可驗(yàn)證的動態(tài)模糊關(guān)鍵字搜索方案，該方案具有抗惡意攻擊的UC安全特性。由于采用基于公鑰系統(tǒng)的RSA累加器對搜索結(jié)果進(jìn)行認(rèn)證，驗(yàn)證過程耗費(fèi)了大量的時(shí)間。

因此，為了構(gòu)建云計(jì)算環(huán)境下更加高效的關(guān)鍵詞搜索方案，提出了一種可驗(yàn)證的模糊關(guān)鍵詞搜索新方案，為了減少計(jì)算開銷和存儲空間，為每個模糊關(guān)鍵字集而并非每個模糊關(guān)鍵字生成一個索引向量并采用三節(jié)點(diǎn)哈希鏈表來構(gòu)建安全索引，并為每個模糊關(guān)鍵字集索引計(jì)算一個混淆函數(shù)對真實(shí)索引進(jìn)行加密混淆，使云端可通過模糊關(guān)鍵詞直接解密對應(yīng)索引，極大地提高了搜索的效率。同時(shí)，為了抵御云服務(wù)器的惡意攻擊，為每一個模糊關(guān)鍵字生成一個驗(yàn)證標(biāo)簽對實(shí)現(xiàn)了對返回結(jié)果的可驗(yàn)證性。

2 問題描述

2.1 系統(tǒng)模型

系統(tǒng)模型包含三個不同的實(shí)體：數(shù)據(jù)擁有者、數(shù)據(jù)使用者以及云服務(wù)器，如圖1所示。

圖1 系統(tǒng)模型框圖

一個非交互的可驗(yàn)證對稱可搜索加密方案是由下述六個多項(xiàng)式時(shí)間算法組成的集合。

（1）KeyGen(k)：算法由數(shù)據(jù)所有者執(zhí)行用來建立系統(tǒng)。輸入安全參數(shù)k，輸出密鑰集

（2）BuildIndex(K,F)：算法由數(shù)據(jù)擁有者執(zhí)行，輸入密鑰集K 和文件集F=(F1,F2,…,FN)，輸出一個安全索引I 和密文集C=(C1,C2,…,CN)。

（3）Trapdoor(K,w)：算法由用戶執(zhí)行，輸入密鑰集K 和查詢關(guān)鍵字w，輸出陷門Tw。

（4）Search(Tw,I,C)：算法由云服務(wù)器執(zhí)行，輸入陷門Tw、安全索引I 和密文集C，輸出集合C(w)和驗(yàn)證標(biāo)簽對(φ(w),tagw)，其中：

（5）Verify(K,Tw,C(w),(φ(w),tagw))：算法由用戶執(zhí)行，輸入密鑰集K、陷門Tw、集合C(w)以及驗(yàn)證標(biāo)簽對(φ(w),tagw)，輸出接受或拒絕。

（6）Dec(K,C(w))：算法由用戶執(zhí)行，輸入密鑰集K、集合C(w)，輸出明文文檔集F(w)。

2.2 威脅模型

在威脅模型中，認(rèn)為數(shù)據(jù)擁有者將誠實(shí)地加密文檔、構(gòu)建安全索引并計(jì)算身份驗(yàn)證標(biāo)簽，數(shù)據(jù)使用者將誠實(shí)地為查詢關(guān)鍵字產(chǎn)生陷門；而云服務(wù)器被視為不受信任的實(shí)體，它可能試圖從加密文件、安全索引和搜索陷門中學(xué)習(xí)其他有價(jià)值的信息。此外，為了節(jié)約計(jì)算成本，它可能會把無效的搜索結(jié)果返回給數(shù)據(jù)使用者。

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

該方案應(yīng)該滿足以下要求。

（1）關(guān)鍵字搜索：可以檢索包含查詢關(guān)鍵字的所有文檔。

（2）有效性：可以有效地返回搜索結(jié)果，并且在進(jìn)行結(jié)果驗(yàn)證時(shí)開銷很小。

（3）隱私保護(hù)：不能向云服務(wù)器泄露任何數(shù)據(jù)信息，如超出泄漏范圍內(nèi)的關(guān)鍵字和文檔的明文信息。

（4）搜索結(jié)果可驗(yàn)證性：可以驗(yàn)證搜索結(jié)果是否正確，以防止云服務(wù)器將不正確的搜索結(jié)果返回給數(shù)據(jù)使用者。

3 預(yù)備知識

加密工具對于設(shè)計(jì)加密方案非常重要[18-19]。下文闡述了所用到的加密工具、概念以及結(jié)構(gòu)。

3.1 對稱加密

一個對稱加密方案包括三個多項(xiàng)式時(shí)間算法SKE=(Gen,Enc,Dec)。算法Gen 通過輸入安全參數(shù)k得到密鑰sk；算法Enc 通過密鑰sk 加密明文F 得到密文C；算法Dec 通過密鑰sk 解密密文C 得到明文F。對稱加密方案應(yīng)該防止選擇明文攻擊。這里選擇符合上述要求的AES 加密算法對文檔進(jìn)行加密。

3.2 偽隨機(jī)函數(shù)和消息驗(yàn)證函數(shù)

偽隨機(jī)函數(shù)(PRF f)和偽隨機(jī)置換函數(shù)(PRP π)是多項(xiàng)式時(shí)間的可計(jì)算函數(shù)，它們與隨機(jī)函數(shù)之間沒有任何概率多項(xiàng)式時(shí)間上的區(qū)別。文中利用f 來盲化索引向量，用π 來打亂關(guān)鍵字的位置，且兩個函數(shù)的參數(shù)如下：

其中l(wèi) 為關(guān)鍵字的最大長度，k 為密鑰，N 為文檔數(shù)。

驗(yàn)證標(biāo)簽生成函數(shù)為：

對所選的消息攻擊[20]具有不可逆性以及消息不可偽造性。通過MAC 函數(shù)為消息生成一個身份驗(yàn)證標(biāo)簽來驗(yàn)證從云服務(wù)器返回的搜索結(jié)果的正確性。在本文中，選擇tag=MAC(k0,m)，其中k0為密鑰，m 為消息。

3.3 倒排索引

本文基于倒排索引[21]構(gòu)建索引表。TF-IDF[22]規(guī)則是一種加權(quán)統(tǒng)計(jì)詞頻的技術(shù)，用于度量關(guān)鍵詞和文件之間的關(guān)聯(lián)程度。當(dāng)關(guān)鍵詞在文檔集合中某個文件出現(xiàn)的次數(shù)越多，則關(guān)聯(lián)程度越高；但關(guān)鍵詞在該文件集合中出現(xiàn)的頻率越高，關(guān)聯(lián)程度越低。對文件ID(Cj)（表示加密文件Cj的標(biāo)識符）中所有關(guān)鍵詞wi，利用TF-IDF評分規(guī)則計(jì)算其相關(guān)性分?jǐn)?shù)sc：

其中，wi表示關(guān)鍵字，|I D(Cj)|表示文件的長度，ID(Cj)wi表示關(guān)鍵字wi在文件中出現(xiàn)的頻率，N 表示文件集合中的文件總數(shù)，cwi表示文件集合中出現(xiàn)關(guān)鍵字wi的頻率。為了找到更相關(guān)文檔，提高搜索的精度，只將文檔集合中某個文件的分?jǐn)?shù)sc 最高的前k 個關(guān)鍵詞加入索引。用v(wi)表示關(guān)鍵字wi的索引向量并令addri=wi。若文件Fj(1 ≤j ≤N)前k 個關(guān)鍵詞包含wi，則令v(wi)[j]=1；否則令v(wi)[j]=0。如表1所示。

表1 倒排索引

3.4 模糊集的構(gòu)造

為了減少模糊關(guān)鍵字集所占存儲空間，本文中用通配符“*”[23]代表每一個特定位置的所有編輯操作（替換、刪除和插入）。對于給定的關(guān)鍵字wi和編輯距離d，基于通配符的模糊關(guān)鍵字集可以表示為：

如編輯距離為1，關(guān)鍵字hello 的模糊集為：

3.5 安全索引

對于任意模糊集合Swi,d，可以計(jì)算混淆函數(shù)：

用以加密真實(shí)索引。利用偽隨機(jī)置換函數(shù)π 打亂關(guān)鍵字的真實(shí)位置，用偽隨機(jī)函數(shù)f 盲化索引向量v(wi)，得到πk1(wi)和安全索引：

對于任意模糊關(guān)鍵字wi,t∈Swi,d計(jì)算：

則對于任意模糊關(guān)鍵詞wi,a,wi,b∈Swi,d利用πk2(wi,a)，πk2(wi,b)均可以得到相同混淆函數(shù)：

因此，利用任意模糊關(guān)鍵詞wi,t∈Swi,d均可解密安全索引得到倒排索引：

4 所提方案及安全性分析

4.1 所提方案

當(dāng)數(shù)據(jù)使用者出現(xiàn)拼寫錯誤時(shí)，可驗(yàn)證精確關(guān)鍵字搜索方案不能返回相關(guān)文件。為了解決這個問題，在已有的可驗(yàn)證精確關(guān)鍵字搜索方案基礎(chǔ)上提出了一種可驗(yàn)證的模糊關(guān)鍵詞搜索（VFKS）新方案，具體步驟如下。

（1）KeyGen(k)：輸入安全參數(shù)k，輸出密鑰集K={ sk,k0,k1,k2}。其中sk ←SKE.Gen(1k)，為加解密文檔的密鑰；k0,k1,k2←{0 ,1}k，k0為MAC 的密鑰，k1為PRP π的密鑰，k2為PRF f 的密鑰。

（2）BuildIndex(K,F)：為了方便高效地構(gòu)建索引，通過擴(kuò)展倒排索引構(gòu)造了包含三個節(jié)點(diǎn)的鏈表作為索引，結(jié)構(gòu)如圖2所示。

（2.1）數(shù)據(jù)擁有者掃描整個文檔提取所有不同的關(guān)鍵字并構(gòu)建關(guān)鍵字集W。對于每一個關(guān)鍵字wi∈W，數(shù)據(jù)擁有者建立包含關(guān)鍵字wi的文件集F(wi)。

（2.2）根據(jù)文件集F(wi)，數(shù)據(jù)擁有者建立相應(yīng)倒排索引。若wi為文件Fj(1 ≤j ≤N)前k 個關(guān)鍵詞，則令v(wi)[j]=1；否則令v(wi)[j]=0。

（2.3）數(shù)據(jù)擁有者為每個關(guān)鍵字wi構(gòu)建模糊關(guān)鍵字集，Swi,d表示與wi編輯距離為d 的模糊關(guān)鍵字集，表示Swi,d中的關(guān)鍵字。

（2.4）數(shù)據(jù)擁有者加密所有文件C(wi)←SKE.Encsk(F(wi))。并計(jì)算Swi,d中每一個模糊關(guān)鍵字的πk1(wi,t)(1 ≤i ≤n,1 ≤t ≤ | Swi,d|)并將其存儲于第一個節(jié)點(diǎn)。數(shù)據(jù)擁有者計(jì)算Ev(wi)←f(Φ(wi))⊕v(wi)，并把Ev(wi)存儲在第二個節(jié)點(diǎn)。為Swi,d中所有關(guān)鍵字計(jì)算驗(yàn)證標(biāo)簽對(φ(wi,t),tagwi.t)，其中：并把它們存儲在第三個節(jié)點(diǎn)。

（2.5）最后，數(shù)據(jù)擁有者把這些鏈表存進(jìn)一個哈希表，作為安全索引I。

（3）Trapdoor(K,w′)：當(dāng)用戶想要搜索包含關(guān)鍵字w′的相關(guān)文件時(shí)，首先計(jì)算陷門：

然后將其送至云服務(wù)器。

（4）Search(Tw′,I,C)：云端查找Tw′={(πk1(w′1),πk2(w′1)),(πk1(w′2),πk2(w′2)),…,(πk1(w′t),πk2(w′t))}中所有πk1(w′i)，若在索引Iw′i={(πk1(wi,1),φ(wi,1)),(πk1(wi,2),φ(wi,2)),…,(πk1(wi,t),φ(wi,t))}中存在：

則找到對應(yīng)索引文件Ev(wi)與對應(yīng)證明(φ(wi,a),tagwi.a)，之后計(jì)算：

以解密安全索引Ev(wi)得到倒排索引v(wi)←f(Φ(wi))⊕Ev(wi)。若v(wi)[j]=1，云服務(wù)器在C(w′)中添加Cj；否則，不添加。最后云服務(wù)器返回C(w′)，(φ(wi,a),tagwi,a)和πk1(w′i)給數(shù)據(jù)用戶。

（5）Verify(K,C(w′),πk1(wi,1),Tw′,(φ(wi,t),tagwi.t))：數(shù)據(jù)使用者根據(jù)C(w′)得到v(w′)。若C(w′)中存在Cj，則v(w′)第j 個位置為1；否則為0。進(jìn)而得到Ev(w′)←f(Φ(w′))⊕v(w′)，其中：

最后檢查下式是否成立：

若成立，用戶接受搜索結(jié)果，反之拒絕。

（6）Dec(sk,C(w′))：數(shù)據(jù)用戶計(jì)算

F(w′)←SKE.Decsk(C(w′))(sk ∈K)

從而解密C(w′)。

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

4.2 安全性分析

定義（隱私性）若對任意的概率多項(xiàng)式時(shí)間PPT模擬器Sim有：

對任何PPT 敵手A 都是可忽略的，則稱該可驗(yàn)證對稱可搜索加密方案滿足隱私性。

這樣來區(qū)分真實(shí)游戲和模擬游戲，真實(shí)游戲由一個挑戰(zhàn)者和一個敵手A 來完成，而模擬游戲則由一個模擬器sim來完成。

真實(shí)游戲(Gamereal)：

敵手A 選擇一對文檔集和關(guān)鍵字集(F,W)，并將它們發(fā)送給挑戰(zhàn)者。

挑戰(zhàn)者根據(jù)密鑰生成和索引構(gòu)建算法計(jì)算密鑰集K 和(I,C)，并把(I,C)送至敵手A。

敵手A 選擇一個關(guān)鍵字w 并將其送至挑戰(zhàn)者。挑戰(zhàn)者把陷門Tw送至敵手A。敵手A 輸出b ∈{ }

0,1。模擬游戲(Gamesim)：

敵手A 選擇一對文檔集和關(guān)鍵字集(F,W)，并將它們發(fā)送給挑戰(zhàn)者。

挑戰(zhàn)者把 |F1|,| F2|,…, | FN|和l 送至模擬器sim。

模擬器sim計(jì)算(I′,C′)并送至挑戰(zhàn)者。

挑戰(zhàn)者把(I′,C′)送至敵手A。

（1）敵手A 選擇關(guān)鍵字w 并送給挑戰(zhàn)者。

（2）模擬器sim 根據(jù)PRP π 和PRF f 計(jì)算陷門T′w，并把T′w送至挑戰(zhàn)者。

（3）挑戰(zhàn)者把T′w送給敵手A。

敵手A 輸出b ∈{0 ,1}。

5 實(shí)驗(yàn)結(jié)果

5.1 性能比較

表2為本文方案同文獻(xiàn)[14-17]和[24]方案就索引構(gòu)建時(shí)間開銷、陷門生成時(shí)間開銷、搜索時(shí)間開銷以及驗(yàn)證開銷四個方面的有效性進(jìn)行比較；各方案的性能比較如表3所示。其中，N 為文檔數(shù)量，n 為精確關(guān)鍵字?jǐn)?shù)量，l 為精確關(guān)鍵字的最大長度，m 為模糊關(guān)鍵字的總數(shù)量，M為模糊關(guān)鍵字集Swi,d中的模糊關(guān)鍵字?jǐn)?shù)的最大值，M′為查詢關(guān)鍵字的模糊關(guān)鍵字?jǐn)?shù)，h 為索引樹的高度。

表2 有效性比較

表3 性能比較

在索引構(gòu)建階段，由于文檔數(shù)N、模糊關(guān)鍵字的總數(shù)量m 均大于精確關(guān)鍵字?jǐn)?shù)n，所以本文的VFKS方案的索引構(gòu)建有效性優(yōu)于文獻(xiàn)[14]和[15]方案。

本文搜索階段首先通過搜索πk1(w)可找到對應(yīng)加密索引。由于本文利用哈希表結(jié)構(gòu)而非方案[24]中所用鏈表結(jié)構(gòu)，故本文搜索階段時(shí)間復(fù)雜度為O(1)。此外本文利用了設(shè)計(jì)的混淆函數(shù)對真實(shí)索引進(jìn)行加密混淆，使云端可通過模糊關(guān)鍵詞直接解密對應(yīng)索引，而非文獻(xiàn)[24]方案中先利用模糊關(guān)鍵詞找到準(zhǔn)確關(guān)鍵詞，之后用戶利用返回關(guān)鍵詞再次構(gòu)造解密方案獲得索引。本文方案相較文獻(xiàn)[24]方案大幅簡化了搜索流程，提高了搜索效率。

綜合以上性能比較結(jié)果，在索引構(gòu)建、陷門生成、搜索以及結(jié)果驗(yàn)證階段，本文方案綜合性能優(yōu)于現(xiàn)存方案。

5.2 實(shí)驗(yàn)分析

為了保證所提方案的有效性，在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。從在線Enron 電子郵件數(shù)據(jù)庫[25]中選擇了10 000個數(shù)據(jù)作為測試數(shù)據(jù)。在實(shí)驗(yàn)中，整個方案采用Java 語言實(shí)現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)均在以Windows7（RAM 4 GB，CPU主頻2.30 GHz）下測得。

（1）索引構(gòu)建

在本文方案中，首先需要給每個關(guān)鍵字構(gòu)建對應(yīng)的模糊關(guān)鍵字集。構(gòu)建模糊關(guān)鍵字集的時(shí)間與關(guān)鍵字的數(shù)量有關(guān)。圖3 給出了在編輯距離d=1 時(shí)，本文方案和文獻(xiàn)[24]方案生成模糊關(guān)鍵字集的時(shí)間開銷的結(jié)果比較。

圖3 模糊關(guān)鍵字集構(gòu)造時(shí)間開銷

在模糊集構(gòu)建階段，由于本文方案使用通配符技術(shù)，極大減少了精確關(guān)鍵字對應(yīng)模糊集中的模糊關(guān)鍵字?jǐn)?shù)量，所以所需時(shí)間開銷遠(yuǎn)小于通過枚舉法來構(gòu)造模糊集的文獻(xiàn)[24]方案。

圖4給出了當(dāng)關(guān)鍵字?jǐn)?shù)量n=5 000 時(shí)，本文方案和文獻(xiàn)[24]方案在構(gòu)建安全索引時(shí)的時(shí)間開銷比較結(jié)果。兩方案的開銷都隨著文檔數(shù)的增加而增加，但本文方案增加幅度較小。由于本文方案模糊關(guān)鍵字?jǐn)?shù)量遠(yuǎn)小于文獻(xiàn)[24]方案，所以總體時(shí)間開銷遠(yuǎn)小于文獻(xiàn)[24]方案。

圖4 索引構(gòu)建時(shí)間開銷(n=5 000)

圖5 給出了當(dāng)文檔數(shù)量N=10 000 時(shí)，本文方案和文獻(xiàn)[24]方案在構(gòu)建安全索引時(shí)的時(shí)間開銷比較結(jié)果。兩方案的開銷都隨著關(guān)鍵字?jǐn)?shù)量的增加而增加，但本文方案增加幅度較小，而文獻(xiàn)[24]方案幾乎是線性增長且總體開銷遠(yuǎn)大于本文方案。

圖5 索引構(gòu)建時(shí)間開銷(N=10 000)

（2）陷門生成

在本文方案中，采用兩元組Tw=(πk1(w),πk2(w))作為陷門。只能由偽隨機(jī)函數(shù)f 和偽隨機(jī)置換函數(shù)π 來得到陷門的兩個偽隨機(jī)序列。函數(shù)π 的輸出長度為常數(shù)，函數(shù)f 的輸出長度和文檔數(shù)量有關(guān)。如圖6給出了陷門生成時(shí)間和關(guān)鍵字長度的關(guān)系（取1 000 次隨機(jī)測試的平均值）。隨著關(guān)鍵字長度的增加，陷門生成時(shí)間開銷幾乎線性增加。

圖6 本文方案陷門生成時(shí)間開銷

（3）搜索的有效性

在本文方案中，用了設(shè)計(jì)的混淆函數(shù)對真實(shí)索引進(jìn)行加密混淆，使云端可通過模糊關(guān)鍵詞直接解密對應(yīng)索引；而文獻(xiàn)[24]方案中要先利用模糊關(guān)鍵詞找到精確關(guān)鍵詞，之后用戶利用返回關(guān)鍵詞再次構(gòu)造解密方案獲得索引，搜索流程復(fù)雜、效率低。如圖7，對本文方案和文獻(xiàn)[24]方案在搜索階段的時(shí)間開銷進(jìn)行了描述（取100次隨機(jī)測試的搜索時(shí)間平均值）。搜索時(shí)間并未隨著關(guān)鍵字?jǐn)?shù)量的增加而增加，而是基本穩(wěn)定在0.08 ms附近，遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[24]方案所需的時(shí)間開銷。

圖7 搜索時(shí)間開銷

（4）驗(yàn)證的有效性

本文方案中，需要從云端驗(yàn)證tagwi,t=MAC(πk1(wi,1),πk1(w′),Ev(w′),C(w′),φ(wi,t))是否成立。驗(yàn)證時(shí)間的復(fù)雜性為O(1)。如圖8 給出了驗(yàn)證時(shí)間開銷隨文檔數(shù)量的變化關(guān)系（取100 次隨機(jī)測試的驗(yàn)證時(shí)間平均值）。隨著文檔數(shù)量的增加，所需的驗(yàn)證時(shí)間開銷也緩慢增加，但本文方案對驗(yàn)證過程進(jìn)行了簡化，故所需時(shí)間還是遠(yuǎn)小于文獻(xiàn)[24]方案。

圖8 驗(yàn)證時(shí)間開銷

6 結(jié)論

本文提出了一種新的可驗(yàn)證的模糊關(guān)鍵詞搜索方案。為了減少計(jì)算開銷和存儲空間，為每個模糊關(guān)鍵字集而并非每個模糊關(guān)鍵字生成一個索引向量，采用三節(jié)點(diǎn)哈希鏈表來構(gòu)建安全索引，并為每個模糊關(guān)鍵字集索引計(jì)算一個混淆函數(shù)對真實(shí)索引進(jìn)行加密混淆，使云端可通過模糊關(guān)鍵詞直接解密對應(yīng)索引，而不需要先找到精確關(guān)鍵字再利用返回關(guān)鍵詞再次構(gòu)造解密方案獲得索引，簡化了搜索流程，極大地提高了搜索的效率。最后，為了抵御云服務(wù)器的惡意攻擊，為每一個模糊關(guān)鍵字生成一個驗(yàn)證標(biāo)簽，實(shí)現(xiàn)了對返回結(jié)果的可驗(yàn)證性。通過與現(xiàn)存方案的比較，提出的VFKS 方案在索引構(gòu)建、陷門生成、搜索以及搜索結(jié)果驗(yàn)證階段的綜合性能更高。在文中，還對所提方案的安全性進(jìn)行了詳細(xì)的分析，實(shí)驗(yàn)評估結(jié)果表明了該方案的安全性和有效性。