云環境下安全的可驗證多關鍵詞搜索加密方案

張鍵紅，武夢龍，王晶，劉沛，姜正濤，彭長根

（1.北方工業大學信息學院，北京 100144；2.貴州大學公共大數據國家重點實驗室，貴州 貴陽 550025；3.京東集團財稅創新部，北京 100176；4.中國傳媒大學計算機與網絡空間安全學院，北京 100024）

1 引言

作為云計算的一種重要服務[1]，云存儲[2]為解決企業和個人的海量數據存儲提供了一個途徑，使用戶能夠擺脫沉重的本地數據計算和管理負擔。然而，將大量敏感數據（如財務文檔、電子醫療記錄等）以明文形式存儲在遠程不可信云服務提供商（CSP,cloud service provider）上，會給用戶的數據隱私安全帶來潛在隱患。為此，在數據外包給遠程服務器之前，數據擁有者需要對數據進行加密。這樣能夠抵制不可信CSP 的數據泄露，從而實現外包數據的隱私安全[3-5]。然而，加密卻破壞了明文間消息的關聯性，給數據的搜索帶來極大困難。為了解決這個問題，對稱可搜索加密（SSE,symmetric searchable encryption）技術[6]被提出，它允許數據所有者根據指定關鍵詞進行搜索。盡管對稱可搜索加密能夠實現較高的搜索效率，但是并不能提供公開可驗證性。為了解決該問題，Boneh 等[7]提出了基于公鑰的可搜索加密方案，該方案是一種單關鍵詞可搜索加密。由于該方案只能對單關鍵詞進行搜索，因此搜索精度不高，還可能會返回一些不相關的結果。為了節省帶寬和計算資源，縮小查詢范圍，可搜索加密（SE,searchable encryption）應該支持多關鍵詞搜索，才能避免返回不必要的加密文件。

Golle 等[8]首次提出了基于連接關鍵詞的可搜索加密方案，在該方案中，關鍵詞的陷門長度與加密文檔的數量呈線性關系，使搜索的通信開銷過高、實用性較低。為了解決該問題，Ballard 等[9]構造了一種基于雙線性映射的多關鍵詞可搜索加密方案，在該方案中，盡管關鍵詞陷門具有固定長度，但是搜索每個文檔需要執行2 次雙線性映射運算，使方案的計算耗費巨大。Ryu 等[10]提出了一個高效的、基于雙線性映射的多關鍵詞可搜索加密方案，在該方案中，關鍵詞陷門具有固定長度，能夠降低計算開銷。Cao 等[11]利用內積相似性問題提出了一種可排序的多關鍵詞搜索加密方案。該方案能夠對搜索結果進行相關度排序，提高了搜索結果的匹配精度。但每一次搜索請求時，存儲服務器都需要遍歷所有文檔索引，使服務器計算負擔較重。

理論上，CSP 應該誠實地根據協議規定來保障外包數據的機密性和完整性。然而，在現實中，為了降低管理負擔和計算壓力，云服務器可能會返回不正確或不完整的搜索結果。這意味著數據所有者的外包數據可能存儲在一個不可信的云服務器上。因此，為了保證搜索結果的正確性，可搜索方案應該提供完整性驗證機制[12-14]。同時，為了不削弱云存儲的優勢，應使結果驗證的計算開銷盡可能小。為了實現以上功能，Miao 等[15]提出了一種新的高效多關鍵詞可搜索加密方案，該方案不僅能實現多關鍵詞搜索，還能實現密文的完整性驗證。盡管該方案被證明是安全的，但是該方案不能抵制搜索模式的隱私泄露。已知2 個搜索令牌T=(T1,T2)和T′=(T'1,T'2)，云服務器能夠通過判定關系式是否成立來確定這2 次的搜索關鍵詞是否一樣。

