支持結(jié)果驗證的多服務(wù)器動態(tài)可搜索加密方案

何 雨，田有亮，3，萬 良，楊 力

(1.貴州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025；2.貴州省公共大數(shù)據(jù)重點實驗室，貴州 貴陽 550025；3.貴州大學(xué) 密碼學(xué)與數(shù)據(jù)安全研究所，貴州 貴陽 550025；4.西安電子科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，陜西 西安 710071)

隨著互聯(lián)網(wǎng)的快速發(fā)展，人們對數(shù)據(jù)的計算和存儲的需求急劇上升，從而會導(dǎo)致本地存儲資源嚴重不足。云計算技術(shù)的快速發(fā)展，給人們在文件存儲和處理方面提供了很大的便捷，廉價的計算成本和巨大的存儲容量也吸引了許多企業(yè)以及用戶將數(shù)據(jù)外包至云服務(wù)器，盡管云服務(wù)給人們帶來了大量的好處，但是它也并非是完全可信賴的，它可能會為了自己的利益去篡改數(shù)據(jù)。為了防止數(shù)據(jù)信息泄露，數(shù)據(jù)擁有者通常會在上傳數(shù)據(jù)之前對數(shù)據(jù)進行加密，同時這會對檢索造成一定的困難；針對此問題就有學(xué)者提出了可搜索加密技術(shù)，它可以使云服務(wù)器對加密數(shù)據(jù)進行查詢并返回相應(yīng)的查詢結(jié)果。

傳統(tǒng)的可搜索加密方案是構(gòu)建一個加密的索引，用來搜索加密的文件，而不會向服務(wù)器泄露關(guān)鍵字和文件的真實信息。文獻[1]首次提出了對文檔加密進行密文檢索，實現(xiàn)了第一個對稱可搜索加密方案，但是該方案檢索效率較低。文獻[2]為了提高檢索效率，構(gòu)造了基于正排索引的對稱可搜索加密方案。隨后，文獻[3]為了進一步提高檢索效率，構(gòu)造了基于倒排索引實現(xiàn)次線性搜索的方案。文獻[4]對可搜索加密技術(shù)展開了進一步的研究。但是這些方案只支持單關(guān)鍵字檢索。

單關(guān)鍵詞檢索無法滿足現(xiàn)實中高效檢索的需求。為了解決單個關(guān)鍵詞檢索方案存在的局限性，許多學(xué)者提出了支持多模式的可搜索加密方案，主要包括模糊關(guān)鍵詞查詢、排序查詢、連接關(guān)鍵詞查詢、和范圍查詢等[5-8]。文獻[9]首次提出了兩個非直接的連接關(guān)鍵詞檢索方案，但是該方案檢索效率不高。文獻[10]提出首個亞線性的連接關(guān)鍵詞查詢方案，并可以將該方案擴展為支持關(guān)鍵詞的布爾查詢。為了豐富檢索功能，文獻[11]和文獻[12]提出了針對加密云數(shù)據(jù)的模糊關(guān)鍵詞搜索。

上述方案是基于單個服務(wù)器模型來實現(xiàn)的。這種模型具有服務(wù)器故障導(dǎo)致數(shù)據(jù)丟失的威脅，同時搜索效率較低。為了解決單服務(wù)器加密方案的局限性，許多學(xué)者提出了多云服務(wù)器模型。文獻[13-15]提出了分布式對稱可搜索加密的雙服務(wù)器模型，其中一個服務(wù)器是存儲服務(wù)器，另一個為代理服務(wù)器來代理協(xié)助查詢。文獻[16]首次提出了一個可以在多云服務(wù)器中使用的可搜索加密方案。文獻[17]通過將文檔劃分為多個塊，然后隨機分配給不同的服務(wù)器，保持了亞線性的搜索時間。文獻[18]利用聯(lián)盟鏈將多個云服務(wù)器連接構(gòu)造成一個多云服務(wù)器平臺，而且數(shù)據(jù)不存儲在服務(wù)器上，減少了服務(wù)器對文檔的控制。

以上都是在服務(wù)器可以誠實地執(zhí)行檢索任務(wù)的假設(shè)下實現(xiàn)的，它們不適用于半可信服務(wù)器返回結(jié)果不驗證的情況。為此，許多學(xué)者提出了結(jié)果可驗證的可搜索加密方案。文獻[19]使用消息認證碼以及用戶的授權(quán)訪問控制，對動態(tài)密文檢索方案進行驗證。在文獻[20]的方案中實施服務(wù)器端驗證，并提出了一種不依賴第三方的可信查詢費用交易模式。文獻[21]結(jié)合區(qū)塊鏈技術(shù)和哈希函數(shù)用于實現(xiàn)搜索費用支付的公平性，無需引入任何第三方。文獻[22]提出使用區(qū)塊鏈構(gòu)建了一個公平的對稱可搜索加密方案。但是這些方案都存在一定的局限性。為了提高檢索的效率，針對這些問題引入智能合約來完成檢索交易，筆者通過智能合約驗證返回的結(jié)果是否準確。

