張 恩，侯纓盈，李功麗，李會(huì)敏，李 鈺

(1.河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453007；2.“智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)”河南省工程實(shí)驗(yàn)室，河南 新鄉(xiāng) 453007)

0 引言

隨著云計(jì)算與大數(shù)據(jù)時(shí)代的到來(lái)，越來(lái)越多的數(shù)據(jù)擁有者將海量數(shù)據(jù)存儲(chǔ)在云端以節(jié)省本地資源，同時(shí)還利用云計(jì)算強(qiáng)大的計(jì)算能力對(duì)數(shù)據(jù)進(jìn)行檢索操作。不僅如此，企業(yè)或機(jī)構(gòu)還在云端建立自己的分等級(jí)系統(tǒng)，在保證用戶可以對(duì)數(shù)據(jù)高效搜索的同時(shí)，還能對(duì)不同用戶進(jìn)行等級(jí)控制，使不同等級(jí)的用戶只能檢索到其所屬等級(jí)下的信息數(shù)據(jù)，但是存儲(chǔ)在云端的數(shù)據(jù)隨時(shí)可能會(huì)泄露給云服務(wù)提供商，此類用戶隱私數(shù)據(jù)泄漏造成的安全問(wèn)題層出不窮，并給用戶造成嚴(yán)重的后果，因此，如何在享受云計(jì)算帶來(lái)便捷服務(wù)的同時(shí)，保護(hù)用戶隱私數(shù)據(jù)的安全性是目前亟待解決的關(guān)鍵問(wèn)題。

為了保護(hù)數(shù)據(jù)的安全性，數(shù)據(jù)擁有者通常在數(shù)據(jù)外包給云服務(wù)器之前對(duì)其進(jìn)行加密；但是加密后如何對(duì)密文域進(jìn)行操作成為一項(xiàng)新的挑戰(zhàn)?？伤阉骷用芗夹g(shù)，把共享給用戶的密文數(shù)據(jù)連同加密關(guān)鍵字列表同時(shí)上傳至云服務(wù)器，用戶產(chǎn)生關(guān)鍵詞陷門，利用該陷門直接對(duì)云服務(wù)器上的密文進(jìn)行關(guān)鍵詞搜索，無(wú)需將密文文件下載至本地先解密再進(jìn)行搜索，從而在實(shí)現(xiàn)隱私數(shù)據(jù)保護(hù)的前提下，有效地提高了對(duì)云上數(shù)據(jù)的操作速度，并且釋放了用戶的本地資源空間。這一技術(shù)是目前密碼學(xué)領(lǐng)域中的熱點(diǎn)研究?jī)?nèi)容，在工業(yè)、醫(yī)療、物聯(lián)網(wǎng)等方面具有廣泛的應(yīng)用。

Boneh等[1]首次提出公鑰可搜索加密(Public Key Encryption with Keyword Search, PEKS)理論并給出幾種具體的構(gòu)造方案，此后公鑰可搜索加密技術(shù)有了很多新的發(fā)展。董曉蕾等[2]圍繞可搜索加密的新理論、新方法和新技術(shù)，針對(duì)可搜索加密的模式、安全性、表達(dá)能力和搜索效率等方面進(jìn)行綜述，并指出該領(lǐng)域當(dāng)前研究中需要解決的問(wèn)題及發(fā)展趨勢(shì)。文獻(xiàn)[3-6]分別針對(duì)移除安全信道、抵抗離線關(guān)鍵詞攻擊、取消身份證書以及對(duì)多密鑰加密文件搜索與驗(yàn)證的問(wèn)題作出了一定貢獻(xiàn)，但是，以上方案僅適用于單用戶環(huán)境，并不能滿足現(xiàn)今實(shí)際生活對(duì)多用戶環(huán)境下可搜索加密方案的需求。苗銀賓等[7]針對(duì)多數(shù)據(jù)擁有者場(chǎng)景，提出一種多數(shù)據(jù)擁有者認(rèn)證的密文檢索方案。該方案結(jié)合線性秘密共享與可搜索加密技術(shù)，使得數(shù)據(jù)用戶只有得到多個(gè)數(shù)據(jù)擁有者的授權(quán)才能解密返回的結(jié)果；但是，該方案基于雙線性Diffie-Hellman問(wèn)題，不能有效抵抗量子攻擊。白平等[8]針對(duì)云環(huán)境中信息檢索過(guò)程可能存在偽造查詢結(jié)果以及密鑰泄露的問(wèn)題，構(gòu)造了一種支持用戶撤銷的可驗(yàn)證密文檢索方案。該方案通過(guò)對(duì)關(guān)鍵詞簽名以及運(yùn)用驗(yàn)證算法和用戶撤銷算法對(duì)檢索結(jié)果進(jìn)行驗(yàn)證，通過(guò)重加密機(jī)制實(shí)現(xiàn)了用戶撤銷，從而保證了系統(tǒng)的安全性；然而，該方案基于判定性Diffie-Hellman問(wèn)題構(gòu)造，同樣不能有效抵抗量子攻擊。