實現文件的前向安全性和搜索模式的隱私性是搜索加密方案亟須解決的2 個問題，現有大多數搜索方案都不滿足這2 種特性。前向安全性能夠確保云服務器不能了解新插入文件的相關信息，也就是說，云服務器不能利用已有的搜索陷門來測試新插入文件是否包含對應的關鍵詞。搜索模式的隱私性能夠確保云服務器不能區分數據用戶2 次提交的搜索陷門是否對應于相同的關鍵詞。這2 個問題的存在給現有可搜索加密方案帶來巨大安全隱患。此外，為了確保云端服務器上外包文件的安全性，應該將公開審計技術[16-17]擴展到SE 方案中來提升方案的安全性。為了解決以上問題，基于分級身份加密、哈希鏈技術和帶密鑰的哈希函數[18-19]，本文在云環境下設計了一種高效的可驗證多關鍵詞可搜索加密方案，該方案不僅能實現對多關鍵詞搜索，也能實現對云端密文的完整性驗證；此外，還能實現搜索模式的隱私保護和文件的前向安全性。

所提可驗證多關鍵詞可搜索加密方案本質上是一種連接關鍵詞搜索。具體而言，本文的主要研究工作可概括如下。

1) 多關鍵詞搜索。本文所提方案允許數據擁有者對多個關鍵詞進行搜索。

2) 搜索結果的完整性驗證。本文所提方案滿足搜索結果完整性驗證，通過結果驗證機制，能夠防止CSP 返回不準確的搜索結果。

3) 標準模型下的安全性。通過形式化安全分析，本文所提方案能夠在標準安全模型下被證明是安全的，能夠抵制抗密鑰猜測攻擊（KGA,keyword guesswork attack），安全分析表明，本文所提方案是有效的、安全的。

4) 搜索模式隱私保護。本文所提方案能夠阻止云服務器通過搜索陷門來猜測關鍵詞的具體信息。

5) 前向安全性。在本文所提方案中，云服務器不能利用已有陷門信息來測試新插入的密文文件是否包含相應的關鍵詞，但仍能利用更新后的陷門信息對原有密文文件和新插入密文文件進行搜索。

2 云環境下多關鍵詞可搜索加密系統

本節將介紹云環境下多關鍵可搜索加密的系統模型、威脅模型，然后給出最終的安全設計目標。

2.1 系統模型

一個云環境下的多關鍵詞可搜索加密系統包含云服務器、數據擁有者、用戶和審計者4 類實體。其系統模型如圖1 所示。

圖1 系統模型

云服務器。云服務器具有豐富的存儲空間和強大的計算能力，負責為用戶存儲數據和執行文件搜索服務。

數據擁有者。數據擁有者希望把數據文件加密后外包到遠程云服務器上。

用戶。數據使用者需要經數據擁有者授權，并向云服務器提交關鍵詞搜索請求以獲取相關文件。

審計者。審計者負責對外包到云服務器的數據進行完整性驗證。

2.2 設計目標

為了確保能夠對密文進行有效的搜索，本文所提方案的主要目標具體如下。

1) 支持多關鍵詞搜索。為了能夠準確地定位相應密文，所提方案應該同時支持多關鍵詞搜索。

2) 抗關鍵詞猜測攻擊。當關鍵詞空間較小時，攻擊者能夠發動關鍵詞猜測攻擊，為此，要確保所提方案能夠抵制攻擊者的猜測攻擊。

3) 密文的完整性。確保在不可信云服務器上存儲的密文不能被云服務篡改，以確保密文的完整性。

4) 前向安全性。確保不可信云服務器不能通過已有搜索令牌，來獲得新插入文件的任何信息。然而，能夠利用新的搜索令牌來搜索滿足搜索關鍵詞的所有文件。

5) 搜索模式的隱私性。云服務不能通過2 個搜索令牌來判定所對應的關鍵詞是否一樣。

2.3 算法定義

一個多關鍵詞可驗證搜索加密方案包括以下幾個算法。

Setup(1k)→(Para)。這是一個確定性算法，輸入一個安全參數k，輸出系統公開參數Para。