針對海量數(shù)據(jù)而言，相對于單個服務(wù)器，將數(shù)據(jù)分別存儲在多個云服務(wù)器上的安全性更高，同時單個服務(wù)器檢索的效率也會提高。所以，筆者通過構(gòu)建在多服務(wù)器模型下的可搜索加密方案，來實現(xiàn)在多服務(wù)器模型中的密文檢索，同時保證文件的隱私以及檢索準確性?；诖耍P者做的主要工作如下：

① 基于Shamir-秘密共享技術(shù)，構(gòu)建了一個多云服務(wù)器模型，防止單點故障導(dǎo)致數(shù)據(jù)大量丟失的問題，實現(xiàn)數(shù)據(jù)安全分布存儲和高效查詢；

② 利用智能合約自動執(zhí)行的特點，構(gòu)造查詢結(jié)果的驗證方法，在查詢過程返回結(jié)果并自動驗證，保證用戶和云服務(wù)器之間查詢結(jié)果的正確性；

③ 引入分區(qū)矩陣，構(gòu)造更新數(shù)據(jù)的子矩陣，減少在更新操作后查詢產(chǎn)生的開銷，同時引入虛假關(guān)鍵字，防止云服務(wù)器的猜測攻擊。

1 基礎(chǔ)知識

1.1 秘密共享

SHAMIR于1979年提出了著名的(t，n)門限秘密共享方案[23]，可以稱其為Shamir-秘密共享技術(shù)。這個方案的基本思想是將秘密分成n份，分別發(fā)送給n個獨立的參與者，它滿足下面兩個條件：① 任何小于t個的參與者都無法重構(gòu)原秘密，單個子秘密丟失也不影響重構(gòu)秘密；② 任何t個或t個以上的參與者能夠協(xié)同恢復(fù)秘密信息。

Shamir-秘密共享技術(shù)是基于Lagrange插值公式提出的，主要內(nèi)容為：設(shè)G是一個關(guān)于q的有限域，q是素數(shù)且q>n。現(xiàn)在將秘密信息K分成n份，分發(fā)給n個參與方，且要使得其中至少任意t(t≤n)個服務(wù)器協(xié)作可以得到秘密信息K，任取a1，a2，…，at-1∈G構(gòu)造一個多項式：f(x)=k+a1x+a2x2+…+at-1xt-1，其中k為密鑰，令α是G域的本原元素，作ki=f(αi)(i=1，2，…，n)，稱ki為子密鑰，分別交給對應(yīng)參與者。若t個參與者想恢復(fù)秘密信息k，則利用Lagrange插值公式：

由k=f(0)=h(0)得到秘密信息k。

1.2 智能合約

智能合約[24]是由密碼學(xué)家SZABO于1997年首次提出來的，其本質(zhì)是以數(shù)字形式定義的承諾，包括合約參與方可以在上面執(zhí)行這些約定內(nèi)容的協(xié)議。智能合約可以部署在以太坊區(qū)塊鏈上，通過參與者協(xié)商構(gòu)造指定條件可以觸發(fā)執(zhí)行合約。智能合約通過使用密碼和其他安全機制，自動化運作可使指定的關(guān)系免受委托人的破壞，以及第三方的竊聽或惡意干擾。它在許多重要方面可以應(yīng)用，包括信用、內(nèi)容權(quán)限管理、支付系統(tǒng)和不記名合同。

1.3 基于AVL樹的倒排索引

倒排索引是一種索引數(shù)據(jù)結(jié)構(gòu)，用于存儲從關(guān)鍵字到文檔的映射。一方面，在基于倒排索引的方案中，字典中的每個關(guān)鍵字都有一個索引。另一方面，每個關(guān)鍵字都映射到包含該關(guān)鍵字的一組文檔，它是基于關(guān)鍵詞進行查找，而不需要遍歷每一個文檔，索引構(gòu)建成功后查詢的時間會比較短。AVL樹也就是平衡二叉搜索樹，基于AVL樹的查詢方法相對于一般的查詢來說，可以提高查找的效率，同時平均查找長度也會減少，從本質(zhì)上講，它將傳統(tǒng)的二叉搜索結(jié)構(gòu)從線性表擴展到樹狀結(jié)構(gòu)，檢索的時間開銷較低。所以筆者基于AVL樹的倒排索引進行方案構(gòu)建，來降低檢索的時間。

2 系統(tǒng)模型

2.1 系統(tǒng)模型

方案系統(tǒng)模型如圖1所示，包含4個參與者，數(shù)據(jù)擁有者(Data Owner，DO)、云服務(wù)器(Cloud Service Provider，CSP)、智能合約(Smart Contract，SC)、數(shù)據(jù)使用者(Data Users，DU)。

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

數(shù)據(jù)擁有者(DO)：擁有一個文檔集，用F={f1，f2，f3，…，fn}表示，主要負責(zé)從文檔集中為每個文檔生成關(guān)鍵字并建立索引，對文檔和索引進行加密，最后使用秘密共享技術(shù)將加密后的文檔上傳到不同的服務(wù)器上；DO還被授權(quán)發(fā)行密鑰，將密鑰發(fā)送給授權(quán)用戶解密文檔。他還可以更新云服務(wù)器上的外包文檔。