在多用戶場(chǎng)景下，可搜索加密技術(shù)也有很多新的發(fā)展，Wang等[9]提出的方案優(yōu)點(diǎn)在于通過(guò)使用基于屬性的分層加密模型，從而提供細(xì)粒度的訪問(wèn)控制和完整的授權(quán)。Lee等[10]提出的方案優(yōu)點(diǎn)在于將數(shù)據(jù)分為數(shù)據(jù)共享和關(guān)鍵詞搜索兩層，從而實(shí)現(xiàn)分層的可搜索加密。Wang等[11]提出的方案優(yōu)點(diǎn)在于通過(guò)定義基于ID分層的可搜索加密方案，從而實(shí)現(xiàn)對(duì)后代的關(guān)鍵詞搜索。文獻(xiàn)[9-11]不僅適用于多用戶環(huán)境，并且實(shí)現(xiàn)了不同定義的分層可搜索加密，避免了所有用戶共享的內(nèi)容是相同的，對(duì)不同用戶的權(quán)限進(jìn)行區(qū)分，但是，當(dāng)不同情景下需要對(duì)訪問(wèn)控制粒度有所改變，例如對(duì)某一(或多個(gè))層級(jí)用戶或者文件更新時(shí)，需要對(duì)某一個(gè)(或多個(gè))等級(jí)進(jìn)行大規(guī)模添加或刪除，以上方案都不能靈活實(shí)現(xiàn)該功能。

Shor[12]證明量子計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)解決離散對(duì)數(shù)和質(zhì)因數(shù)分解問(wèn)題，這表明現(xiàn)有的公鑰可搜索加密方案都將受到量子計(jì)算機(jī)的攻擊。針對(duì)此問(wèn)題，Regev[13]首先提出能夠抵抗量子攻擊的基于格上錯(cuò)誤學(xué)習(xí)(Learning With Errors, LWE)的密碼系統(tǒng)，從此LWE問(wèn)題成為后量子時(shí)代的開(kāi)端。由于基于格上難題構(gòu)造的方案目前尚未找到量子多項(xiàng)式算法，因此可以有效抵抗量子攻擊，并且格密碼具有高效的實(shí)現(xiàn)，只需要在一個(gè)適當(dāng)?shù)哪K上進(jìn)行簡(jiǎn)單的加法和乘法操作。自格密碼被提出至今，已有人提出了基于格的簽名方案、密鑰交換協(xié)議以及多密鑰全同態(tài)方案[14-16]等，因此，格上的密碼系統(tǒng)已經(jīng)成為抗量子攻擊可搜索加密工作的一種必然選擇。

Gu等[17]和Hou等[18]首先將可搜索加密技術(shù)與抗量子算法結(jié)合，提出格上的PEKS方案，成為單用戶環(huán)境下抗量子可搜索加密的基礎(chǔ)方案；但該方案較為簡(jiǎn)單，無(wú)法適用于多用戶環(huán)境。Zhang等[19]針對(duì)安全信道的設(shè)置并不實(shí)際，從而成功移除安全信道，優(yōu)點(diǎn)在于通過(guò)指定服務(wù)器搜索及返回結(jié)果，安全性較高且實(shí)際可行；但該方案只考慮了單用戶環(huán)境，不適用于多用戶環(huán)境。Yang等[20]提出的方案不僅實(shí)現(xiàn)了格上模糊關(guān)鍵詞搜索，優(yōu)點(diǎn)在于利用廣播加密技術(shù)將單用戶環(huán)境拓展至多用戶環(huán)境，對(duì)批量用戶提供云服務(wù)；但方案中用戶僅被區(qū)分為被授權(quán)與未授權(quán)，沒(méi)有明確的等級(jí)劃分，不能實(shí)現(xiàn)分等級(jí)的數(shù)據(jù)搜索。Zhang等[21]提出面向代理的基于身份加密的可搜索加密方案，優(yōu)勢(shì)在于通過(guò)授權(quán)代理代表原數(shù)據(jù)擁有者加密數(shù)據(jù)并將其外包給云服務(wù)器，從而減輕原數(shù)據(jù)擁有者的數(shù)據(jù)處理負(fù)擔(dān)；但該方案是單用戶環(huán)境的，并不適用于多用戶環(huán)境。Xu等[22]提出多寫入者格上可搜索加密方案，該方案允許用戶直接使用他們的身份進(jìn)行數(shù)據(jù)加密，從而降低密鑰管理的復(fù)雜性。該方案的優(yōu)點(diǎn)在于解決了多數(shù)據(jù)擁有者使用不同加密密鑰加密數(shù)據(jù)帶來(lái)的密鑰管理復(fù)雜的問(wèn)題，且首次實(shí)現(xiàn)了基于LWE的可搜索加密方案；但該方案主要針對(duì)多對(duì)一(多數(shù)據(jù)擁有者-單數(shù)據(jù)用戶)場(chǎng)景，并未考慮多用戶場(chǎng)景。

本文針對(duì)現(xiàn)有分等級(jí)的可搜索加密方案不能靈活添加與刪除某一個(gè)或多個(gè)等級(jí)以及不能有效抵抗量子攻擊的問(wèn)題，提出一種基于LWE的自適應(yīng)等級(jí)可搜索加密(Adaptive Hierarchical Searchable Encryption based on LWE, AHSE)方案。該方案利用格的多維特點(diǎn)并基于格上LWE困難問(wèn)題構(gòu)造，可以有效抵抗量子攻擊。首先，通過(guò)設(shè)置條件鍵對(duì)用戶進(jìn)行明確的等級(jí)訪問(wèn)控制，使不同等級(jí)的用戶可以搜索到其所屬等級(jí)下對(duì)應(yīng)的文件；其次，設(shè)計(jì)一種分段式索引結(jié)構(gòu)，使所有用戶僅共享一張索引表即可實(shí)現(xiàn)搜索操作，無(wú)需為每個(gè)文件分別建立索引后逐一搜索，從而提高搜索效率；并且，該結(jié)構(gòu)中等級(jí)數(shù)目可由不同場(chǎng)景對(duì)等級(jí)粒度的需求自由設(shè)定，具有良好的自適應(yīng)性；最后，方案中用戶、文件以及它們所屬等級(jí)都可靈活更改，適用于動(dòng)態(tài)的云計(jì)算環(huán)境。