KeyGen(Para)→（PKD,SKD,PKC,SKC）。該算法是一個概率算法，輸入系統公開參數Para，輸出數據擁有者的密鑰對（PKD,SKD）和云服務器的密鑰對（PKC,SKC）。

Enc(Para,PKD,SKD,PKC,F,W)→{SigF,IF,π}。該算法是一個概率算法，輸入系統公共參數Para、數據擁有者的密鑰對（PKD,SKD）、云服務器的公鑰PKC以及關鍵詞集W和文件集F，輸出簽名集SigF、索引集IF和報頭π。

TrapdoorGen(Para,SKD,W′,L)→{T}。該算法是一個概率算法，輸入系統參數、數據擁有者的私鑰SKD和關鍵詞集W′以及關鍵詞的位置信息L，輸出搜索令牌{T}。

Insert(Para,PKD,SKD,PKC,F,W)→{SigF,IF,π}。該算法是一個概率算法，輸入公共系統參數Para、數據擁有者的密鑰對（PKD,SKD）以及關鍵詞集W和新插入的文件集F，輸出簽名集SigF、索引集IF和報頭π。

Search(Para,T,L,IF,SKC)→(C′,FID′)。該算法是一個概率算法，輸入系統參數Para、云服務器的私鑰SKC、索引集IF、關鍵詞的位置信息L和搜索令牌T，云服務器調用該算法來進行文件匹配，最后，返回滿足條件的密文C′和文件標識FID。

Verify(Para,C′,FID′)→1/0。該算法是一個交互式算法，需要審計者與云服務器執行一個交互過程，與遠程數據完整審計方案中的審計過程一樣，如果通過驗證返回1；否則，返回0。

2.4 安全模型

對于一個關鍵詞可搜索加密而言，關鍵詞的空間相對較小，這使許多可搜索加密方案易遭受字典攻擊和離線關鍵詞猜測攻擊。此外，在一個可搜索加密方案中，由于不可信云服務器擁有密文和搜索陷門信息，它是一個攻擊性較強的內部敵手。因而，對于一個可搜索加密方案，如果能夠抵抗不可信云服務器的安全攻擊，那么該方案就是安全的。下面，給出云服務器關鍵詞猜測攻擊的安全模型定義。

定義1安全模型。令k是一個安全參數，A 是一個多項式時間攻擊者，敵手A 與挑戰者C之間的交互游戲定義如下。

系統建立階段。C輸入一個安全參數k來調用Seup 算法和KeyGen 算法，產生系統公開參數Para、數據擁有者密鑰對（PKD,SKD）以及云服務器的密鑰對（PKC,SKC），發送(Para,PKD,PKC,SKC)給敵手A。

階段1

陷門詢問階段。敵手A 能夠自適應地選擇一個關鍵詞集{w1,…,wd}發布陷門詢問。C 調用TapdoorGen 算法產生陷門（d0,d1），并把它返回給敵手A。

插入詢問。敵手A 能夠自適應地選擇一個文件F和相應的關鍵集W來發起插入詢問，C能夠利用公共參數Para 和(PKD,PKC)產生一個密文集、索引集和簽名集，并把它們返回給敵手A。

挑戰階段。敵手A選擇2個含有m個元素的關鍵詞集(W*0,W*1)發起挑戰。C隨機選擇一個比特b∈{0,1}，并調用Enc 算法來產生搜索索引I*b。最后，C發送I*b給敵手A。

階段2

陷門詢問階段。像階段1 的挑戰階段一樣，敵手A 能夠自適應地選擇關鍵詞集{w1,…,wd}發布陷門詢問。限制條件為關鍵詞集(W*0,W*1)不能被發布陷門詢問。

猜測階段。A 返回一個猜測的比特b′∈{0,1}。當b′=b時，敵手贏得該游戲。敵手A 能夠贏得該游戲的優勢定義為=Pr[b′=b]?1/2。

3 具體方案構造

為了方便理解方案的設計，表1 總結了本文所用符號。

表1 本文所用符號

3.1 系統建立階段（Setup）

