支持關(guān)鍵詞任意連接搜索的屬性加密方案

宋衍，韓臻，陳棟，趙進(jìn)華

(1.北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044；2.信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100072)

支持關(guān)鍵詞任意連接搜索的屬性加密方案

宋衍1,2，韓臻1，陳棟1,2，趙進(jìn)華2

(1.北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044；2.信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100072)

構(gòu)建一種基于素?cái)?shù)階雙線性群的可搜索加密方案?；趯傩约用?，實(shí)現(xiàn)每個(gè)關(guān)鍵詞密文能夠被多個(gè)用戶(hù)私鑰搜索，顯著降低細(xì)粒度訪問(wèn)控制帶來(lái)的網(wǎng)絡(luò)帶寬和發(fā)送節(jié)點(diǎn)的處理開(kāi)銷(xiāo)?；诙囗?xiàng)式方程，支持對(duì)關(guān)鍵詞的任意連接搜索，顯著提高連接搜索的靈活性。對(duì)方案的性能進(jìn)行了分析，并與現(xiàn)有的連接關(guān)鍵詞搜索方案進(jìn)行了比較。

可搜索加密；屬性加密；連接關(guān)鍵詞；多項(xiàng)式方程

1 引言

隨著云計(jì)算的快速發(fā)展，數(shù)據(jù)外包成為一種廣泛的應(yīng)用形式。數(shù)據(jù)使用者只是享受云環(huán)境提供的數(shù)據(jù)服務(wù)，而不用購(gòu)買(mǎi)和維護(hù)自己的信息系統(tǒng)。這樣一是能夠提高數(shù)據(jù)管理的專(zhuān)業(yè)化程度，改善數(shù)據(jù)應(yīng)用效率，二是用戶(hù)能夠根據(jù)需要隨意地增加和裁減服務(wù)的功能和容量，降低信息化投入。但是用戶(hù)在享受云存儲(chǔ)服務(wù)的同時(shí)，需要將數(shù)據(jù)交由云端的服務(wù)提供者來(lái)進(jìn)行存儲(chǔ)和處理。其最主要的特征是：數(shù)據(jù)與其所有者分離，處于所有者不可控的區(qū)域內(nèi)[1]。

在不可控環(huán)境中，加密是保證數(shù)據(jù)安全的最有效方法。但是，加密破壞了原有數(shù)據(jù)的值和大小關(guān)系等，密文不再具有可供檢索的語(yǔ)義和統(tǒng)計(jì)特性，因此，針對(duì)明文的檢索技術(shù)并不能直接應(yīng)用于密文。傳統(tǒng)的處理方式是：服務(wù)提供者將所有滿(mǎn)足訪問(wèn)控制策略的密文都返回給請(qǐng)求者，由請(qǐng)求者解密后再進(jìn)行明文的檢索。這種方法簡(jiǎn)單易行，但是，一方面，云端的計(jì)算和存儲(chǔ)等資源優(yōu)勢(shì)無(wú)法得到有效利用，另一方面，返回大量數(shù)據(jù)需要占用相當(dāng)多的網(wǎng)絡(luò)帶寬，解密也會(huì)給請(qǐng)求者帶來(lái)很大的計(jì)算量，因此，對(duì)客戶(hù)機(jī)配置和網(wǎng)絡(luò)質(zhì)量有很高的要求，同時(shí)其效率也是不能被接受的。

為了更好地解決這個(gè)問(wèn)題，可搜索加密（searchable encryption）應(yīng)運(yùn)而生，并在近幾年中得到了廣泛研究和快速發(fā)展[2]。2000年，Song等[3]提出了實(shí)用的可搜索對(duì)稱(chēng)加密方案，僅需要用戶(hù)與服務(wù)器之間的一次交互，每項(xiàng)檢索耗費(fèi)的工作時(shí)間是線性的。對(duì)稱(chēng)可搜索加密方案的優(yōu)點(diǎn)是效率高、安全性好，但缺點(diǎn)是僅適用于用戶(hù)檢索自己事先存儲(chǔ)到云端服務(wù)器上的密文數(shù)據(jù)。2004年，Boneh等[4]利用公鑰密碼算法構(gòu)造了一個(gè)可搜索加密方案（PEKS），解決了對(duì)其他用戶(hù)的加密數(shù)據(jù)進(jìn)行檢索的難題。

鑒于一次搜索多個(gè)關(guān)鍵詞能夠縮小搜索范圍改進(jìn)搜索性能[5]，Golle等[6]提出了關(guān)鍵詞連接搜索的概念和安全模型，給出了2種連接關(guān)鍵詞搜索方案；但是，該方案基于對(duì)稱(chēng)密鑰加密和搜索關(guān)鍵詞，應(yīng)用環(huán)境受限。2005年，Park等[7]基于雙線性映射提出了一種公鑰密碼系統(tǒng)連接關(guān)鍵詞搜索方案（PKCKS）。Hwang等[8]也基于雙線性映射設(shè)計(jì)了一種PKCKS方案，并且將方案擴(kuò)展到多用戶(hù)環(huán)境；但是，采用多對(duì)公私鑰的形式，給密鑰管理帶來(lái)較大負(fù)擔(dān)。2007年，Boneh等[9]提出的基于謂詞加密的概念，利用合數(shù)階雙線性群構(gòu)造了一種支持連接關(guān)鍵詞的可搜索加密方案，并擴(kuò)展到子集和比較搜索；但是，方案需要較大的群空間。Katz等[10]介紹了一種基于內(nèi)積向量的謂詞加密可搜索方案，并給出了在匿名身份加密、隱藏向量加密、關(guān)鍵詞合?。ㄟB接關(guān)鍵詞）、關(guān)鍵詞析取和多項(xiàng)式方程搜索等方面的實(shí)現(xiàn)思路。Chen等[11]提出了一種基于時(shí)間戳的PKCKS，能夠減小服務(wù)器在搜索時(shí)的運(yùn)算量；但是，服務(wù)器需要利用密文生成時(shí)間戳，而數(shù)據(jù)請(qǐng)求者需要獲取每個(gè)時(shí)間戳的一個(gè)組件來(lái)生成相應(yīng)的陷門(mén)。Zhang等[12]提出一種支持連接關(guān)鍵詞子集搜索的PKCKS，但是用戶(hù)計(jì)算量較大。Yang等[13]提出一種指定搜索者、支持代理重加密的 PKCKS方案，能夠抵御關(guān)鍵詞猜測(cè)攻擊（keyword guessing attack）。Chen等[14]使用合數(shù)階群和素?cái)?shù)階群分別提出了2種PECKS方案，但無(wú)法實(shí)現(xiàn)關(guān)鍵詞域的子集搜索，如果需要支持所有可能的連接搜索，就會(huì)導(dǎo)致密文成指數(shù)增長(zhǎng)。Wang等[15]采用授權(quán)用戶(hù)和云端服務(wù)器先后對(duì)關(guān)鍵詞加密的方式，基于偽隨機(jī)函數(shù)提出了一種連接關(guān)鍵詞搜索方案，陷門(mén)大小固定，適用于多用戶(hù)環(huán)境；但是，如果服務(wù)提供者與任意一個(gè)數(shù)據(jù)請(qǐng)求者共謀，則能夠破解方案的主密鑰，同時(shí)，基于對(duì)稱(chēng)密鑰來(lái)加密和搜索關(guān)鍵詞，應(yīng)用環(huán)境受限。