1 基礎(chǔ)知識(shí)

1.1 格相關(guān)知識(shí)

1)整數(shù)格。

設(shè)a1,a2,…,am∈Rm是m個(gè)線性獨(dú)立無(wú)關(guān)向量，A=[a1,a2,…,am]∈Rm×m表示由m個(gè)線性無(wú)關(guān)向量組組成的m×m維矩陣，m維滿秩格L可以由A生成，定義為：

其中：a1,a2,…,am稱為格的基向量。

2)高斯分布。

3)錯(cuò)誤學(xué)習(xí)(LWE)問(wèn)題。

LWE問(wèn)題允許重復(fù)向挑戰(zhàn)預(yù)言機(jī)Ψ進(jìn)行查詢。如果一個(gè)敵手能夠準(zhǔn)確分辨該實(shí)例來(lái)自Ψ0或Ψ1的優(yōu)勢(shì)|Pr[AΨ0=1]-Pr[AΨ1=1]|是不可忽略的，則存在一個(gè)多項(xiàng)式時(shí)間敵手可以解決判定性LWE問(wèn)題。

1.2 格密碼算法

2 AHSE方案設(shè)計(jì)

2.1 方案模型定義

一個(gè)公司內(nèi)部的數(shù)據(jù)加密后放在服務(wù)器端，所有合法用戶通過(guò)可搜索加密技術(shù)搜索不同的關(guān)鍵詞來(lái)獲取所需數(shù)據(jù)。該公司中，所有合法成員都可以作為數(shù)據(jù)擁有者對(duì)數(shù)據(jù)進(jìn)行共享操作(場(chǎng)景如圖1所示)。該公司將其內(nèi)部合法用戶分為N個(gè)等級(jí)，其中N可以根據(jù)需要的等級(jí)粒度自由設(shè)定。本文假定N=3，分別為頂層管理者、管理人員和普通員工。該公司的普通員工為第三等級(jí)用戶，只能訪問(wèn)搜索少量的數(shù)據(jù)；管理人員為第二等級(jí)用戶，可訪問(wèn)搜索數(shù)據(jù)包含第三等級(jí)可見(jiàn)數(shù)據(jù)，但不是公司內(nèi)部所有的數(shù)據(jù)；頂層管理者為第一等級(jí)用戶，能看到公司內(nèi)部所有數(shù)據(jù)，包含第二和第三等級(jí)的可見(jiàn)數(shù)據(jù)；非公司內(nèi)部的員工不能看到企業(yè)內(nèi)部的任何數(shù)據(jù)。根據(jù)該場(chǎng)景，基于LWE的分等級(jí)可搜索加密方案由5個(gè)必要的通信實(shí)體構(gòu)成：

1)可信中心(Trust Authority，TA)。TA為系統(tǒng)所有合法用戶頒發(fā)公私鑰對(duì)，且與代理服務(wù)器交互，生成數(shù)據(jù)擁有者與用戶之間的代理重加密轉(zhuǎn)換鍵。

2)數(shù)據(jù)擁有者(Data Owner, DO)。DO對(duì)文件進(jìn)行加密后上傳至服務(wù)器，對(duì)關(guān)鍵詞進(jìn)行可搜索加密后構(gòu)建分段式索引表并上傳至代理搜索服務(wù)器。

3)數(shù)據(jù)用戶(Data User, DU)。DU確定需要的文件所對(duì)應(yīng)的關(guān)鍵詞，利用自己的公私鑰對(duì)為該關(guān)鍵詞生成陷門(搜索令牌)，發(fā)送至代理搜索服務(wù)器，等待返回結(jié)果。

圖1 AHSE方案模型Fig. 1 Model of AHSE scheme

4)存儲(chǔ)服務(wù)器(Storage Service, SS)。SS負(fù)責(zé)存儲(chǔ)數(shù)據(jù)擁有者的加密后的文件數(shù)據(jù)，并在搜索成功后，為合法用戶返回指定文件。

5)代理搜索服務(wù)器(Proxy Search Server, PSS)。PSS負(fù)責(zé)存儲(chǔ)數(shù)據(jù)擁有者的索引表，并在搜索時(shí)對(duì)用戶的關(guān)鍵詞陷門與索引表進(jìn)行匹配，根據(jù)匹配結(jié)果，找到對(duì)應(yīng)的文件。

本文建立的模型中，首先由TA為DO和DU分配獨(dú)立的公私鑰對(duì)，由DO將加密數(shù)據(jù)上傳至SS，將加密的索引上傳至PSS；其次，DU搜索文件時(shí)，確定文件所對(duì)應(yīng)的關(guān)鍵詞，并對(duì)該關(guān)鍵詞生成陷門，發(fā)送至PSS；然后，PSS將關(guān)鍵詞陷門與關(guān)鍵詞索引表進(jìn)行匹配，找到匹配關(guān)鍵詞后對(duì)DU進(jìn)行等級(jí)匹配，將該等級(jí)能讀取到的文件標(biāo)識(shí)符發(fā)送給SS；最后，SS返回給DU在該權(quán)限下的有效文件。

2.2 核心算法定義

本文設(shè)計(jì)的基于LWE的分等級(jí)可搜索加密方案，由參數(shù)生成、密鑰生成、條件鍵生成、重加密轉(zhuǎn)換鍵生成、可搜索加密、陷門生成以及搜索測(cè)試等7個(gè)算法構(gòu)成。

1)ParaGen(1n)。輸入一個(gè)安全參數(shù)n，輸出系統(tǒng)的公共參數(shù)P、主公鑰Mpk和主私鑰Msk。

