支持可驗證的密文模糊關鍵字檢索方案

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

1.重慶郵電大學 自動化學院，重慶400065

2.重慶第二師范學院 數學與信息工程學院，重慶400065

3.四川大學 網絡空間安全學院，成都610065

1 引言

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

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

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

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

2 問題描述

2.1 系統模型

系統模型包含三個不同的實體：數據擁有者、數據使用者以及云服務器，如圖1所示。

圖1 系統模型框圖

一個非交互的可驗證對稱可搜索加密方案是由下述六個多項式時間算法組成的集合。

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

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

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

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

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

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

2.2 威脅模型

在威脅模型中，認為數據擁有者將誠實地加密文檔、構建安全索引并計算身份驗證標簽，數據使用者將誠實地為查詢關鍵字產生陷門；而云服務器被視為不受信任的實體，它可能試圖從加密文件、安全索引和搜索陷門中學習其他有價值的信息。此外，為了節約計算成本，它可能會把無效的搜索結果返回給數據使用者。

2.3 設計目標

該方案應該滿足以下要求。

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

（2）有效性：可以有效地返回搜索結果，并且在進行結果驗證時開銷很小。

（3）隱私保護：不能向云服務器泄露任何數據信息，如超出泄漏范圍內的關鍵字和文檔的明文信息。

（4）搜索結果可驗證性：可以驗證搜索結果是否正確，以防止云服務器將不正確的搜索結果返回給數據使用者。

3 預備知識

加密工具對于設計加密方案非常重要[18-19]。下文闡述了所用到的加密工具、概念以及結構。

3.1 對稱加密

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

3.2 偽隨機函數和消息驗證函數

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

其中l 為關鍵字的最大長度，k 為密鑰，N 為文檔數。

驗證標簽生成函數為：

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

3.3 倒排索引

本文基于倒排索引[21]構建索引表。TF-IDF[22]規則是一種加權統計詞頻的技術，用于度量關鍵詞和文件之間的關聯程度。當關鍵詞在文檔集合中某個文件出現的次數越多，則關聯程度越高；但關鍵詞在該文件集合中出現的頻率越高，關聯程度越低。對文件ID(Cj)（表示加密文件Cj的標識符）中所有關鍵詞wi，利用TF-IDF評分規則計算其相關性分數sc：

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

表1 倒排索引

3.4 模糊集的構造

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

如編輯距離為1，關鍵字hello 的模糊集為：

3.5 安全索引

對于任意模糊集合Swi,d，可以計算混淆函數：

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

對于任意模糊關鍵字wi,t∈Swi,d計算：

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

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

4 所提方案及安全性分析

4.1 所提方案

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

（1）KeyGen(k)：輸入安全參數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)：為了方便高效地構建索引，通過擴展倒排索引構造了包含三個節點的鏈表作為索引，結構如圖2所示。

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

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

（2.3）數據擁有者為每個關鍵字wi構建模糊關鍵字集，Swi,d表示與wi編輯距離為d 的模糊關鍵字集，表示Swi,d中的關鍵字。

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

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

（3）Trapdoor(K,w′)：當用戶想要搜索包含關鍵字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))}中存在：

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

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

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

最后檢查下式是否成立：

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

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

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

從而解密C(w′)。

圖2 安全索引的構建

4.2 安全性分析

定義（隱私性）若對任意的概率多項式時間PPT模擬器Sim有：

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

這樣來區分真實游戲和模擬游戲，真實游戲由一個挑戰者和一個敵手A 來完成，而模擬游戲則由一個模擬器sim來完成。

真實游戲(Gamereal)：

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

挑戰者根據密鑰生成和索引構建算法計算密鑰集K 和(I,C)，并把(I,C)送至敵手A。

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

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

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

挑戰者把 |F1|,| F2|,…, | FN|和l 送至模擬器sim。

模擬器sim計算(I′,C′)并送至挑戰者。

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

（1）敵手A 選擇關鍵字w 并送給挑戰者。

（2）模擬器sim 根據PRP π 和PRF f 計算陷門T′w，并把T′w送至挑戰者。

（3）挑戰者把T′w送給敵手A。

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

5 實驗結果

5.1 性能比較

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

表2 有效性比較

表3 性能比較

在索引構建階段，由于文檔數N、模糊關鍵字的總數量m 均大于精確關鍵字數n，所以本文的VFKS方案的索引構建有效性優于文獻[14]和[15]方案。

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

綜合以上性能比較結果，在索引構建、陷門生成、搜索以及結果驗證階段，本文方案綜合性能優于現存方案。

5.2 實驗分析

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

（1）索引構建

在本文方案中，首先需要給每個關鍵字構建對應的模糊關鍵字集。構建模糊關鍵字集的時間與關鍵字的數量有關。圖3 給出了在編輯距離d=1 時，本文方案和文獻[24]方案生成模糊關鍵字集的時間開銷的結果比較。

圖3 模糊關鍵字集構造時間開銷

在模糊集構建階段，由于本文方案使用通配符技術，極大減少了精確關鍵字對應模糊集中的模糊關鍵字數量，所以所需時間開銷遠小于通過枚舉法來構造模糊集的文獻[24]方案。

圖4給出了當關鍵字數量n=5 000 時，本文方案和文獻[24]方案在構建安全索引時的時間開銷比較結果。兩方案的開銷都隨著文檔數的增加而增加，但本文方案增加幅度較小。由于本文方案模糊關鍵字數量遠小于文獻[24]方案，所以總體時間開銷遠小于文獻[24]方案。

圖4 索引構建時間開銷(n=5 000)

圖5 給出了當文檔數量N=10 000 時，本文方案和文獻[24]方案在構建安全索引時的時間開銷比較結果。兩方案的開銷都隨著關鍵字數量的增加而增加，但本文方案增加幅度較小，而文獻[24]方案幾乎是線性增長且總體開銷遠大于本文方案。

圖5 索引構建時間開銷(N=10 000)

（2）陷門生成

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

圖6 本文方案陷門生成時間開銷

（3）搜索的有效性

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

圖7 搜索時間開銷

（4）驗證的有效性

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

圖8 驗證時間開銷

6 結論

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