目前，絕大多數(shù)的連接關(guān)鍵詞搜索方案采用了Golle[6]的假設(shè)，設(shè)置關(guān)鍵詞域來(lái)對(duì)位搜索和被搜索的關(guān)鍵詞。這種方式對(duì)于結(jié)構(gòu)化、語(yǔ)義確定的數(shù)據(jù)具有較高的搜索效率，如郵件的首部信息；但是，對(duì)于非結(jié)構(gòu)化的數(shù)據(jù)，則很難用固定的關(guān)鍵詞域覆蓋所有文件的準(zhǔn)確內(nèi)容[16]。因此，在實(shí)用性上有一定限制。

除此之外，已有可搜索加密方案大都針對(duì)數(shù)據(jù)擁有者與請(qǐng)求者是“一對(duì)一”的情形，在越來(lái)越多的信息共享的大背景下，這些方案顯然不適合多方搜索的需求。屬性加密將應(yīng)用場(chǎng)景擴(kuò)展到“一對(duì)多”的情況，一個(gè)密文可以選擇性地由多個(gè)特定用戶(hù)解密。Li等[17]基于密鑰策略的屬性加密實(shí)現(xiàn)了一種單關(guān)鍵詞的可搜索加密方案，但是在陷門(mén)中，關(guān)鍵詞組件和訪問(wèn)樹(shù)組件沒(méi)有關(guān)聯(lián)，容易被服務(wù)提供者和數(shù)據(jù)請(qǐng)求者的共謀所仿冒。Zheng等[18]基于密鑰策略和密文策略的屬性加密分別提出了2種可搜索加密方案，并且支持搜索的可驗(yàn)證。到現(xiàn)在為止，還沒(méi)有支持連接關(guān)鍵詞搜索的屬性加密方案。

針對(duì)以上2個(gè)問(wèn)題，本文提出一種新的連接關(guān)鍵詞可搜索屬性加密方案，文檔無(wú)需按照關(guān)鍵詞域來(lái)設(shè)置關(guān)鍵詞，搜索運(yùn)算時(shí)無(wú)需對(duì)位密文和陷門(mén)中的關(guān)鍵詞。方案基于屬性關(guān)聯(lián)實(shí)現(xiàn)搜索的細(xì)粒度訪問(wèn)控制，基于多項(xiàng)式方程實(shí)現(xiàn)關(guān)鍵詞的任意連接搜索。具有較高的安全性，能夠抵御選擇關(guān)鍵詞攻擊（CKA,chosen keyword attack）。

2 預(yù)備知識(shí)

2.1 雙線性群及復(fù)雜性假設(shè)

假設(shè)p為素?cái)?shù)，G1、G2和GT為p階循環(huán)群，g1、g2和 gT分別為其生成元。e∶ G1×G2→GT為雙線性映射，則有：

1)?h1∈G1,h2∈G2，?a,b∈Zp，滿(mǎn)足 e(h1a,

3)G1、G2和GT中的運(yùn)算以及雙線性映射e都是在多項(xiàng)式時(shí)間內(nèi)可完成的。

假設(shè)1m維判定性Diffie-Hellman（m-DDH）問(wèn)題。隨機(jī)選擇給定元組判斷等式 x=gam是否成立是困難的。

2.2 系統(tǒng)模型

系統(tǒng)包括4個(gè)參與角色，記為{UM,Serv,DO,DReq}。其中，UM 是授權(quán)管理機(jī)構(gòu)，負(fù)責(zé)系統(tǒng)的初始化，并管理用戶(hù)的屬性及其密鑰生成；Serv是云端的服務(wù)提供者，負(fù)責(zé)數(shù)據(jù)的存儲(chǔ)和搜索；DO是數(shù)據(jù)擁有者，將自己的數(shù)據(jù)加密后交由Serv存儲(chǔ)和管理；DReq是數(shù)據(jù)請(qǐng)求者，向Serv請(qǐng)求數(shù)據(jù)搜索服務(wù)。UM是完全可信的，并且UM與DReq的對(duì)話是安全的；Serv是“誠(chéng)實(shí)但狡猾”的，能夠忠實(shí)地執(zhí)行規(guī)定的操作，但可能會(huì)竊取數(shù)據(jù)的信息，或與DReq發(fā)起共謀攻擊。方案的系統(tǒng)模型及工作流程如圖1所示。

1)UM管理所有用戶(hù)的屬性集合；UM調(diào)用初始化算法生成公開(kāi)參數(shù)和主私鑰；公開(kāi)參數(shù)用于數(shù)據(jù)加密、用戶(hù)私鑰生成、陷門(mén)生成和密文搜索算法，發(fā)布給系統(tǒng)的合法用戶(hù)；主私鑰用于生成用戶(hù)私鑰，由UM保存。

2)DO向UM申請(qǐng)系統(tǒng)的公開(kāi)參數(shù)。

3)UM將公開(kāi)參數(shù)返回給DO。

4)DO從文檔中選出關(guān)鍵詞集合，調(diào)用對(duì)稱(chēng)算法加密文檔，對(duì)稱(chēng)加密算法選用現(xiàn)有的 3DES或AES等即可。

5)DO制定訪問(wèn)控制策略，調(diào)用屬性加密公鑰算法分別加密對(duì)稱(chēng)加密密鑰和關(guān)鍵詞集合。

6)DO將文檔密文、對(duì)稱(chēng)密鑰密文和關(guān)鍵詞集合密文組成數(shù)據(jù)密文，發(fā)送給Serv存儲(chǔ)。

7)DReq如果已經(jīng)申請(qǐng)過(guò)用戶(hù)私鑰，則進(jìn)入10)，否則向UM申請(qǐng)用戶(hù)私鑰。

8)UM調(diào)用私鑰生成算法，生成與用戶(hù)屬性集匹配的用戶(hù)私鑰。

9)UM將用戶(hù)私鑰通過(guò)安全方式返回給DReq，如用DReq的公鑰加密。