2)KeyGen(P,Mpk,Msk,i)。輸入系統(tǒng)的公共參數(shù)P、主公鑰Mpk、主私鑰Msk，每個(gè)合法用戶的唯一身份標(biāo)識(shí)符i，為每個(gè)用戶生成一個(gè)秘密值Ri，輸出每個(gè)用戶的公私鑰對(duì)(PKi,SKi)。系統(tǒng)內(nèi)部保存Ri，用于重加密轉(zhuǎn)換鍵生成階段構(gòu)造轉(zhuǎn)換鍵。

3)ConKeyGen(P,v,t)。輸入公共參數(shù)P，一個(gè)條件向量v和與該條件匹配的斷言向量t，輸出每一個(gè)等級(jí)條件項(xiàng)Con并公開(kāi)，同時(shí)輸出為每個(gè)用戶生成的條件鍵Conkey通過(guò)以(PKi,RKc′)的形式創(chuàng)建用戶等級(jí)控制列表CL(Control List)，并發(fā)送至PSS。

4)ReKeyGen(PKi,PKj)。輸入TA保存的Pki、PKj對(duì)應(yīng)的秘密值Ri、Rj，輸出代理重加密轉(zhuǎn)化鍵RKi → j。

5)PEKS(P,PKi,w,Con)。輸入系統(tǒng)公共參數(shù)P、數(shù)據(jù)擁有者的公鑰PKi、關(guān)鍵詞w以及等級(jí)條件項(xiàng)Con，輸出關(guān)鍵詞分段式索引結(jié)構(gòu)表I。

6)TrapGen(PKj,SKj,w)。輸入私鑰SKj和用戶查找的關(guān)鍵詞w，輸出w的陷門e。

7)Test(C,e,RKi → j)。輸入用戶的關(guān)鍵詞陷門e、可搜索密文C以及重加密轉(zhuǎn)換鍵RKi → j，輸出該用戶所屬等級(jí)下對(duì)應(yīng)的文件。

2.3 安全模型構(gòu)建

本文基于LWE的分等級(jí)可搜索加密方案可以通過(guò)以下安全游戲建立安全模型。

初始化階段 初始化系統(tǒng)公共參數(shù)P，生成主公鑰Mpk與主私鑰Msk。

密鑰生成階段 模擬器B運(yùn)行密鑰生成算法KeyGen，生成用戶i的密鑰對(duì)(PKi,SKi)，并將PKi發(fā)送給敵手A。

階段1 敵手A有能力自適應(yīng)地發(fā)出多次查詢，但每次只能查詢一個(gè)問(wèn)題。

私鑰查詢 敵手A適應(yīng)性地多次查詢用戶私鑰，如果查詢的用戶為條件控制列表內(nèi)合法用戶，模擬器B將該用戶的私鑰發(fā)送給敵手A；若不是合法用戶，則拒絕查詢。

陷門查詢 敵手A可以適應(yīng)性地多次查詢關(guān)鍵詞所對(duì)應(yīng)的陷門。選取任意關(guān)鍵詞w∈{0,1}*，適應(yīng)性地向挑戰(zhàn)者詢問(wèn)w所對(duì)應(yīng)的陷門Tw。

挑戰(zhàn)階段 敵手A選擇兩個(gè)目標(biāo)關(guān)鍵詞w0、w1和目標(biāo)身份i*作為挑戰(zhàn)對(duì)象，發(fā)送給模擬器B。其中，目標(biāo)身份i*的私鑰要求在第一階段未被查詢過(guò)，對(duì)目標(biāo)關(guān)鍵詞w0和w1的要求為不能選擇A之前詢問(wèn)過(guò)的關(guān)鍵詞，即w≠w0，w≠w1。模擬器B隨機(jī)選取b∈{0,1}，并將對(duì)應(yīng)的密文I=(C1,C2,{Con})發(fā)送給敵手A令其挑戰(zhàn)。

階段2 敵手A繼續(xù)適應(yīng)性地向模擬器B詢問(wèn)任何滿足條件w′≠w0，w′≠w1的關(guān)鍵詞所對(duì)應(yīng)的陷門。

猜測(cè)階段 敵手A最終輸出b′∈{0,1}，如果b=b′，則定義敵手A贏得了這場(chǎng)游戲。

在這場(chǎng)游戲中，定義敵手A贏得這場(chǎng)游戲的優(yōu)勢(shì)為ε=|Pr[b′=b]-1/2|，如果ε可以忽略，則稱AHSE方案是抵抗選擇關(guān)鍵詞攻擊的。

3 分段式索引結(jié)構(gòu)

現(xiàn)有帶索引的可搜索加密方案雖然在搜索效率上有一定的提升，但并未實(shí)現(xiàn)對(duì)多用戶分等級(jí)控制的功能，而現(xiàn)有具有訪問(wèn)控制的可搜索加密方案，通常使用屬性加密對(duì)用戶進(jìn)行訪問(wèn)控制，搜索時(shí)需對(duì)每一個(gè)文件先進(jìn)行用戶身份的邏輯判斷后再匹配關(guān)鍵詞，操作略為復(fù)雜，而對(duì)于分等級(jí)的應(yīng)用場(chǎng)景來(lái)說(shuō)，等級(jí)數(shù)目可靈活定義，以及等級(jí)可以靈活添加與刪除的索引結(jié)構(gòu)尤為重要，因此，本文針對(duì)分等級(jí)的應(yīng)用場(chǎng)景設(shè)計(jì)一種分段式索引結(jié)構(gòu)(如圖2)，具有以下特點(diǎn)：

圖2 分段式索引結(jié)構(gòu)Fig. 2 Segmented index structure