云服務(wù)器(CSP)：針對多個服務(wù)器，DO使用Shamir-秘密共享技術(shù)對加密文檔生成編號，每個編號對應(yīng)一個服務(wù)器，將加密文檔按照生成的編號分別上傳至對應(yīng)的服務(wù)器上，服務(wù)器獲得查詢陷門后，對存儲的加密文檔執(zhí)行搜索，經(jīng)過計算后將各服務(wù)器對應(yīng)的結(jié)果整合到一起再反饋給用戶，最后將搜索得到的前K個相關(guān)系數(shù)最高的加密文檔集返回給DU。

數(shù)據(jù)使用者(DU)：將查詢生成陷門，并將陷門分別發(fā)送至服務(wù)器和智能合約，以搜索云服務(wù)器上存在的加密文檔。服務(wù)器將驗證后的結(jié)果發(fā)送給DU后，DU使用解密密鑰對文檔進行解密。

智能合約(SC)：通過DO和DU輸入的安全索引和陷門，計算得到相關(guān)文檔ID，在服務(wù)器反饋計算結(jié)果后與之驗證，來判斷服務(wù)器返回結(jié)果是否正確。

系統(tǒng)參數(shù)如表1所示。

表1 系統(tǒng)參數(shù)

2.2 威脅模型

在文中的模型中有多個不完全可信的云服務(wù)器。假設(shè)這些云服務(wù)器是半誠實且好奇的，即它們誠實地遵循著系統(tǒng)定義的協(xié)議，但是又對用戶與系統(tǒng)的交互中產(chǎn)生的信息感興趣，并且希望推斷出敏感信息。云服務(wù)器知加密文檔大小、加密索引以及每次搜索之后返回的加密文檔，它可能會根據(jù)這些已知的知識來推斷加密關(guān)鍵字以及對應(yīng)的加密文檔。

3 算法設(shè)計

3.1 索引生成階段

索引生成：數(shù)據(jù)所有者利用TF-IDF方法對每個待上傳文檔進行提取關(guān)鍵詞操作，從每個文檔中提取候選關(guān)鍵詞，將得到的關(guān)鍵詞集合根據(jù)權(quán)值倒序排列，最后將前K個權(quán)值最高的關(guān)鍵詞作為文本的關(guān)鍵詞。

詞頻(Term Frequency，TF)定義為包含特定關(guān)鍵字的文檔出現(xiàn)的次數(shù)；逆文檔頻率(Inverse Document Frequency，IDF)定義為在將文檔集中的文檔總數(shù)除以文檔集中特定關(guān)鍵字出現(xiàn)的次數(shù)之后得到的值：

fTF=ln(1+Nf，Wi) ，

(1)

fIDF=ln(1+n/NWi) 。

(2)

關(guān)鍵字的總數(shù)會因為文檔的大小而不同，這會影響文檔的相關(guān)性得分，導(dǎo)致最后計算結(jié)果出現(xiàn)誤差。因此，需要將fTF、fIDF都歸一化，以最大程度地減少對檢索相關(guān)文檔的影響。fTF′，fIDF′分別是為每個穩(wěn)文檔關(guān)鍵詞創(chuàng)建一個歸一化詞頻值，為每個查詢關(guān)鍵詞生成一個包含所有查詢關(guān)鍵字的歸一化逆文檔頻率值：

(3)

(4)

索引結(jié)構(gòu)：將所有的文檔構(gòu)建基于關(guān)鍵字的索引樹，樹的每個葉子節(jié)點包含文檔的相關(guān)值。除葉子節(jié)點外的每個節(jié)點都包含3個指針，分別指向父節(jié)點、左節(jié)點以及右節(jié)點。每個節(jié)點表示為一個三元信息組{ID，TF，L}，其中ID表示為二叉樹中每個節(jié)點的標識符，TF為該節(jié)點關(guān)鍵詞的詞頻，L表示為關(guān)鍵詞對應(yīng)的相關(guān)文檔列表。具體結(jié)構(gòu)如圖2所示。

圖2 索引結(jié)構(gòu)圖

3.2 密鑰生成階段

(sk，SK)←KeyGen(1λ)：密鑰生成算法，構(gòu)造一個維度為m的隨機二進制向量S和兩個階數(shù)為m×m的隨機可逆矩陣M1和M2，其中m是關(guān)鍵詞的數(shù)量，生成密鑰SK={S，M1，M2}和對稱密鑰sk。

3.3 索引加密階段

將關(guān)鍵字與文檔構(gòu)建的索引進行加密，得到安全索引進行密文檢索。將密鑰sk和文檔集合F作為輸入，對文檔進行關(guān)鍵字提取，得到關(guān)鍵字集合W，并對關(guān)鍵字和文檔集合構(gòu)建倒排索引，使用密鑰SK加密索引并使用對稱密鑰sk加密文檔集F，最后輸出安全索引I和加密文檔集合C。