10)DReq調(diào)用陷門(mén)生成算法，生成被搜索關(guān)鍵詞集合相應(yīng)的陷門(mén)；陷門(mén)是關(guān)鍵詞集合的一個(gè)單向函數(shù)值，能夠用于關(guān)鍵詞的判斷，而不會(huì)泄露關(guān)鍵詞的信息。

11)DReq將自身的屬性集和陷門(mén)發(fā)送給Serv。

12)Serv首先根據(jù)DReq的屬性集篩選滿(mǎn)足訪問(wèn)控制策略的數(shù)據(jù)密文，然后調(diào)用搜索算法，對(duì)搜索關(guān)鍵詞集合的密文和被搜索關(guān)鍵詞集合的陷門(mén)進(jìn)行運(yùn)算，驗(yàn)證同時(shí)滿(mǎn)足訪問(wèn)控制策略和搜索策略的數(shù)據(jù)密文；如果陷門(mén)所屬的DReq滿(mǎn)足密文的訪問(wèn)控制策略，并且陷門(mén)的關(guān)鍵詞集合包含于密文所代表的關(guān)鍵詞集合，則結(jié)果為一個(gè)固定值，否則結(jié)果為隨機(jī)值。

13)將滿(mǎn)足要求的文檔密文和對(duì)稱(chēng)密鑰密文返回給DReq。

14)DReq利用自己掌握的用戶(hù)私鑰，調(diào)用屬性加密公鑰算法，解密對(duì)稱(chēng)密鑰；如果DReq滿(mǎn)足訪問(wèn)控制策略要求，則能夠得出正確的對(duì)稱(chēng)密鑰，接著調(diào)用對(duì)稱(chēng)加密算法解密出文檔明文，否則，不能得出正確的對(duì)稱(chēng)密鑰，無(wú)法解密出文檔明文。

圖1 系統(tǒng)模型及工作流程

在 12)中，雖然搜索算法能夠辨別出密文是否同時(shí)滿(mǎn)足訪問(wèn)控制策略和搜索策略，但是由 Serv首先根據(jù)DReq的屬性集篩選滿(mǎn)足訪問(wèn)控制策略的數(shù)據(jù)密文，則可以在計(jì)算之前就過(guò)濾掉不滿(mǎn)足訪問(wèn)控制策略的數(shù)據(jù)密文，從而減少搜索算法的調(diào)用次數(shù)，降低計(jì)算開(kāi)銷(xiāo)。

在9)中對(duì)用戶(hù)私鑰的公鑰算法加密，在4)、14)中對(duì)文檔的對(duì)稱(chēng)算法加解密以及第5)、14)中對(duì)對(duì)稱(chēng)密鑰的屬性算法加解密，均有成熟技術(shù)可用，這里不再做研究。因此，本文之后的章節(jié)將忽略對(duì)文檔及其對(duì)稱(chēng)密鑰的處理，而只考慮關(guān)鍵詞的處理。經(jīng)過(guò)簡(jiǎn)化后，一個(gè)支持關(guān)鍵詞任意連接搜索的基于屬性加密方案由以下5種多項(xiàng)式時(shí)間算法組成。

1)Setup(1λ)→(pm,mk)∶ UM 執(zhí)行該算法以初始化系統(tǒng)；輸入一個(gè)安全參數(shù)1λ，輸出一個(gè)公開(kāi)參數(shù)pm和一個(gè)主私鑰mk。

2)KeyGen(Atts,mk,pm)→sk∶ UM 根據(jù) DReq 提供的屬性集為其生成相應(yīng)的用戶(hù)私鑰；輸入公開(kāi)參數(shù)pm、主私鑰mk和DReq的屬性集Atts，輸出對(duì)應(yīng)的私鑰sk。

3)Encrypt(pm,W,T)→cph∶ DO根據(jù)訪問(wèn)控制策略加密文檔的關(guān)鍵詞集合；輸入公開(kāi)參數(shù) pm、文檔的關(guān)鍵詞集合W，以及訪問(wèn)結(jié)構(gòu)T，輸出密文cph。

4)TokenGen(sk,pm,W′)→tk∶ DReq 生成搜索陷門(mén)；輸入公開(kāi)參數(shù)pm，用戶(hù)私鑰sk，關(guān)鍵詞集合W′，輸出關(guān)鍵詞集合的陷門(mén)tk。

5)Search(tk,cph)→1∶Serv根據(jù)陷門(mén)對(duì)密文進(jìn)行搜索；輸入陷門(mén)tk和密文cph，若用戶(hù)的屬性集Atts滿(mǎn)足密文的訪問(wèn)結(jié)構(gòu)T，并且搜索的關(guān)鍵詞集合W′包含于文檔的關(guān)鍵詞集合W，則返回1，否則返回隨機(jī)值。

方案特點(diǎn)為：1)每個(gè)密文（本文以后提到的密文都指文檔關(guān)鍵詞集合的密文）都可以指定多個(gè)不同的用戶(hù)私鑰進(jìn)行搜索；2)每個(gè)用戶(hù)私鑰都可以對(duì)不同的密文（這些密文可以由不同的DO生成）進(jìn)行搜索；3)每個(gè)密文都支持對(duì)其中關(guān)鍵詞的任意連接的搜索。

2.3 訪問(wèn)控制

使用樹(shù)形結(jié)構(gòu)表示訪問(wèn)控制策略，具有清晰、簡(jiǎn)便的優(yōu)點(diǎn)[19]。訪問(wèn)樹(shù)的內(nèi)部節(jié)點(diǎn)代表關(guān)系（門(mén)），包括 and（與）、or（或）和 threshold（門(mén)限）；葉子節(jié)點(diǎn)代表屬性。假設(shè)numv為節(jié)點(diǎn)v下子節(jié)點(diǎn)的個(gè)數(shù)，kv為節(jié)點(diǎn)v的門(mén)限值，則有1≤kv≤numv。2種特別的情況是，當(dāng)kv=1時(shí)，節(jié)點(diǎn)v代表關(guān)系or；當(dāng)kv=numv時(shí)，節(jié)點(diǎn)v代表關(guān)系and。使用parent(v)表示節(jié)點(diǎn)v的父節(jié)點(diǎn)，ind(v)表示節(jié)點(diǎn)v在父節(jié)點(diǎn)下的索引號(hào)，lvs(T)表示訪問(wèn)樹(shù)T中所有葉子節(jié)點(diǎn)組成的集合，att(v)表示葉子節(jié)點(diǎn)v所代表的屬性，Tv表示T中根為v的子樹(shù)。

給定一個(gè)屬性集合Atts，F(xiàn)(Atts,Tv)=1表示Atts滿(mǎn)足樹(shù) Tv代表的訪問(wèn)控制策略，F(xiàn)(Atts,Tv)=0表示Atts不滿(mǎn)足樹(shù) Tv代表的訪問(wèn)控制策略。那么F(Atts,Tv)的取值可以通過(guò)下列方式遞歸確定。