①該索引結(jié)構(gòu)具有分等級(jí)搜索功能，明確劃分了文件所屬的等級(jí)范圍，使不同等級(jí)的用戶在進(jìn)行關(guān)鍵詞搜索過(guò)程中，即使匹配到同一個(gè)關(guān)鍵詞，也能返回不同等級(jí)下對(duì)應(yīng)的文件。

②該索引結(jié)構(gòu)具有良好的適應(yīng)性。不同應(yīng)用場(chǎng)景對(duì)訪問(wèn)控制的粗細(xì)粒度需求不同，等級(jí)數(shù)目可以自由設(shè)置，有良好的適應(yīng)性。

③該索引結(jié)構(gòu)設(shè)置清晰簡(jiǎn)潔，文件的更新與刪除操作具有獨(dú)立性，可單一修改而不影響其他文件的訪問(wèn)控制，因此，該結(jié)構(gòu)操作簡(jiǎn)單靈活，易于維護(hù)，適用于動(dòng)態(tài)環(huán)境。

④該索引結(jié)構(gòu)能夠?qū)崿F(xiàn)不同等級(jí)用戶共享同一張索引表，在有效的等級(jí)權(quán)限控制前提下，無(wú)需對(duì)每個(gè)文件進(jìn)行逐一搜索，從而可以減少搜索時(shí)間，提高搜索效率；并且，該索引結(jié)構(gòu)基于反向索引構(gòu)造，具有亞線性的搜索效率。

⑤該索引表中的關(guān)鍵詞密文、等級(jí)控制項(xiàng)與條件鍵都基于LWE困難問(wèn)題構(gòu)建，能夠有效保證數(shù)據(jù)安全性。

3.1 索引表的建立、更新與刪除

分段式索引表采用鄰接表構(gòu)建。DO對(duì)文檔集合建立文件標(biāo)識(shí)符{id1,id2,…,idn}(n為文件總數(shù))。從文件中提取k個(gè)關(guān)鍵詞，表示為{w1,w2,…,wk}，對(duì)其進(jìn)行加密，即{Enc(w1),Enc(w2),…,Enc(wk)}。建立一個(gè)數(shù)組，存放每個(gè)關(guān)鍵詞的加密信息以及等級(jí)控制項(xiàng)Con1,Con2,Con3,…(根據(jù)實(shí)際需要的等級(jí)數(shù)量設(shè)置Con的數(shù)目)。對(duì)于每一個(gè)不同的等級(jí)，由此等級(jí)控制項(xiàng)Con作為鏈表頭節(jié)點(diǎn)，用指針鏈接該等級(jí)下控制的關(guān)鍵詞所對(duì)應(yīng)的文件，從而完成索引表的建立。

當(dāng)用戶發(fā)送的關(guān)鍵詞陷門匹配到某一關(guān)鍵詞時(shí)，用戶被分配的條件鍵與該關(guān)鍵詞所對(duì)應(yīng)的每一個(gè)Con控制項(xiàng)進(jìn)行匹配，當(dāng)找到該條件鍵可以匹配的控制項(xiàng)后，按照該控制項(xiàng)的指針讀取文件。當(dāng)不同級(jí)別的用戶同時(shí)匹配到同一個(gè)關(guān)鍵詞時(shí)，由控制項(xiàng)控制不同用戶級(jí)別，控制相應(yīng)的指針指向不同的文件節(jié)點(diǎn)，從而實(shí)現(xiàn)了不同級(jí)別的用戶可以搜索到不同范圍的文件。

更新與刪除：當(dāng)對(duì)索引表進(jìn)行更新時(shí)，DO首先判斷該文件所屬條件控制項(xiàng)，并根據(jù)該級(jí)別指針的索引插入到鏈表中對(duì)應(yīng)位置(如圖3中在第一等級(jí)下添加文件id11,id12,id14，在第二等級(jí)添加文件id9,id13,id15)；若需刪除文件，首先判斷文件是否是控制項(xiàng)指針指向的文件，如果是，則將該指針指向需要?jiǎng)h除的下一個(gè)文件，并將需要?jiǎng)h除文件的前一個(gè)文件指針指向需要?jiǎng)h除文件的下一個(gè)文件；否則，直接將需要?jiǎng)h除的文件前一個(gè)文件指針指向需要?jiǎng)h除文件的下一個(gè)文件即可(如圖3中在第二等級(jí)下刪除文件id7)。

圖3 不同等級(jí)下文件的更新與刪除操作Fig. 3 Update and deletion of files at different levels

3.2 等級(jí)的自適應(yīng)性

分段式索引結(jié)構(gòu)中等級(jí)控制項(xiàng)Con的數(shù)量具有自適應(yīng)性。為了簡(jiǎn)化描述，本文假定系統(tǒng)內(nèi)的合法成員有三個(gè)級(jí)別，即N=3，對(duì)應(yīng)圖2中具有3個(gè)等級(jí)控制項(xiàng)Con1、Con2、Con3。在實(shí)際的應(yīng)用場(chǎng)景中，可以根據(jù)實(shí)際需要的等級(jí)數(shù)量設(shè)置N的大小，即粒度可調(diào)節(jié)。圖4展示了等級(jí)控制項(xiàng)的更新與刪除，只需更新刪除對(duì)應(yīng)的等級(jí)控制項(xiàng)與其所帶的指針即可。顯然，該結(jié)構(gòu)可以實(shí)現(xiàn)任意數(shù)目的等級(jí)控制項(xiàng)，因此具有良好的自適應(yīng)性。

圖4 等級(jí)控制項(xiàng)的自適應(yīng)性Fig. 4 Adaptability of hierarchical control item

4 AHSE方案實(shí)現(xiàn)