算法1生成索引：I←BuildIndex(SK，F(xiàn)，W)。

輸入：密鑰SK={S，M1，M2}，文檔集合F。

輸出：安全索引I、加密文檔集合C。

① 利用TF-IDF算法對文檔集合F提取關(guān)鍵字集合。

② 根據(jù)關(guān)鍵字集合構(gòu)造一個m維的向量Bi。

③ 生成一個隨機參數(shù)r1∈R。

④ fori= 0，1，2，…，mdo

⑤ ifsi==1 then

⑥b′i=b″i=bi

⑦ else

⑩ end

3.4 陷門生成階段

用戶將查詢關(guān)鍵字集合生成安全陷門，并發(fā)送給各個服務(wù)器。通過安全陷門，云服務(wù)器在搜索查詢過程中無法獲取明文關(guān)鍵字信息來推測敏感文檔信息。輸入密鑰SK，查詢關(guān)鍵字集合Q，生成安全陷門T，并用這個陷門T來進行查詢相關(guān)加密文檔。

算法2生成陷門：T←Trapdoor(SK，Q)。

輸入：密鑰SK={S，M1，M2}，查詢關(guān)鍵字集合Q。

輸出：陷門T。

① 生成一個隨機參數(shù)r2∈R。

② 根據(jù)查詢關(guān)鍵字集合Q構(gòu)造一個m維的向量B。

③ fori= 0，1，2，…，mdo

④ ifsi==0 then

⑤b′i=b″i=bi

⑥ else

⑨ end

(5)

(6)

由上式可知，選取的隨機數(shù)r2只會對每次生成的關(guān)鍵字陷門產(chǎn)生影響，而不會影響最終的計算結(jié)果，所以可以隨機選擇，而且因為加入了隨機數(shù)，所以生成的陷門的安全性更高，服務(wù)器無法推測出相關(guān)信息，陷門的安全性和隱私性得到了一定的保證。

(7)

同理可知，隨機數(shù)r1對最終結(jié)果也沒有影響，可以隨機選擇，同時在索引構(gòu)造過程中引入隨機數(shù)，加強了索引的安全性，使索引的隱私性得到了一定的保證。

3.5 查詢階段

用戶通過查詢關(guān)鍵字生成的陷門，發(fā)送至各個服務(wù)器進行查詢操作。首先需要判斷用戶是否被授權(quán)，檢查用戶賬戶余額是否足夠支付查詢的押金以及查詢費用。如果成立，則開始搜索操作，服務(wù)器收到查詢陷門后，結(jié)合安全索引I，得到查詢結(jié)果；如果匹配成功，則返回加密的相關(guān)文檔集合，并進行排序，否則，返回空值。

由式(6)和式(7)推導(dǎo)可知，關(guān)于查詢集Q計算得到的結(jié)果集R為

(8)

算法3查詢過程：R←Search(Ii，Q)。

輸入：查詢關(guān)鍵字集合Q，安全索引Ii，返回的文檔個數(shù)K。

輸出：結(jié)果列表List。

① 根據(jù)算法2將查詢關(guān)鍵字集合Q生成安全陷門T。

② 將安全陷門T分裂成T1和T2。

③ 計算相關(guān)系數(shù)R=I′iT1+I″iT2。

④ ifR==0 then

⑤ Return null

⑥ else

⑦ 根據(jù)計算得到的相關(guān)系數(shù)R，找到索引樹節(jié)點u。

⑧ 將新元素 插入到列表List中。

⑨ 對列表List中元素進行排序。

⑨ end

3.6 查詢結(jié)果驗證

通過構(gòu)造驗證合約，將服務(wù)器執(zhí)行任務(wù)返回的結(jié)果進行驗證。用戶將查詢陷門發(fā)送給智能合約后啟動查詢服務(wù)，CSP將查詢得到的結(jié)果發(fā)送至驗證合約地址，調(diào)用verify()函數(shù)來進行驗證；智能合約計算后得到的搜索結(jié)果，通過與云服務(wù)器返回的結(jié)果進行匹配，來驗證云服務(wù)器返回結(jié)果的正確性。如果匹配成功，則返回true，并將查詢結(jié)果發(fā)送至DU，否則查詢操作失敗，交易取消。

合約中存在變量查詢開銷α，用戶觸發(fā)合約發(fā)起查詢?nèi)蝿?wù)的押金β，每個服務(wù)器簽訂合約所需繳納的押金γ，每個服務(wù)器進行查詢?nèi)蝿?wù)的計算成本gs，以及用戶給每個服務(wù)器支付的計算報酬ρc。顯然需要α=nρc，且β≥nρc，否則用戶無法發(fā)起查詢?nèi)蝿?wù)；ρc>gs，否則服務(wù)器不會接受查詢?nèi)蝿?wù)。

具體步驟如下：

步驟1 如果用戶繳納押金β且滿足以上兩個公式來簽訂合約，則合約被激活，進入步驟2。