1)當(dāng)v是葉子節(jié)點(diǎn)時(shí)，如果att(v)∈Atts，則設(shè)置F(Atts,Tv)=1；否則F(Atts,Tv)=0。

2)當(dāng) v是內(nèi)部節(jié)點(diǎn)時(shí)，假設(shè)v1,v2,…,vnum為v的子節(jié)點(diǎn)，如果存在一個(gè)子集 I?{1,…,numv}使|I|≥kv，并且對(duì)于?j∈I，有那么設(shè)置F(Atts,Tv)=1；否則，設(shè)置F(Atts,Tv)=0。

對(duì)于訪問(wèn)樹(shù)T，本文將T的秘密共享算法表示為

算法從上至下為T(mén)中的每個(gè)內(nèi)部節(jié)點(diǎn)v構(gòu)造一個(gè) kv?1次一元多項(xiàng)式 qv，并為每個(gè)內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)賦值。

1)如果v是T的根節(jié)點(diǎn)，設(shè)置qv(0)=q，并為多項(xiàng)式qv隨機(jī)選取kv?1個(gè)系數(shù)。

2)如果v是T中除根節(jié)點(diǎn)外的其他內(nèi)部節(jié)點(diǎn)，設(shè)置qv(0)=qparent(v)(ind(v))，并為多項(xiàng)式qv隨機(jī)選取kv?1 個(gè)系數(shù)。

3)如果 v是 T的葉子節(jié)點(diǎn)，設(shè)置 qv(0)=qpar-ent(v)(ind(v))。

根據(jù)訪問(wèn)樹(shù)T的結(jié)構(gòu)，算法從底向上執(zhí)行如下步驟。

對(duì)于節(jié)點(diǎn) v，如果 F(att(u1),…,att(um),Tv)=0，則繼續(xù)；

否則，F(xiàn)(att(u1),…,att(um),Tv)=1，則

如果v是葉子節(jié)點(diǎn)，則存在一個(gè)uj，使uj=v；設(shè)置

3 方案設(shè)計(jì)

3.1 方案構(gòu)造

DO可以任意設(shè)置文檔的關(guān)鍵詞集合，沒(méi)有域的劃分，沒(méi)有關(guān)鍵詞個(gè)數(shù)、位置的限制。假設(shè)H∶{0,1}*→Zp是一個(gè)安全的單向散列函數(shù)，將位串隨機(jī)的映射到群Zp中。G1、G2和GT為p階循環(huán)群，g1、g2和 gT分別為其生成元，e∶G1×G2→GT為雙線性映射。方案的詳細(xì)描述如下。

1)Setup(1λ)。運(yùn)行算法 G(1λ)獲得(p,G1,G2,GT,e)。隨機(jī)選取b,c,d∈Zp*，發(fā)布公開(kāi)參數(shù)為

保存主密鑰為

2)KeyGen(Atts,mk,pm)。構(gòu)造屬性集 Atts對(duì)應(yīng)的私鑰。隨機(jī)選擇，計(jì)算對(duì)于每個(gè) attj∈Atts，隨機(jī)選擇 rj∈Zp*，計(jì)算構(gòu)造私鑰如下

3)Encrypt(pm,W,T)。加密關(guān)鍵詞集合 W={w1,…,wm}。隨機(jī)選取q∈Zp作為訪問(wèn)樹(shù)T的秘密共享值，執(zhí)行{qv(0)|v∈lvs(T)}←Share(T,q)，使T中的每個(gè)葉子節(jié)點(diǎn) v得到一個(gè)關(guān)于 q的秘密共享值qv(0)，并為每個(gè)葉子節(jié)點(diǎn)計(jì)算和隨機(jī)選擇構(gòu)造一個(gè) m次多項(xiàng)式為

4)TokenGen(Atts,sk,pm,W′)。構(gòu)造關(guān)鍵詞集合對(duì)應(yīng)的陷門(mén)，其中，t≤m。隨機(jī)選取計(jì)算這部分工作在線下提前完成。對(duì)于每個(gè) i∈{0,1,…,m}，計(jì)算構(gòu)造關(guān)鍵詞陷門(mén)為

5)Search(tk,cph)。根據(jù)密文中的訪問(wèn)樹(shù)T和陷門(mén)tk中的屬性集Atts，服務(wù)器從Atts中選擇一個(gè)滿(mǎn)足T的屬性子集S。如果S不存在，則返回0；否則，對(duì)于每個(gè)attj∈S，找到與之相應(yīng)的att(v)=attj，計(jì)算T中葉子節(jié)點(diǎn)的秘密值為

然后計(jì)算根節(jié)點(diǎn)的秘密值

3.2 正確性驗(yàn)證

做如下計(jì)算

當(dāng)搜索的關(guān)鍵詞集合包含于文檔的關(guān)鍵詞集合，即W′∈W時(shí)，有當(dāng)屬性集Atts滿(mǎn)足訪問(wèn)樹(shù)T，即F(Atts,T)=1時(shí)，有因此

4 方案分析

4.1 安全性分析

實(shí)現(xiàn)訪問(wèn)控制的基本思想是：將每個(gè)陷門(mén)和密文分為 2部分：1)與關(guān)鍵詞明文相關(guān)聯(lián)；2)與屬性相關(guān)聯(lián)，陷門(mén)中的屬性表示DReq的屬性集，密文中的屬性表示DO的訪問(wèn)控制策略。如果DReq的屬性集滿(mǎn)足DO的訪問(wèn)控制策略，服務(wù)器能夠通過(guò)雙線性映射算法確定密文的關(guān)鍵詞集合是否包含陷門(mén)的關(guān)鍵詞集合。實(shí)現(xiàn)任意連接搜索的基本思想是：利用文檔的所有關(guān)鍵詞和2個(gè)隨機(jī)數(shù)構(gòu)造一個(gè)次數(shù)等于關(guān)鍵詞個(gè)數(shù)的多項(xiàng)式，將多項(xiàng)式的系數(shù)以?xún)绲男问桨l(fā)布；如果所搜索的關(guān)鍵詞都包含在文檔的關(guān)鍵詞集合中，則能夠利用拉格朗日插值公式還原出該隨機(jī)數(shù)，否則，返回結(jié)果不正確。

方案在私鑰生成、密文生成和陷門(mén)生成階段，分別使用隨機(jī)數(shù)將各組件關(guān)聯(lián)化和隨機(jī)化。以下從3個(gè)方面來(lái)說(shuō)明或證明方案的安全性。