本文提出基于LWE的自適應(yīng)等級(jí)可搜索加密方案，包括參數(shù)生成、密鑰生成、條件鍵生成、重加密轉(zhuǎn)換鍵生成、可搜索加密、陷門生成以及搜索測(cè)試7部分，本章展示其具體構(gòu)造，并在每部分后附上對(duì)應(yīng)的偽碼。

算法1 ParaGen。

輸入：n,q;

TA do:

A,TRA← TrapGen(q,n)

Mpk←A,Msk←TRA

算法2 KeyGen。

輸入：P,Mpk,Msk,i;

For eachDUi,TA do:

算法3 ConKeyGen。

輸入：P,v,t;

輸出：Con,CL。

TA do:

Definev=(V1,V2,…,Vl),t=(T1,T2,…,Tl),

for each level,TA do:

DefineCon=At·Sv

PublishCon

for eachDUi,TA do:

CreatCL← (PKi,Conkey′)

SendCLto PSS

算法4 ReKeyGen。

輸入：PKi,PKj;

輸出：RKi → j。

TA do:

算法5 REKS。

輸入：P,PKi,w,Gv;

輸出：I=(C1,C2,{Con})。

DO do:

ComputeC1←sTARi,C2←sTH(w)

Define File correspond withCon

Creat IndexI=(C1,C2,{Con})

算法6 TrapGen。

輸入：PKj,SKj,w;

輸出：e。

DU do:

u←H(w)

e← SamplePre(PKj,SKj,u,σ)

sendeto PSS

7)Test(C,e,RKi → j)。代理服務(wù)器PSS輸入來(lái)自PKj發(fā)送的陷門，執(zhí)行以下步驟：

①查找請(qǐng)求搜索的用戶是否在訪問(wèn)權(quán)限控制列表CL中，如果不存在，直接返回⊥，拒絕服務(wù)；如果存在，則找到并提取其對(duì)應(yīng)的條件鍵Conkey′，執(zhí)行下一步。

②代理服務(wù)器為其請(qǐng)求代理重加密轉(zhuǎn)換鍵RKi → j，對(duì)用戶發(fā)送的陷門以及關(guān)鍵詞密文進(jìn)行匹配，計(jì)算η=C2-C1·RKi → j·e，如果|η|≤q/4，則輸出1(“yes”)，否則輸出0(“no”)，并執(zhí)行下一步。

③在索引表中匹配到關(guān)鍵詞后執(zhí)行條件鍵匹配，計(jì)算α=β·Conkey′的文件，等式成立則根據(jù)滿足匹配的條件項(xiàng)所帶頭指針地址返回有效的文件。

算法7 Test。

輸入：C,e,RKi → j;

輸出：File。

PSS do:

if (exit(DUi))

returnConkey′

else return ⊥

requestRKi → j

computeη←C2-C1·RKi → j·e

if |η|≤q/4

output 1

else output 0

ifα==β·Conkey′

returnFile

5 正確性與安全性證明

5.1 正確性證明

本文方案中，每個(gè)用戶擁有獨(dú)立的條件鍵，即使一些用戶級(jí)別相同，但由于Sc是隨機(jī)選取的，因此每個(gè)用戶條件鍵Conkey′是不同的，保證了每個(gè)用戶的條件鍵的隨機(jī)性，從而使得僅從條件鍵分析不出用戶的等級(jí)，保護(hù)了用戶的權(quán)限級(jí)別隱私，其正確性為：

[V1G|V2G|…|VlG]·

本方案中，代理服務(wù)器收到數(shù)據(jù)用戶發(fā)來(lái)的關(guān)鍵詞陷門e后，查詢?cè)撚脩羰欠駷楹戏ㄓ脩?，然后為該用戶搜索分段式索引結(jié)構(gòu)表，從而進(jìn)行關(guān)鍵詞匹配測(cè)試δ=C2-C1·RKi → j·e，其正確性為：

sTH(w)=C2

根據(jù)文獻(xiàn)[24]中參數(shù)相關(guān)定義，在|δ|≤q/4時(shí)，輸出1(“yes”)；否則輸出0(“no”)。

5.2 安全性證明

本文AHSE方案依賴于LWE假設(shè)。為了證明AHSE的安全性，需要證明如果有攻擊者可以破壞AHSE的安全性，那么實(shí)際上可以利用一個(gè)敵手A來(lái)解決LWE問(wèn)題。由于沒(méi)有一種概率多項(xiàng)式時(shí)間(Probability Polynomial Time， PPT)算法能夠以不可忽略的概率解決LWE問(wèn)題，則表明本文方案是抵抗選擇關(guān)鍵詞攻擊的。

定理1 在隨機(jī)預(yù)言機(jī)模型下，假定存在一個(gè)PPT敵手A可以以不可忽略的概率優(yōu)勢(shì)成功攻破選擇關(guān)鍵詞攻擊游戲，那么可以構(gòu)造一個(gè)PPT算法B可以以不可忽略地概率優(yōu)勢(shì)ε成功解決LWE問(wèn)題。

證明 假設(shè)A是一個(gè)可以以不可忽略的優(yōu)勢(shì)攻破本文方案的敵手。構(gòu)造一個(gè)模擬器B，通過(guò)一個(gè)隨機(jī)預(yù)言機(jī)Ψ，決定輸出的樣本是從LWE分布中選取(Ψ0)或從均勻隨機(jī)的分布中選取(Ψ1)。模擬器B模擬挑戰(zhàn)者C并與敵手A交互，進(jìn)行選擇關(guān)鍵詞攻擊游戲的具體過(guò)程如下。

階段1 敵手每次只能查詢一個(gè)問(wèn)題，自適應(yīng)地多次發(fā)出以下查詢：