輸入一個安全參數k，該階段調用setup(1k)算法輸出一組雙線對密碼參數（G1,G2,e,p,g1,g2），其中G1和G2是2 個階為p的乘法循環群，p是一個大素數，e:G1×G1→G2是一個雙線性對映射，g1和g2是群G1的2 個隨機生成元。H1:{0,1}*→G1，H2:{0,1}*→Zp和f:{0,1}*→Zp是3個密碼哈希函數。然后，隨機選擇r0∈Zp和hi∈Gl（i=0,1,…,l），其中l表示一個文件所包含關鍵詞的最大個數。最后，系統公開參數被公布為

3.2 密鑰產生（KeyGen）

對于數據擁有者，它隨機選擇一個數d∈Zp作為密鑰，并計算其公鑰PKD=。對于云服務器而言，它也隨機選擇一個數c∈Zp作為密鑰，并計算其公鑰

最后，數據擁有者和云服務器分別保存相應的私鑰SKD=d和SKC=c。此外，數據擁有者還要選擇一個隨機數θ∈Zp秘密保存，并且計算一個哈希鏈（f1,f2,…,fχ），其中fi=f(fi?1(θ))和f0=（f θ）。

3.3 加密和認證標簽產生（Enc）

在該階段，數據擁有者不僅需要對多個關鍵詞加密來建立搜索索引，還需要產生外包文件集F的認證標簽。其具體過程如下。

1) 為了方便陳述，假設首次外包文件集F0中包含n個文件，并且每個文件都包含m個關鍵詞，即F0={F01,…,F0n}，W={w1,…,wm}。

2) 選擇一個安全的對稱加密算法 Enc=（Ek,Dk），并計算文件F0j的密文C0j=Ek(F0j)，i=1,…,n。

3) 隨機選擇sb∈Zp計算

3.4 文件插入（Insert）

令Fi表示第i次插入的文件集，為了表述方便，不妨設該文件集也包括n個文件，并且每個文件都包含m個關鍵詞，即Fi={Fi1,…,Fin}，W={w1,…,wm}。為了插入該文件集，數據擁有者計算如下。

1)利用安全對稱加密算法Enc=(Ek,Dk)來計算文件Fij的密文Cij=Ek(Fij)，i=1,…,n。

2) 然后，隨機選擇sb∈Zp計算

作為簽名公鑰。接著，對于文件集Fi中的文件，即對于j=1,…,n，計算每個文件Fij的認證標簽

3.5 陷門產生階段（TrapdoorGen）

3.6 搜索階段（Search）

當接收到用戶提交的搜索令牌T=(d0,d1,fχ?i)和位置信息L后，云服務器執行搜索算法，如算法1所示，其具體步驟如下。

3.7 驗證階段（Verify）

該階段的目的是驗證外包在云端的密文是否被云服務器篡改。為此，審計者需要與云服務器執行一個交互過程，具體步驟如下。

4 安全性分析

本節將對本文所提方案的正確性和安全性進行分析。為了方便理解，首先，回顧一下本文方案所基于的數學難題——基于截斷決定性雙線性Diffie-Hellman 安全假設（truncated decisionalq-augmentedbilinear Difffie-Hellmanexponent(q-ABDHE)problem）[19]。已知一組元素，判斷關系式是否成立是一個困難問題。

正確性對于整個協議，如果每個實體都能按照協議規定正確地執行協議，那么，式(17)和式(20)一定成立。這就意味著，授權用戶一定能獲取滿足關鍵詞的相應密文。

因為對于式(17)，依據算法1 可知

因此，當式(17)成立時，這就意味著有效的搜索令牌一定能匹配到滿足條件的密文文件。

對于式(20)，依據算法1 可知

這意味著，如果所返回的密文沒有被篡改，那么，式(20)一定成立。

定理1在q-ABDHE 假設下，本文所提方案能夠安全地抵制KGA。

插入詢問。當敵手用一個含有n個文件集F和關鍵詞集W進行文件插入詢問時，C執行3.4 節中的文件插入算法來得到以下密文