步驟2 服務(wù)器在用戶繳納押金后規(guī)定時間內(nèi)繳納押金γ，簽訂合約階段結(jié)束，根據(jù)用戶提交的陷門觸發(fā)合約，進入步驟3。

步驟3 每個服務(wù)器根據(jù)接收到的陷門信息來執(zhí)行任務(wù)。如果服務(wù)器均按時執(zhí)行，則進入下一階段；否則歸還用戶押金，并沒收每個超時服務(wù)器的押金分配給正常執(zhí)行的服務(wù)器，同時合約終止。

步驟4 服務(wù)器按時執(zhí)行并返回結(jié)果后，執(zhí)行驗證過程。如果服務(wù)器都是誠實的，則將用戶押金β中的ρc交付給每一個服務(wù)器，并返回服務(wù)器押金γ，同時歸還用戶剩余的押金β-nρc。否則，如果只有部分服務(wù)器是誠實的，則將誠實服務(wù)器以及用戶押金退還，將不誠實服務(wù)器押金獎勵給誠實服務(wù)器。此時合約終止。

算法4驗證過程：Verify(FID)。

輸入：查詢關(guān)鍵字集合Q生成的陷門T，安全索引I，結(jié)果文件排序編號FID。

輸出：驗證結(jié)果值Flag(Boolean)。

① 根據(jù)陷門T和索引I，計算得到FID′并排序。

② 判斷FID和FID′中各個值是否相等。

③ Fori=0，1，2…，Kdo

④ ifFID[i]=!FID′[i]

⑤ 返回用戶押金和查詢費用，扣除服務(wù)器押金。

⑥ Flag = false

⑦ break

⑧ else

⑨ 將交易費用發(fā)送至服務(wù)器，并返回各自押金。

⑩ Flag = true

3.7 返回結(jié)果解密

將服務(wù)器返回的加密文檔進行解密操作。文檔集合中每個文檔都通過對稱加密算法加密，密鑰通過安全傳輸信道與用戶共享。該算法將服務(wù)器返回的加密文檔集合Ck，解密密鑰sk作為輸入，用戶再使用密鑰對返回的加密文檔進行解密，最后得到明文文檔Fk。

4 文檔更新

DO希望上傳的數(shù)據(jù)是能夠?qū)崟r更新的，即對已經(jīng)上傳的文檔進行刪除操作或者添加新的文檔。當向云服務(wù)器增加或者刪除某些文檔時，那么原始文檔的關(guān)鍵詞的TF值會發(fā)生改變，同時也會導(dǎo)致索引樹結(jié)構(gòu)發(fā)生改變。這會導(dǎo)致后續(xù)查詢操作復(fù)雜且計算開銷增大。針對這一問題，筆者提出了一種方法來執(zhí)行更新操作而不影響先前的索引結(jié)構(gòu)。

4.1 刪除文檔

刪除某些已上傳的文檔時，要保持原有的索引結(jié)構(gòu)。如果刪除文檔時將該文檔對應(yīng)關(guān)鍵詞索引也刪除，則AVL樹的平衡結(jié)構(gòu)可能會被打破，此時需要重新構(gòu)建二叉樹使其保持平衡。如果刪除的關(guān)鍵字為葉子節(jié)點，則可以直接刪除，此時平衡二叉樹的結(jié)構(gòu)沒有破壞；如果不是，則可以把待刪除關(guān)鍵字節(jié)點對應(yīng)文檔序號改為null，不改變其節(jié)點位置，保持樹的平衡。

4.2 添加文檔

如果要添加新的文檔，可能會增加新的關(guān)鍵字，同時需要構(gòu)建新的索引，那么現(xiàn)有的索引樹結(jié)構(gòu)將會被改變，根據(jù)倒排索引構(gòu)造的AVL樹結(jié)構(gòu)，則需要根據(jù)新添加關(guān)鍵字的值選擇插入的位置來調(diào)整樹結(jié)構(gòu)使其達到新平衡。采用遞歸的方法在樹中向下搜索，直到找到新節(jié)點所在的位置。然后考慮其插入路徑是否會導(dǎo)致樹結(jié)構(gòu)的不平衡。如果新節(jié)點插入后二叉樹失去了平衡，重新平衡該樹，使之重新達到平衡狀態(tài)。

如果只是簡單地將加密的關(guān)鍵字索引上傳至服務(wù)器，這會使原始的矩陣改變，增大矩陣階數(shù)，使得計算更加復(fù)雜，導(dǎo)致計算成本增加。為了解決這個問題，引入了分塊矩陣的概念，這可以使新添加的關(guān)鍵字產(chǎn)生一個新的隨機可逆矩陣，從而不改變現(xiàn)有的關(guān)鍵字集合來添加新的關(guān)鍵字。由于新的關(guān)鍵字與先前的關(guān)鍵字集合區(qū)分開，服務(wù)器會知道新添加的關(guān)鍵字索引與加密文檔信息，這會導(dǎo)致隱私泄露。為了使服務(wù)器無法將新添加的信息相關(guān)聯(lián)，引入了一種新的方法，對于新添加的關(guān)鍵字集合，我們向其中添加一部分虛假關(guān)鍵字，真實關(guān)鍵字與虛假關(guān)鍵字的位置是隨機的，這增加了向關(guān)鍵字集合添加關(guān)鍵字的隨機性，降低了服務(wù)器找到新添加的真實關(guān)鍵字的位置以及相關(guān)文檔等敏感信息的概率。