陷門查詢 敵手A可以自適應(yīng)地向模擬器B詢問(wèn)對(duì)于用戶i任意關(guān)鍵詞對(duì)應(yīng)的陷門(假定PKi的私鑰都已經(jīng)被查詢)。模擬器B通過(guò)SamplePre算法構(gòu)造陷門ei，如果生成成功，挑戰(zhàn)者C將ei發(fā)送給敵手A；否則終止操作。

階段2 敵手A繼續(xù)像階段1一樣發(fā)出關(guān)鍵詞陷門查詢，但仍然不能查詢A所要挑戰(zhàn)的關(guān)鍵詞w0和w1對(duì)應(yīng)的陷門，且目標(biāo)身份i*的私鑰依舊不能在第一階段被查詢過(guò)。

猜測(cè)階段 敵手A最終輸出猜測(cè)b′∈{0,1}。如果b=b′，那么模擬器B輸出1，判定A贏得了這場(chǎng)游戲；否則輸出0。定義1中定義了敵手A在游戲中的優(yōu)勢(shì)為|Pr[b=b′]-1/2|，且隨機(jī)預(yù)言機(jī)的采樣有以下兩種情況：

1)當(dāng)隨機(jī)預(yù)言機(jī)Ψη輸出為η=0時(shí)，為真實(shí)的LWE實(shí)例，敵手A的概率優(yōu)勢(shì)為ε，其中，η=0，Pr[b=b′|η=0]=1/2+ε。模擬器B攻破判定性LWE問(wèn)題的概率為Pr[η′=η|η=0]=1/2+ε。

2)當(dāng)隨機(jī)預(yù)言機(jī)Ψη輸出為η=1時(shí)，為均勻隨機(jī)采樣，敵手A沒(méi)有概率優(yōu)勢(shì)，其中，η=1，Pr[b≠b′|η=1]=1/2。模擬器B攻破判定性LWE問(wèn)題的概率為Pr[η′=η|η=1]=1/2。

挑戰(zhàn)密文的分布在統(tǒng)計(jì)上接近真實(shí)的安全環(huán)境，因?yàn)镃*是使用判定性LWE實(shí)例構(gòu)造的。如果LWE實(shí)例是真實(shí)的，則挑戰(zhàn)密文C*的分布將與LWE游戲中的分布相同。如果LWE實(shí)例是隨機(jī)的元素，那么C*中的元素也是隨機(jī)的。從上面的證明可以看出，如果對(duì)手A能夠打破這個(gè)方案，那么挑戰(zhàn)者C也可以利用模擬器B的算法攻破LWE問(wèn)題。已得出模擬器B的優(yōu)勢(shì)為ε/2，且定義概率優(yōu)勢(shì)ε是不可忽略的，從而得出結(jié)論，該算法可以以ε/2的概率攻破LWE困難問(wèn)題。又已知LWE困難問(wèn)題是不可攻破的，因此，結(jié)論矛盾，前提假設(shè)不成立，即，得以證明ε為可忽略的概率，因此，敵手A只能以可以忽略的優(yōu)勢(shì)贏得選擇關(guān)鍵詞攻擊游戲，該方案的安全性得以證明。

6 分析與比較

6.1 功能性分析

本文選出近年來(lái)可搜索加密領(lǐng)域與本文較為相關(guān)的文獻(xiàn)[17]方案、文獻(xiàn)[18]方案、文獻(xiàn)[9]方案、文獻(xiàn)[10]方案、文獻(xiàn)[19]方案、文獻(xiàn)[20]方案，與其功能比較如表1所示。從表中直觀看出，本文AHSE方案在多用戶環(huán)境下實(shí)現(xiàn)了公鑰可搜索加密、代理重加密、訪問(wèn)控制以及抗量子攻擊的功能。具體的分析如下。

表1 不同方案的功能比較 Tab. 1 Function comparison of different schemes

文獻(xiàn)[9]、[10]這兩個(gè)方案考慮到了訪問(wèn)控制，都采用屬性加密進(jìn)行訪問(wèn)控制。與其不同的是，AHSE采用自適應(yīng)的等級(jí)進(jìn)行訪問(wèn)控制，并且，屬性加密雖然在細(xì)粒度的訪問(wèn)控制上十分有效，但是同一屬性的用戶私鑰以及同一屬性加密的密文之間有一定的聯(lián)系，也就是說(shuō)，在屬性需要撤銷更新的情況下，與該屬性相關(guān)的密文以及用戶的私鑰不能保證獨(dú)立性，可能均需要更新，因此實(shí)際操作時(shí)較為繁瑣。本文AHSE中的用戶具有獨(dú)立的私鑰，條件鍵由系統(tǒng)控制，某一用戶動(dòng)態(tài)更新時(shí)，不會(huì)對(duì)其他用戶的私鑰造成影響。另外，文獻(xiàn)[9]方案與文獻(xiàn)[10]方案未考慮抗量子攻擊。

文獻(xiàn)[20]方案、文獻(xiàn)[19]方案分別是2017年和2018年提出的可搜索加密方案，二者均可抗量子攻擊，實(shí)現(xiàn)關(guān)鍵詞搜索功能，但二者均未考慮訪問(wèn)控制問(wèn)題。文獻(xiàn)[20]方案使用了可搜索廣播加密的方式，實(shí)現(xiàn)了多用戶數(shù)據(jù)共享，但對(duì)于用戶的訪問(wèn)只是粗粒度地分為數(shù)據(jù)共享與非共享兩種。文獻(xiàn)[19]方案中考慮的是單用戶場(chǎng)景，本文引入代理服務(wù)器，使代理服務(wù)器利用代理重加密轉(zhuǎn)換鍵，從而將方案拓展為多用戶搜索場(chǎng)景。

6.2 性能分析