來猜測出與之對應的關鍵詞。因此，本文所提方案能夠實現搜索模式的隱私保護。證畢。

定理3在離散對數安全假設下，不可信服務器不能在外包密文被篡改情況下，產生一個證明信息Prof，使其通過審計者的驗證。

證明因為本文中采用的完整性驗證方案是基于Shacham 和Waters 的遠程數據完整驗證方案[12]。而該方案在安全模型下被證明是安全抵制云服務器的篡改和刪除攻擊，因而，本文所提方案也能夠抵制相應攻擊。

定理4在哈希函數的單向性條件下，本文所提方案能夠實現前向安全性。

證明在本文所提方案中，采用哈希鏈來實現文件的前向安全性。在第i次文件插入時，哈希鏈中的哈希值fχ?i被嵌入文件密文中，即

當第i次文件被插入以后，用戶的搜索令牌是T=(d0,d1,fχ?i)，其中嵌入了哈希鏈中的fχ?i哈希值，這使云服務器僅能搜索第i次插入文件集。為了實現對第i次插入前的文件進行搜索，云服務器需要計算

然后，利用T=(d0,d1,fχ?i+1)來搜索第i?1 次插入的文件集。依次類推，云服務器能夠搜索第i次前所有滿足關鍵詞集的所有文件。

然而，對于云服務器，盡管它擁有第i次文件插入前的搜索令牌，例如，第i?1 次文件插入后的搜索令牌為T=(d0,d1,fχ?i+1)，它仍然不能利用(d0,d1,fχ?i+1)來對新插入的文件進行搜索，因為新插入文件的密文中嵌入了哈希值fχ?i，由于哈希函數f的單向性，云服務器不能通過哈希值fχ?i+1來獲得fχ?i。因而，它不能通過式(21)來判斷搜索令牌是否匹配新插入的文件，從而實現了方案的前向安全性。

5 效率分析

本節將從理論角度來對所提方案的效率和功能進行分析。為了更好地說明本文所提方案的性能，本節將通過與3 種多關鍵詞搜索加密方案[13-15]比較來分析本文所提方案性能。為了簡化分析，在下文的分析中，僅考慮耗時的密碼運算。令E 表示在群G1或G2中的指數運算，M 表示乘法運算，P表示對運算，H1表示一個比特串映射到群G1中元素的map2point 運算。表3 給出了本文所提方案與文獻[13-15]方案的效率比較，其中，n表示文件的個數，m表示關鍵詞集中的元素個數，l表示所詢問的關鍵詞個數，d表示返回的搜索結果，“___”表示不具有該功能，search model 表示搜索模式是否滿足隱私性，leak 表示不滿足，anonymity表示滿足。forward security 表示方案是否滿足前向安全性。

表3 幾種方案的效率比較

從表3可知，就算法KeyGen、Trapdoor和Search而言，與其他2 種方案相比，本文所提方案和文獻[15]方案具有更小的計算開銷。就Enc 算法而言，本文所提方案是所有方案中計算量最小的方案，這是因為在本文所提方案中最耗時的對運算獨立于文件和關鍵詞個數，對運算不會隨著關鍵詞的數量和文件的數量的增加而增多。同時，從表3 中可以發現，本文所提方案和文獻[15]方案在效率上基本一致。在陷門產生階段，本文所提方案比文獻[15]方案需要較多的計算量。然而，本文所提方案能夠實現搜索模式的隱私保護，具體原因在定理2 中被分析。但是文獻[15]方案不能實現搜索模式的隱私保護，因為在文獻[15]方案中，搜索令牌T=(T1,T2)具有如下形式

因此，對于 2 個搜索令牌T=(T1,T2)和T′=(T′1,T′2)，如果它們包含同一組關鍵詞集，那么，云服務器可以通過驗證