為了在不重新加密的情況下對新添加的關(guān)鍵字進行加密，使用了分塊矩陣，Mn1和Mn2是兩個大小為n×n的隨機可逆矩陣。

(9)

(10)

新生成的矩陣M′1和M′2的逆矩陣，分別為

(11)

通過分區(qū)矩陣來對關(guān)鍵字進行添加操作，這可以保證文檔中現(xiàn)有關(guān)鍵字的TF值在添加關(guān)鍵字后不會發(fā)生改變，降低了計算的開銷，同時引入虛假關(guān)鍵字，降低了好奇的服務(wù)器關(guān)聯(lián)相關(guān)信息的概率，防止云服務(wù)器和惡意用戶的猜測攻擊，提高了新添加關(guān)鍵字及相關(guān)文檔的隱私性。

5 安全性分析及證明

5.1 安全性分析

(1) 文檔的安全及隱私性

DO所擁有的文檔在上傳至云服務(wù)器之前已經(jīng)用對稱加密算法將文檔以及關(guān)鍵詞加密，上傳至云服務(wù)器的都是加密數(shù)據(jù)，而且相關(guān)的密鑰也是通過安全信道傳輸給需要搜索的授權(quán)用戶，只有DO以及授權(quán)用戶能夠擁有文檔的解密密鑰，所以云服務(wù)器無法獲取上傳的敏感信息；同時，關(guān)鍵詞是基于倒排索引與文檔關(guān)聯(lián)的，所以在搜索過程中不需要對所有文檔遍歷查找，而且索引與陷門都是加密形式存在，即使服務(wù)器掌握這些信息也無法推測出相關(guān)明文信息。因此文件的安全性與隱私性得到了一定的保證。

(2) 查詢的不可鏈接性

生成索引以及查詢向量的時候引入隨機數(shù)r1和r2，使得每次得到的陷門都不一樣，增強了陷門的機密性以及不可鏈接性，服務(wù)器都無法從不同的查詢中獲得關(guān)聯(lián)信息，即使每次用相同的關(guān)鍵詞進行查詢，得到的陷門都各不相同，因此，云服務(wù)器也無法識別兩次相同關(guān)鍵詞的查詢請求是否相同。

(3) 檢索的正確性

因為服務(wù)器是半可信的，它的自利性可能會導(dǎo)致查詢后返回的結(jié)果缺失或者錯誤，所以在本方案中，引入智能合約取代可信第三方，通過使用智能合約，在授權(quán)用戶向服務(wù)器發(fā)送查詢陷門后，服務(wù)器需要向智能合約提交檢索結(jié)果；智能合約根據(jù)計算得到的結(jié)果與服務(wù)器返回結(jié)果進行對比，如果正確，則將檢索費用給服務(wù)器，否則扣除服務(wù)器押金的同時，返回用戶檢索費用。如果用戶在檢索過程中自動取消，則扣除用戶提交的押金。這些都保證了檢索返回結(jié)果的正確性以及用戶及服務(wù)器之間的交易公平。

5.2 安全性證明

在本方案中，數(shù)據(jù)信息是存儲在半可信的云服務(wù)器上，它對上傳的信息(文檔、索引、陷門等)好奇，并試圖收集允許泄漏更多的信息。如果能夠證明云服務(wù)器無法獲取允許泄露信息外更多的信息，那么就可以證明本方案是安全的。首先，以3種形式化定義來描述允許泄漏信息的泄漏函數(shù)；其次，通過分析文檔的機密性、陷門的不可區(qū)分性及索引構(gòu)建過程等方面來證明本方案的安全性。用模擬器S和敵手A定義了兩個實驗Reals1(sk)和Ideals2(sk)。

泄露函數(shù)L1、L2、L3定義如下：

(1) 泄露函數(shù)L1：在文檔加密階段，每個文檔對應(yīng)的標識符記為fi，文檔總數(shù)記為n，加密文檔記為FE，密文文檔大小可以定義為|FE|，實驗Ideals2(sk)可以獲取實驗Reals1(sk)的密文FE，文檔大小|FE|，文檔數(shù)量n以及文檔標識符fi。將這些允許泄露信息記為L1。

(2) 泄露函數(shù)L2：在陷門生成過程中，云服務(wù)器無法區(qū)分關(guān)于用戶根據(jù)查詢的關(guān)鍵字生成的陷門Tw所對應(yīng)的關(guān)鍵字的信息。實驗Ideals2(sk)可以獲取實驗Reals1(sk)的查詢關(guān)鍵字集合Q的大小|Q|，以及元素qi。將這些允許泄露信息記為L2。