根據(jù)不同文獻(xiàn)中出現(xiàn)的算法，定義psf表示運(yùn)行Pre-image Sample Function目標(biāo)圖像采樣算法的計(jì)算成本，tg表示運(yùn)行TrapGen陷門生成算法的計(jì)算成本，sb表示運(yùn)行SampleBasis短基生成算法的計(jì)算成本，sp表示運(yùn)行SamplePre預(yù)采樣算法的計(jì)算成本，bd表示運(yùn)行NewBasisDel新的格基生成算法的計(jì)算成本。mul僅表示矩陣之間乘法的計(jì)算成本，add表示矩陣之間加法的計(jì)算成本。由此，可以計(jì)算出AHSE的公鑰、私鑰、陷門以及密文的存儲(chǔ)開(kāi)銷分別為mnlogq、m2logq、mlogq和(m+1) logq。公私鑰生成、密文生成、陷門生成以及關(guān)鍵詞陷門匹配測(cè)試的計(jì)算開(kāi)銷分別是1tg、2mul+1add、1sp、2mul+1add。

文獻(xiàn)[17]、[18]方案為單用戶基于格密碼的可搜索加密方案，AHSE方案為多用戶基于格密碼的方案。表2與表3為文獻(xiàn)[17]、[18]方案與AHSE方案的存儲(chǔ)開(kāi)銷和計(jì)算開(kāi)銷?？梢钥闯觯诖鎯?chǔ)開(kāi)銷方面，AHSE方案的公鑰、私鑰、陷門以及密文的大小與文獻(xiàn)[17]、[18]方案相當(dāng)。計(jì)算開(kāi)銷方面，AHSE方案在公私鑰生成、密文生成、陷門生成階段與文獻(xiàn)[17]方案、文獻(xiàn)[18]方案相當(dāng)，而關(guān)鍵詞匹配搜索階段，計(jì)算開(kāi)銷略有增加，主要由AHSE從單用戶拓展至多用戶，使用代理重加密轉(zhuǎn)換技術(shù)所致。文獻(xiàn)[19]方案沒(méi)有細(xì)粒度的訪問(wèn)控制，僅分為數(shù)據(jù)共享與非共享兩種，可以看出，本文AHSE在實(shí)現(xiàn)了自適應(yīng)等級(jí)的訪問(wèn)控制下，計(jì)算開(kāi)銷與存儲(chǔ)開(kāi)銷性能表現(xiàn)優(yōu)于該方案。文獻(xiàn)[20]方案考慮的僅為單用戶場(chǎng)景，而本文將方案拓展為多用戶搜索場(chǎng)景?？梢詮谋?和表3看出，AHSE在具有良好的訪問(wèn)控制下，存儲(chǔ)開(kāi)銷與計(jì)算開(kāi)銷方面表現(xiàn)良好。最后，文獻(xiàn)[21]方案針對(duì)數(shù)據(jù)擁有者設(shè)計(jì)了代理，即減輕原始數(shù)據(jù)所有者的數(shù)據(jù)處理負(fù)擔(dān)，但比較數(shù)據(jù)可以看出，本文AHSE方案不僅適用于多用戶，并且在計(jì)算及存儲(chǔ)開(kāi)銷方面表現(xiàn)優(yōu)于該方案。

表2 不同方案的存儲(chǔ)開(kāi)銷比較 Tab. 2 Memory overhead comparison of different schemes

表3 不同方案的計(jì)算開(kāi)銷比較 Tab. 3 Computation overhead comparison of different schemes

對(duì)于帶有訪問(wèn)控制的密文搜索方案，AHSE中使用分段式索引結(jié)構(gòu)，搜索時(shí)間復(fù)雜度為Ο(K)，而其他現(xiàn)有帶訪問(wèn)控制的可搜索加密方案[25-27]的搜索時(shí)間復(fù)雜度為Ο(MN)。其中，K為本文索引中使用的關(guān)鍵詞個(gè)數(shù)，N為所有文件個(gè)數(shù)，M為每個(gè)文件中的關(guān)鍵詞個(gè)數(shù)。如果所有文件的關(guān)鍵詞都不相同，則K=MN；但是，在實(shí)際情況中，特定應(yīng)用場(chǎng)景或某一領(lǐng)域數(shù)據(jù)庫(kù)文件數(shù)據(jù)相關(guān)性較大，不同文件的關(guān)鍵詞重復(fù)率較高，即K?MN，因此本搜索方案可以有效提高搜索效率。

7 結(jié)語(yǔ)

針對(duì)現(xiàn)有分等級(jí)可搜索加密方案不能有效抵抗量子攻擊以及不能靈活添加與刪除某一個(gè)或多個(gè)等級(jí)的問(wèn)題，本文提出一種基于LWE的自適應(yīng)等級(jí)可搜索加密方案，通過(guò)構(gòu)造簡(jiǎn)單靈活的條件鍵，為用戶分配不同的等級(jí)，實(shí)現(xiàn)有效的等級(jí)訪問(wèn)控制；同時(shí)本文設(shè)計(jì)一種分段式索引結(jié)構(gòu)，其等級(jí)具有良好的自適應(yīng)性，能夠靈活添加與刪除，滿足了加密數(shù)據(jù)庫(kù)、云醫(yī)療等系統(tǒng)對(duì)不同粒度訪問(wèn)控制的需求；并且，該方案中用戶和文件的更新、刪除以及等級(jí)變動(dòng)易于操作，適用于動(dòng)態(tài)環(huán)境。最后，本文并未考慮格上多對(duì)多應(yīng)用場(chǎng)景，以及更靈活的多關(guān)鍵詞可搜索加密技術(shù)，但它們是實(shí)際生活對(duì)可搜索加密技術(shù)的同等需求，同樣是下一步將要研究的方向。