1)陷門(mén)不可偽造。DReq隨機(jī)選擇大數(shù) s，使陷門(mén)的每個(gè)組件都是以s為指數(shù)的冪，如此以來(lái)，每個(gè)組件都通過(guò)s相關(guān)聯(lián)。在離散對(duì)數(shù)困難問(wèn)題假設(shè)下，攻擊者無(wú)法通過(guò)已用陷門(mén)中的組件求解得到隨機(jī)數(shù)s的值，并偽造新陷門(mén)。當(dāng)攻擊者隨機(jī)選擇s來(lái)偽造陷門(mén)時(shí)，只能構(gòu)造陷門(mén)的組件H，還必須獲得用戶(hù)私鑰來(lái)構(gòu)造陷門(mén)的組件tok0、tok1、A和B。

2)用戶(hù)私鑰不可偽造。用戶(hù)私鑰中的組件 Bj通過(guò)隨機(jī)數(shù)rj與組件Aj相關(guān)聯(lián)，組件K通過(guò)隨機(jī)數(shù)r與Aj相關(guān)聯(lián)。由于不同攻擊者的用戶(hù)私鑰所選取的隨機(jī)數(shù)不同，所以，即使攻擊者們的屬性組合能夠包含某DReq的屬性集合，也無(wú)法以共謀的方式通過(guò)組件組合獲得該DReq的私鑰。用戶(hù)私鑰中的組件在用于陷門(mén)時(shí)，都以隨機(jī)數(shù)s為指數(shù)進(jìn)行了冪運(yùn)算，在離散對(duì)數(shù)困難問(wèn)題假設(shè)下，保證了用戶(hù)私鑰的安全性。

3)CKA安全性。在m-DDH假設(shè)下，本文方案是CKA安全的。下面用反證法予以證明。

證明假設(shè)本文方案在下面的 CKA安全游戲中是不安全的，那么存在一個(gè) PPT算法A能夠贏得安全游戲，而本文可以構(gòu)造出一個(gè)PPT算法S利用A攻破m-DDH假設(shè)。假設(shè)gβ為群Gβ的生成元，隨機(jī)取 a∈Zp*{1}，x∈Gβ，生成S的挑戰(zhàn)元組其中，

1)初始化。S取G2=Gβ和g2=gβ，隨機(jī)選取b,c,d∈Zp*，保存主密鑰 mk=(b,c,d)和公開(kāi)參數(shù)并生成用戶(hù)私鑰。為了保證詢(xún)問(wèn)的一致性，S保存元組(wi,j,xi,j)的列表，記為L(zhǎng)。A選擇多項(xiàng)式數(shù)量的關(guān)鍵詞集合，向S詢(xún)問(wèn)相應(yīng)的密文。假設(shè)其中一個(gè)關(guān)鍵詞集合為 Wi=(wi,1,…,wi,m)，對(duì)于每個(gè) wi,j∈Wi，如果未被詢(xún)問(wèn)過(guò)，S隨機(jī)選擇xi,j∈Zp作為H(wi,j)，并將元組(wi,j,xi,j)加入到列表L中；如果已經(jīng)被詢(xún)問(wèn)過(guò)，則S返回列表 L中相應(yīng)元組的 xi,j。接著，S按照3.1節(jié)中的Encrypt算法生成關(guān)鍵詞集合Wi的密文，并發(fā)送給A。

2)詢(xún)問(wèn)階段1。A詢(xún)問(wèn)關(guān)鍵詞集合的陷門(mén)。假設(shè)其中一個(gè)關(guān)鍵詞集合為對(duì)于每個(gè) wq′,t∈ Wq′ ，如果已經(jīng)在之前詢(xún)問(wèn)的密文或陷門(mén)中出現(xiàn)過(guò)，則S返回列表 L中相應(yīng)元組的 xi,j作為其；否則隨機(jī)選擇xq,i∈Zp作為其同樣，元組被加入到列表L中保存。接下來(lái)，S按照3.1節(jié)中的TokenGen算法生成關(guān)鍵詞集合Wq′的陷門(mén)。由于當(dāng)關(guān)鍵詞wq′,i出現(xiàn)在不同的詢(xún)問(wèn)中時(shí)，S前后使用同一個(gè)散列值；因此，生成的陷門(mén)是關(guān)鍵詞集合Wq′的正確陷門(mén)。在收到陷門(mén)后，A調(diào)用搜索算法Search對(duì)每個(gè)密文進(jìn)行搜索，看關(guān)鍵詞集合Wq′是否包含于某些密文的關(guān)鍵詞集合中。

3)挑戰(zhàn)。在經(jīng)過(guò)多項(xiàng)式數(shù)量的詢(xún)問(wèn)后，A開(kāi)始挑戰(zhàn)。A選擇2個(gè)關(guān)鍵詞集合W0={w0,1,…,w0,m}和W1={w1,1,…,w1,m}發(fā)送給S，要求A沒(méi)有詢(xún)問(wèn)過(guò)(W0W1)∪(W1W0)中任何關(guān)鍵詞子集的陷門(mén)。S隨機(jī)選擇 β∈{0,1}，構(gòu)造關(guān)鍵詞集合 Wβ的密文。對(duì)于每個(gè) wβ,i(1≤i≤m)，如果已經(jīng)被詢(xún)問(wèn)過(guò)，則S返回列表 L中相應(yīng)元組的 xi,j作為其散列值，否則隨機(jī)選擇 xβ,i∈Zp作為其散列值，并加入到列表 L中保存。S按照3.1節(jié)中的 Encrypt算法生成關(guān)鍵詞集合Wβ的密文Cβ，并發(fā)送給A。

4)詢(xún)問(wèn)階段 2。A繼續(xù)詢(xún)問(wèn)關(guān)鍵詞集合的陷門(mén)，只是不能詢(xún)問(wèn)(W0W1)∪(W1W0)中任何關(guān)鍵詞子集的陷門(mén)。假設(shè)其中一個(gè)關(guān)鍵詞集合為其中，t≤m。S隨機(jī)選取計(jì)算tok1=Ks，對(duì)于每個(gè)attj∈Atts，計(jì)算對(duì)于每個(gè)j∈{1,…,t}，隨機(jī)選擇 hj∈Zp；對(duì)于每個(gè) i∈{0,1,…,m}，計(jì)算S利用挑戰(zhàn)元組對(duì)于每個(gè) i∈{0,1,…,m?1}，計(jì)算并計(jì)算S將陷門(mén)發(fā)送給A，A調(diào)用搜索算法Search對(duì)密文Cβ進(jìn)行搜索，看關(guān)鍵詞集合Wq′是否是Wβ的子集。5)猜測(cè)。最終，A輸出一個(gè)猜測(cè)β’∈{0,1}。如果 β’=β，S 猜測(cè)否則S猜測(cè)y=x。