(3) 泄露函數(shù)L3：在索引構(gòu)建階段，云服務(wù)器也無法區(qū)分關(guān)于加密索引I所對應(yīng)的關(guān)鍵字信息，實驗Ideals2(sk)可以獲取實驗Reals1(sk)中安全索引所包含的元素qi是否存在于文件fi中。將這些允許泄露信息記為L3。

如果說本方案對于抵抗適應(yīng)性選擇關(guān)鍵字攻擊是安全的，那么對于任意多項式敵手，存在一個PPT模擬器S滿足

|Pr[Reals1(sk)=1]-Pr[Ideals1(sk)=1]|≤negl(k) ，

其中，negl(k)表示關(guān)于k的一個可忽略概率函數(shù)，k是一個安全參數(shù)。

定理1如果在文檔加密階段、陷門生成過程以及索引構(gòu)建過程所泄露的信息概率函數(shù)都是可忽略的，則文中提出的可搜索加密方案是CKA安全的。

證明 定義了一個挑戰(zhàn)者C，與敵手A進行交互，分別執(zhí)行實驗Reals1(sk)和實驗Ideals2(sk)，如果最后敵手A對得到的結(jié)果無法區(qū)分，那么此證明成功。

(1) 密文生成階段

初始階段：挑戰(zhàn)者C生成系統(tǒng)的公共參數(shù)，并發(fā)送給敵手A。挑戰(zhàn)階段：敵手A可以在多項式時間內(nèi)向挑戰(zhàn)者C發(fā)起任意文檔的查詢，挑戰(zhàn)者生成加密文檔FE并返回給敵手A。挑戰(zhàn)者分別執(zhí)行實驗Reals1(sk)和實驗Ideals2(sk)。

實驗Reals1(sk)：明文信息集F={f1，f2，…，fn}，執(zhí)行加密算法Enc(fi)，其中1≤i≤n，輸出加密文檔真實值X=(Enc(fi)，1≤i≤n)。

實驗Ideals2(sk)：根據(jù)泄露函數(shù)L1，隨機生成fi，(1≤i≤n)，得到加密文檔的模擬值為X′=(f′i，1≤i≤n)。

挑戰(zhàn)者C生成隨機參數(shù)b∈{0，1}，b=0時，將真實值X發(fā)送給敵手；b=1時，將模擬值發(fā)送給敵手。

猜測：敵手輸出對b的一個猜測。

上傳文檔是經(jīng)過AES(Advanced Encryption Standard)算法加密的，所以服務(wù)器只知道密文文檔的某些信息，而解密秘鑰只存在于數(shù)據(jù)擁有者以及授權(quán)用戶，服務(wù)器無法獲取，所以敵手得到的結(jié)果是真實值X還是模擬值X′不能確定，即敵手A獲勝的概率是可忽略的。

(2) 陷門生成階段

初始階段：挑戰(zhàn)者C生成系統(tǒng)的公共參數(shù)，并發(fā)送給敵手A。挑戰(zhàn)階段：敵手A可以在多項式時間內(nèi)向挑戰(zhàn)者C發(fā)起任意關(guān)鍵字的查詢，挑戰(zhàn)者生成陷門T并返回給敵手A。挑戰(zhàn)者分別執(zhí)行實驗Reals1(sk)和實驗Ideals2(sk)。

實驗Reals1(sk)：挑戰(zhàn)者將Q作為輸入，執(zhí)行算法Trapdoor(sk，Q)，輸出真實陷門值T。

實驗Ideals2(sk)：根據(jù)泄露函數(shù)L1、L2，按以下步驟生成模擬的陷門值。

① 建立查詢關(guān)鍵字Q′=(q′i，1≤q≤|Q|)。

② 執(zhí)行算法Trapdoor(sk′，Q′)，輸出模擬陷門值T′。

挑戰(zhàn)者C隨機選擇參數(shù)b∈{0，1}，當b=0時，將真實值T發(fā)送給敵手；b=1時，將模擬值T′發(fā)送給敵手。

猜測：敵手輸出對b的一個猜測。

根據(jù)式(6)可知，在陷門生成算法中引入的參數(shù)r2，能夠保證在相同關(guān)鍵字情況下兩次生成的陷門不同，使敵手不能確定得到的結(jié)果是真實值T還是模擬值T′，即敵手獲勝的概率是可忽略的。

(3) 索引生成階段

敵手A可以在多項式時間內(nèi)向挑戰(zhàn)者C發(fā)起任意關(guān)鍵字的查詢，挑戰(zhàn)者生成關(guān)鍵字索引I并返回給敵手A。挑戰(zhàn)者分別執(zhí)行實驗Reals1(sk)和實驗Ideals2(sk)。

實驗Reals1(sk)：挑戰(zhàn)者將W作為輸入，執(zhí)行算法BuildIndex(sk，F(xiàn)，W)，輸出真實安全索引I。

實驗Ideals2(sk)：根據(jù)泄露函數(shù)L1、L2、L3，按以下步驟生成模擬的安全索引值。