來判定這2 個搜索令牌T和T′是否包含同樣的關鍵詞。從而泄露了搜索模式的相關統計信息。此外，文獻[15]方案也不能抵制惡意云服務器的離線猜測攻擊，對于含有n個元素的關鍵詞集，云服務器能夠以概率猜測出相應的關鍵詞集。當關鍵詞空間相對較小、搜索關鍵詞個數較多時，云服務器能夠以較大概率猜測出關鍵詞。此外，文獻[15]方案不支持文件的前向安全性，這使云服務能夠利用已有的搜索令牌來搜索新插入文件是否包含相應關鍵詞，從而泄露新插入文件的相關信息。

本文所提方案通過引入一個帶密鑰的哈希函數來有效地抵制惡意云服務器的離線關鍵詞猜測攻擊，因為云服務器不知道密鑰θ，使它不可能產生一個，所以能夠阻止云服務器的離線關鍵詞猜測攻擊。此外，為了實現前向安全性，本文所提方案采用一個哈希鏈，然后借助哈希鏈的單向性來實現本文所提方案的前向安全性。

綜上所述，本文所提方案在陷門產生階段盡管計算量比文獻[15]方案大，但也優于文獻[13-14]方案，并且所增加的計算量是由計算力豐富的云服務器完成的，而沒有增加用戶的任何計算負擔。此外，就方案的功能而言，本文所提方案不僅能實現搜索模式的隱私保護和文件前向安全性，還能抵制云服務器的離線關鍵詞猜測攻擊。而文獻[15]方案不能實現搜索模式的隱私性和插入文件的前向安全性，也不能抵制云服務器的離線關鍵詞猜測攻擊。通過犧牲一點計算代價換取方案的功能增強和安全性增強是值得的。這就意味著，本文所提方案就綜合性能而言是4 種方案中最好的。

6 實驗分析

為了評估本文所提方案的實際性能，本文實驗在一臺1.5 GHz 主頻、Broadcom BCM2711 處理器、2 GB 內存、Raspbian 操作系統的樹莓派上進行。每個算法運行100 次，最后，通過取平均數來得到以下所有實驗數據。

在加密階段，4 種方案的計算開銷與關鍵詞個數和文件個數呈線性相關，如圖2 和圖3 所示。同時，由圖2 和圖3 可知，本文所提方案與文獻[15]方案對應的直線斜率都低于文獻[13-14]方案所對應的直線斜率，這意味著本文所提方案和文獻[15]方案在計算開銷上優于文獻[13-14]方案。

圖2 n=2 000 時加密階段的計算開銷

在陷門產生階段，本文所提方案與文獻[13-15]方案都與關鍵詞的個數呈線性關系，如圖4 所示。由于在文獻[15]方案中，所有關鍵詞只是進行加法運算，而加法的計算開銷幾乎可以忽略，所以在圖4中，文獻[15]方案的計算量幾乎呈一條水平直線。盡管在陷門產生階段，本文所提方案的計算開銷劣于文獻[15]方案的計算開銷，但本文所提方案仍優于文獻[13-14]方案。

圖3 m=200 時加密階段的計算開銷

圖4 陷門產生階段的計算開銷

在搜索階段，本質上，本文所提方案與文獻[13-15]方案的計算開銷都與關鍵詞個數呈線性關系，如圖5 所示。

圖5 搜索階段的計算開銷

然而，在文獻[15]方案和本文所提方案中，與關鍵詞數量相關的運算只有乘法運算，而乘法運算具有較低的計算開銷，因此，在圖5 中，文獻[15]方案和本文所提方案幾乎呈一條水平直線。同時，由圖5 可知，本文所提方案的計算效率也優于文獻[13-15]方案。

7 結束語

本文提出了一種新的可驗證多關鍵詞可搜索加密方案，它既能支持密文的完整性驗證，又能支持多關鍵詞搜索，同時，還支持文件的前向安全性和搜索模式的隱私保護。與以往的可搜索加密方案相比，本文所提方案能夠在標準模型下被證明是安全的，且能夠抵制不可信云服務器的離線猜測攻擊，并且該方案是一種基于公鑰環境下支持文件前向安全的可搜索加密方案。在未來的研究工作中，將探索設計有效地支持更豐富語義表達的密文搜索方案。