在挑戰(zhàn)階段，由于A不知道主密鑰，并且主密鑰的選擇與所有的關(guān)鍵詞無(wú)關(guān)，因此，從A的角度看來(lái)，密文中的組件Fi是均勻分布的，即構(gòu)造的m次多項(xiàng)式 f(x)的系數(shù)是均勻分布的。在離散對(duì)數(shù)難題假設(shè)下，A無(wú)法從已經(jīng)詢(xún)問(wèn)過(guò)的密文和陷門(mén)中計(jì)算出主密鑰或者f(x)的系數(shù)。因此，在挑戰(zhàn)階段，A無(wú)法分辨出β是0還是1。

4.2 性能分析

本節(jié)將構(gòu)造的方案與現(xiàn)有的支持連接關(guān)鍵詞子集搜索的加密方案在通信開(kāi)銷(xiāo)、存儲(chǔ)開(kāi)銷(xiāo)和計(jì)算開(kāi)銷(xiāo)方面做詳細(xì)比較。其中，性能指標(biāo)包括每個(gè)密文的長(zhǎng)度和加密計(jì)算量，每個(gè)陷門(mén)的長(zhǎng)度和計(jì)算量，以及DSP使用一個(gè)陷門(mén)針對(duì)一個(gè)密文進(jìn)行搜索時(shí)的計(jì)算量。

密文長(zhǎng)度關(guān)系到DO與DSP之間的通信開(kāi)銷(xiāo)以及DSP的存儲(chǔ)開(kāi)銷(xiāo)；陷門(mén)長(zhǎng)度關(guān)系到DReq與DSP之間的通信開(kāi)銷(xiāo)。加密計(jì)算量關(guān)系到DO的計(jì)算開(kāi)銷(xiāo)，陷門(mén)計(jì)算量關(guān)系到DReq的計(jì)算開(kāi)銷(xiāo)，搜索計(jì)算量關(guān)系到DSP的計(jì)算開(kāi)銷(xiāo)。

在云計(jì)算的數(shù)據(jù)外包環(huán)境中，DO和DReq所在終端的計(jì)算能力、通信能力和存儲(chǔ)能力可能受限。由于公開(kāi)參數(shù)和用戶(hù)私鑰等信息的存儲(chǔ)量并不大，因此，公開(kāi)參數(shù)長(zhǎng)度和用戶(hù)私鑰長(zhǎng)度對(duì)用戶(hù)終端的影響很小，可以忽略。但是，要求密文長(zhǎng)度、密文計(jì)算量、陷門(mén)長(zhǎng)度和陷門(mén)計(jì)算量盡可能小。由于所有的密文都存儲(chǔ)在DSP端，并由DSP進(jìn)行搜索計(jì)算，因此，密文長(zhǎng)度大時(shí)，導(dǎo)致DSP存儲(chǔ)開(kāi)銷(xiāo)大，DSP的存儲(chǔ)能力需要相應(yīng)提高；而搜索的計(jì)算量大時(shí)，則對(duì)于DSP固定的計(jì)算能力來(lái)說(shuō)，將帶來(lái)響應(yīng)時(shí)間長(zhǎng)的問(wèn)題。

算法建立、用戶(hù)私鑰生成是由UM預(yù)先實(shí)現(xiàn)的，它們同公開(kāi)參數(shù)長(zhǎng)度、用戶(hù)私鑰長(zhǎng)度一樣，與用戶(hù)體驗(yàn)無(wú)太大關(guān)系，這里就不做比較了。

記P和M分別為循環(huán)群中的指數(shù)運(yùn)算（橢圓曲線的點(diǎn)乘運(yùn)算）和乘法運(yùn)算（橢圓曲線的點(diǎn)加運(yùn)算），E為雙線性映射運(yùn)算，H為從群Zp到群G和GT（或從群G和GT到群Zp）的編碼運(yùn)算。|G|表示群G和GT中元素的長(zhǎng)度，|p|表示域Zp中元素的長(zhǎng)度。m為每個(gè)文檔的關(guān)鍵詞數(shù)量，t為搜索的關(guān)鍵詞的數(shù)量。v表示屬性個(gè)數(shù)，u表示具有訪問(wèn)權(quán)限的DReq個(gè)數(shù)，i表示系統(tǒng)中的用戶(hù)屬性總數(shù)。

連接搜索時(shí)，搜索條件是文檔的關(guān)鍵詞集合包含陷門(mén)的關(guān)鍵詞集合。當(dāng)搜索的關(guān)鍵詞的數(shù)量大于文檔的關(guān)鍵詞的數(shù)量時(shí)，必然沒(méi)有文檔滿(mǎn)足搜索條件。因此，搜索的關(guān)鍵詞數(shù)量和文檔的關(guān)鍵數(shù)量之間存在關(guān)系t≤m。

在訪問(wèn)樹(shù)中，葉子節(jié)點(diǎn)代表屬性，通過(guò)代表關(guān)系的內(nèi)部節(jié)點(diǎn)進(jìn)行組合，確定具有訪問(wèn)權(quán)限的DReq集合。這使訪問(wèn)樹(shù)可以通過(guò)規(guī)模很小、數(shù)量固定的屬性集來(lái)表示規(guī)模巨大、不斷增加的授權(quán)用戶(hù)集。訪問(wèn)樹(shù)中的用戶(hù)屬性個(gè)數(shù)與屬性總數(shù)之間有關(guān)系v≤i。i個(gè)用戶(hù)屬性可以定義2i種用戶(hù)，v個(gè)用戶(hù)屬性在通過(guò)and關(guān)系組合時(shí)，定義最少的允許訪問(wèn)用戶(hù)數(shù)量，這時(shí)u=2i?v，通過(guò)or關(guān)系組合時(shí)，定義最多的允許訪問(wèn)用戶(hù)數(shù)量，這時(shí)u=v2i?1。因此有2i?v≤u≤v2i?1，即在大多數(shù)情況下，u 遠(yuǎn)大于或者大于v，并且隨著u的增加，v并不增加。

采用對(duì)稱(chēng)密鑰加密關(guān)鍵詞時(shí)，雖然單次加密和搜索的效率較高，但在多用戶(hù)場(chǎng)景中，訪問(wèn)控制實(shí)現(xiàn)困難，當(dāng)更改用戶(hù)權(quán)限時(shí)，需要花費(fèi)大量的通信開(kāi)銷(xiāo)和計(jì)算開(kāi)銷(xiāo)來(lái)更新密文和分發(fā)密鑰，因此一般只適用于搜索自己存儲(chǔ)在服務(wù)器中的數(shù)據(jù)。所以，這里沒(méi)有把這類(lèi)方案[6,15]列入性能對(duì)比，如表1所示。