① 對任意qi∈Q，如果關(guān)鍵字qi包含在fi中，將qi轉(zhuǎn)換成向量W′fi。

② 執(zhí)行算法BuildIndex(sk，fi，W′fi)，輸出安全索引模擬值I′。

挑戰(zhàn)者C隨機選擇參數(shù)b∈{0，1}，當b=0時，將真實值I發(fā)送給敵手；b=1時，將模擬值發(fā)送給敵手。

猜測：敵手A輸出對b的一個猜測。

根據(jù)式(7)可知，在索引構(gòu)建算法中引入的隨機參數(shù)r1，同樣能夠保證在相同關(guān)鍵字情況下兩次生成的安全索引不同，同理可知敵手獲勝的概率是可忽略的。

綜上所述，對任意多項式敵手，實驗Reals1(sk)和實驗Ideals2(sk)的輸出是一致的，即存在可忽略概率negl(k)，使得

|Pr[Reals1(sk)=1]-Pr[Ideals1(sk)=1]|≤negl(k) 。

因此，文中方案在允許泄露(L1，L2，L3)的情況下是關(guān)于選擇關(guān)鍵字攻擊(CKA)安全的。

6 性能分析

對本方案中算法進行數(shù)據(jù)仿真實驗，并對不同數(shù)量關(guān)鍵字分析本方案的算法效率。仿真實驗是在Windows操作系統(tǒng)下利用python語言進行編程來實現(xiàn)，在PC機(Intel(R) Core(TM) i5-9400 CPU 2.90 GHz，8 GB(RAM)，64位)的環(huán)境中運行的，實驗結(jié)果取算法運行100次的平均值。圖3是分別對50、100、200個文檔進行關(guān)鍵字提取，每個文本關(guān)鍵詞數(shù)量分別取1、5、10、15、20，對不同數(shù)量關(guān)鍵字生成的時間消耗對比。由實驗結(jié)果可知，在相同文檔數(shù)量情況下，隨著關(guān)鍵字數(shù)量的增加，時間消耗基本保持一致；而隨著文檔數(shù)量的增加，每個文檔生成相同關(guān)鍵字數(shù)量所消耗的時間也逐漸增加。

圖3 提取關(guān)鍵字時間

圖4是索引生成的時間對比圖。在每個文檔生成關(guān)鍵詞數(shù)量相同的情況下，文檔數(shù)量分別為50、100、200到500時，索引生成的時間隨著文檔數(shù)量增加而增加；而針對相同數(shù)量的文檔，在關(guān)鍵詞數(shù)量不同時，索引生成消耗時間基本保持一致。

圖4 索引生成時間

圖5表示在使用不同索引結(jié)構(gòu)的情況下，索引生成時間的對比。在每個文檔生成5個關(guān)鍵詞的情況下，使用TF-IDF方法構(gòu)造關(guān)鍵詞索引，方案[2]為正排索引、方案[12]是使用對偶編碼函數(shù)和位置敏感hash函數(shù)構(gòu)建索引，3種不同形式的索引結(jié)構(gòu)生成時間對比如圖5所示，當文檔數(shù)量一致時，隨著文檔數(shù)量的增加，本方案的索引生成算法的時間成本比其他方案更低。

圖5 索引時間對比

圖6表示在不同文檔數(shù)量，不同關(guān)鍵字數(shù)量的情況下，搜索時間的變化趨勢，因為文檔數(shù)量越多，索引生成時間也會增加，所以，搜索的時間與文檔數(shù)量呈正相關(guān)。如圖6所示，在每個文檔生成相同關(guān)鍵字數(shù)量時，檢索的時間是隨著文檔數(shù)量增加而不斷增加的；同時，當文檔數(shù)量一致時，檢索時間與關(guān)鍵詞數(shù)量也是正相關(guān)的。

圖6 搜索時間

圖7表示在查詢階段的時間消耗對比。在每個文檔關(guān)鍵詞數(shù)量為10時，查詢時間消耗如圖所示，文中方案與其他兩個方案查詢時間與文檔數(shù)量都呈遞增關(guān)系，但在文中方案中，使用倒排索引和多個服務(wù)器同步查詢，所以查詢所需時間明顯低于其他兩個方案。

圖7 查詢方案對比

7 結(jié)束語

筆者提出了一種支持結(jié)果驗證的多服務(wù)器動態(tài)可搜索加密方案，利用Shamir-秘密共享技術(shù)將加密文檔分別存儲在不同的服務(wù)器上，去執(zhí)行檢索任務(wù)，并通過智能合約來驗證檢索結(jié)果的正確性；如果驗證通過，則將最終的檢索結(jié)果返回給用戶。而且筆者提出的方案能夠很好地支持對文檔的動態(tài)更新，對更新數(shù)據(jù)構(gòu)造分塊矩陣的子矩陣，降低了更新后查詢的計算開銷。通過安全性分析和仿真實驗分析，文中方案能有效地保護數(shù)據(jù)隱私，同時在索引生成、檢索方面與其他方案進行實驗對比。結(jié)果表明，文中方案具有更高的效率。