表1 多用戶(hù)環(huán)境下連接關(guān)鍵詞搜索方案的性能對(duì)比

從表1可以看出，在密文長(zhǎng)度和運(yùn)算量上，其他方案（除了HL-2的密文運(yùn)算量）是基于授權(quán)用戶(hù)數(shù)量u和文檔關(guān)鍵詞數(shù)量m的二次函數(shù)，而本文方案是基于屬性數(shù)量v和文檔關(guān)鍵詞數(shù)量m的一次函數(shù)，由于訪問(wèn)樹(shù)中的屬性數(shù)量與授權(quán)訪問(wèn)的用戶(hù)數(shù)量沒(méi)有直接關(guān)系，因此，隨著用戶(hù)數(shù)量的增長(zhǎng)，本文方案并不增長(zhǎng)，而其他方案則會(huì)線性增長(zhǎng)；隨著用戶(hù)數(shù)量和關(guān)鍵詞數(shù)量的增長(zhǎng)，本文方案的增長(zhǎng)率遠(yuǎn)小于其他方案。在陷門(mén)長(zhǎng)度上，3種方案為固定值，BW方案是搜索關(guān)鍵詞數(shù)量t的一次函數(shù)，ZZ方案是文檔關(guān)鍵詞數(shù)量m的一次函數(shù)；本文方案是屬性數(shù)量v和文檔關(guān)鍵詞數(shù)量m的一次函數(shù)，隨著屬性數(shù)量和關(guān)鍵詞數(shù)量的增加，將大于其他方案。在陷門(mén)運(yùn)算量上，前4種方案是搜索關(guān)鍵詞數(shù)量t的一次函數(shù)，ZZ方案和本文方案是文檔關(guān)鍵詞數(shù)量m的一次函數(shù)，但本文方案對(duì)每個(gè)關(guān)鍵詞處理的操作較少，體現(xiàn)在函數(shù)計(jì)算上，即系數(shù)較小，因此同其他方案相比各有優(yōu)勢(shì)。在搜索運(yùn)算量上，前4種方案是搜索關(guān)鍵詞數(shù)量t的一次函數(shù)，ZZ方案是文檔關(guān)鍵詞數(shù)量m的一次函數(shù)，本文方案是屬性數(shù)量v和文檔關(guān)鍵詞數(shù)量m的一次函數(shù)，在v較大時(shí)，具有一定的劣勢(shì)。

相比于其他方案，本文方案在陷門(mén)計(jì)算量上處于中等水平。搜索運(yùn)算量和陷門(mén)長(zhǎng)度與屬性數(shù)量和關(guān)鍵詞數(shù)量成線性關(guān)系，但屬性數(shù)量相比于其可以定義的用戶(hù)數(shù)量，可以忽略，一般情況下有限，為個(gè)位數(shù)；并且每個(gè)文檔的關(guān)鍵詞數(shù)量也不可能太多，因此，陷門(mén)長(zhǎng)度和搜索運(yùn)算量的開(kāi)銷(xiāo)增加有限。而在云存儲(chǔ)環(huán)境中，如果使用其他方案，DO需要基于所有授權(quán)用戶(hù)的公鑰，將關(guān)鍵詞集合分別加密成相應(yīng)的密文版本，造成密文長(zhǎng)度和加密運(yùn)算量線性增長(zhǎng)，由于用戶(hù)數(shù)量通常較大，所以DO的加密負(fù)擔(dān)、通信負(fù)擔(dān)、Serv的存儲(chǔ)負(fù)擔(dān)以及文檔內(nèi)容修改所帶來(lái)的重新加密負(fù)擔(dān)，是不可接受的。因此，本文方案能夠顯著減少多用戶(hù)環(huán)境下的密文長(zhǎng)度和加密運(yùn)算量，更適合于大用戶(hù)量的云存儲(chǔ)環(huán)境。其原因是在搜索機(jī)制中融入了基于屬性的訪問(wèn)控制，使一個(gè)公鑰對(duì)應(yīng)多個(gè)不同的私鑰，DO通過(guò)相同公鑰加密形成的密文，能夠授權(quán)給不同的 DReq進(jìn)行搜索，避免了多次加密和多個(gè)密文版本。但本文方案的代價(jià)是除陷門(mén)運(yùn)算量外，各項(xiàng)開(kāi)銷(xiāo)有所增加，主要用于屬性相關(guān)的表示和運(yùn)算，陷門(mén)長(zhǎng)度和每次搜索的運(yùn)算量比大多數(shù)方案稍大。但是在方案實(shí)現(xiàn)時(shí)，DReq可以提前將陷門(mén)中的屬性部分發(fā)送給Serv，由Serv在空閑時(shí)段計(jì)算出權(quán)限分量在DReq有搜索需求并發(fā)送陷門(mén)的關(guān)鍵詞部分后，Serv再將分量、陷門(mén)的關(guān)鍵詞部分，連同密文輸入到搜索算法中，驗(yàn)證是否滿(mǎn)足訪問(wèn)控制策略和搜索策略，從而降低搜索進(jìn)行時(shí)的運(yùn)算量，減小搜索響應(yīng)時(shí)間。

此外，本文方案支持非域形式的關(guān)鍵詞連接搜索，在多文檔應(yīng)用場(chǎng)景中，當(dāng)文檔不斷增加、文檔類(lèi)型不斷豐富時(shí)，無(wú)需根據(jù)文檔語(yǔ)義調(diào)整關(guān)鍵詞域，重新加密關(guān)鍵詞，即能夠支持非結(jié)構(gòu)化數(shù)據(jù)的密文檢索，因而具有更廣闊的應(yīng)用前景。

5 結(jié)束語(yǔ)

本文基于屬性加密和多項(xiàng)式方程提出了一種連接關(guān)鍵詞可搜索加密方案。方案實(shí)現(xiàn)了“一對(duì)多”通信模式，支持多用戶(hù)環(huán)境下的細(xì)粒度訪問(wèn)控制，顯著減小了大用戶(hù)量時(shí)的密文長(zhǎng)度和加密計(jì)算量；實(shí)現(xiàn)了關(guān)鍵詞的任意連接搜索模式，支持針對(duì)非結(jié)構(gòu)化數(shù)據(jù)的連接關(guān)鍵詞檢索。只是在陷門(mén)長(zhǎng)度和搜索運(yùn)算量上，增加了相應(yīng)的開(kāi)銷(xiāo)。下一步將重點(diǎn)研究通過(guò)融入代理加密機(jī)制，使首次搜索時(shí)權(quán)限分量的計(jì)算結(jié)果，能夠用于以后的搜索請(qǐng)求，避免每次搜索時(shí)重復(fù)發(fā)送屬性部分和計(jì)算權(quán)限分量，從而減小陷門(mén)的計(jì)算量和長(zhǎng)度，達(dá)到降低數(shù)據(jù)請(qǐng)求者的計(jì)算和通信開(kāi)銷(xiāo)，以及減少搜索時(shí)運(yùn)算量的目的。

[1]項(xiàng)菲,劉川意,方濱興,等. 云計(jì)算環(huán)境下密文搜索算法的研究[J].通信學(xué)報(bào),2013,34(7): 143-153.XIANG F,LIU C Y,FANG B X,et al. Research on ciphertext search for the cloud environment[J]. Journal on Communications,2013,34(7):143-153.

[2]沈志榮,薛巍,舒繼武. 可搜索加密機(jī)制研究與進(jìn)展[J]. 軟件學(xué)報(bào),2014,25(4): 880-895.SHEN Z R,XUE W,SHU J W. Survey on the research and development of searchable encryption schemes[J]. Journal of Software,2014,25(4): 880-895.

[3]SONG D,WAGNER D,PERRIG A. Practical techniques for searches on encrypted data[C]//The IEEE Symposium on Security and Privacy(Samp;P’00). c2000:44-55.

[4]BONEH D,CRESCENZOM G D,OSTROVSKY R,et al. Public key encryption with keywordsearch[C]//The International Conference on the Theory and Applications of Cryptographic Techniques(EUROCRYPT2004). Interlaken,Switzerland,c2004:506-522.

[5]LEE C C,HSU S T,H M S. A study of conjunctive keyword searchable schemes[J]. International Journal of Network Security,2013,15(5): 321-330.

[6]GOLLE P,STADDON J,WATERS B. Secure conjunctive keyword search over encrypted data[C]//Applied Cryptography and Network Security Conference (ACNS 2004). Yellow Mountain,China,c2004:31-45.

[7]PARK D J,KIM K,LEE P J. Public key encryption with conjunctive-field keyword search[C]//The 5th Information Security Applications International Workshop (WISA 2004).Jeju Island,Korea,c2004:73-86.

[8]HWANG Y H,LEE P J. Public key encryption with conjunctive keyword search and its extension to a multi-user system[C]//The first International Conference of Pairing-BasedCryptography (Pairing 2007).Tokyo,Japan,c2007:2-22.

[9]BONEH D,WATERS B. Conjunctive,subset,and range queries on encrypted data[C]//The 4th Theory of Cryptography conference (TCC 2007). Amsterdam,The Netherlands,c2007: 535-554.

[10]KATZ J,SAHAI A,WATERS B. Predicate encryption supporting disjunctions,polynomial equations,and inner products[C]//The 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2008). Istanbul,Turkey,c2008:146-162.

[11]CHEN Y C,HORNG G. Timestamped conjunctive keyword searchable public key encryption[C]//Fourth International Conference on Innovation Computing Information and Control (ICICIC). Kaohsiung,c2009:729-932.

[12]ZHANG B,ZHANG F G. An efficient public key encryption with conjunctive-subset keywords search[J]. Journal of Network and Computer Applications,2011,34(1):262-267.

[13]YANG Y,MA G D. Proxy re-encryption conjunctive keyword search against keyword guessing attack[C]//The IEEE International Conference on Computers,Communications and IT Applications. Hongkong,China,c2013:125-130.

[14]CHEN Z H,WU C Y,WANG D S,et al. Conjunctive keywords searchable encryption with efficient pairing,constant ciphertext and short trapdoor[C]//Intelligence and Security InformaticsPacific Asia Workshop (PAISI 2012). Kuala Lumpur,Malaysia,c2012:176-189.

[15]王尚平,劉利軍,劉亞玲. 一個(gè)高效的基于連接關(guān)鍵詞的可搜索加密方案[J]. 電子與信息學(xué)報(bào),2013,35(9): 2266-2271.WANG S P,LIU L J,LIU Y L. An efficient conjunctive keyword searchable encryption scheme[J]. Journal of Electronics and Information Technology,2013,35(9): 2266-2271.

[16]KERSCHBAUM F. Secure conjunctive keyword searches for unstructured text[C]//The 5th International Conference on Network and System Security (NSS). c2011: 285-289.

[17]李雙,徐茂智. 基于屬性的可搜索加密方案[J]. 計(jì)算機(jī)學(xué)報(bào),2014,37(5): 1017-1024.LI S,XU M Z. Attribute-based public encryption with keyword search[J]. Chinese Journal of Computers,2014,37(5):1017-1024.

[18]ZHENG Q,XU S H,ATENIESE G. VABKS: verifiable attribute-based keyword search over outsourced encrypted data[C]//Proceeding-IEEE INFOCOM. c2014:522-530.

[19]GOYAL V,PANDEY O,SAHAI A,et al. Attribute-based encryption for fine-grained access control of encrypted data[C]//The 13th ACM Conference on Computer and Communications Security. Alexandria,VA,USA,c2006: 89-98.

Attribute-based encryption supporting arbitrary conjunctive key word search

SONG Yan1,2,HAN Zhen1,CHEN Dong1,2,ZHAO Jin-hua2

(1. School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China;2. Technology on Information Assurance Key Laboratory,Beijing 100072,China)

A new searchable encryption scheme was proposed in prime order bilinear groups based on the attribute-based encryption and polynomial equation. The scheme,in which each conjunctive-keyword ciphertext can be searched by a number of users,may significantly reduce the overhead of network and sending nodes’ computation in the application of fine-grained access control.Meanwhile,the scheme facilitates the flexibility of conjunctive search by supporting arbitrary conjunctive search of the keywords. At last,the performance was analyzed and compared with some recent conjunctive search schemes.

searchable encryption,attribute-based encryption,conjunctive keyword,polynomial equation

s:The National Natural Science Foundation of China (No.60973112),Discipline Construction and Graduate Education Foundation of Beijing Municipal Commission of Education (No.BMKY2011B06)

TP309.7

A

2015-10-23；

2016-07-29

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.60973112）；北京市教育委員會(huì)學(xué)科建設(shè)與研究生培養(yǎng)基金資助項(xiàng)目（No.BMKY2011B06）

10.11959/j.issn.1000-436x.2016158

宋衍（1982-），男，湖北老河口人，北京交通大學(xué)博士生，主要研究方向?yàn)槊軕B(tài)計(jì)算、安全數(shù)據(jù)庫(kù)等。

韓臻（1962-），男，浙江寧波人，博士，北京交通大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾畔踩w系結(jié)構(gòu)、可信計(jì)算等。

陳棟（1982-），男，山西運(yùn)城人，北京交通大學(xué)博士生，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、軟件工程等。

趙進(jìn)華（1981-），男，山東菏澤人，信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室副研究員，主要研究方向?yàn)槊艽a理論與應(yīng)用。