裴樹(shù)軍，易 鑫，陳彥橦，苗 輝

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱150080

+通訊作者E-mail:yixinbelinda@163.com

1 引言

隨著云計(jì)算技術(shù)的迅猛發(fā)展，在云端進(jìn)行存儲(chǔ)和共享數(shù)據(jù)的用戶越來(lái)越多，這樣不僅可以節(jié)約本地資源，還可以節(jié)省系統(tǒng)維護(hù)的開(kāi)銷。但是，云計(jì)算給個(gè)人及企業(yè)提供便利的同時(shí)，也引入了一定的安全問(wèn)題。為了保護(hù)數(shù)據(jù)的安全，數(shù)據(jù)擁有者通常將數(shù)據(jù)文件加密后再上傳至云端，但這樣造成了文件搜索困難。因此，可搜索加密技術(shù)（searchable encryption，SE）[1]的提出，有效解決了這一問(wèn)題。

可搜索加密技術(shù)在提出之后，即得到了廣泛的研究和迅速的發(fā)展[2]。在最早的可搜索加密技術(shù)中，用戶只能搜索自己加密存儲(chǔ)在云端的密文，實(shí)用性不強(qiáng)，因此Boneh等人[3]于2004年結(jié)合公鑰加密技術(shù)構(gòu)造了一個(gè)可搜索加密方案，解決了其他用戶無(wú)法檢索密文數(shù)據(jù)的問(wèn)題。

屬性基加密（attribute-based encryption，ABE）是由Sahai 和Waters[4]提出的一種可以實(shí)現(xiàn)訪問(wèn)控制的加密技術(shù)。該技術(shù)通過(guò)制定訪問(wèn)策略來(lái)限制用戶對(duì)文件的訪問(wèn)權(quán)限。其中，密文策略屬性基加密（ciphertextpolicy attribute-based encryption，CP-ABE）[5]將訪問(wèn)策略嵌入到密文中，更適合在云環(huán)境中應(yīng)用。為此，學(xué)者們對(duì)基于ABE加密技術(shù)的可搜索加密方案展開(kāi)了研究[6-8]。Hu 等人[9]提出了一種基于動(dòng)態(tài)性的屬性基可搜索加密方案，實(shí)現(xiàn)了數(shù)據(jù)屬主對(duì)訪問(wèn)策略的動(dòng)態(tài)更新，但該方案僅支持單關(guān)鍵字搜索，搜索效率低。而宋衍等人[10]提出的一種支持多關(guān)字搜索的屬性基加密方案，相比于單個(gè)關(guān)鍵字的搜索，該方案能夠更準(zhǔn)確地定位到用戶所需要的文件。當(dāng)用戶的屬性集發(fā)生改變時(shí)，該用戶的搜索權(quán)限也會(huì)發(fā)生改變，此時(shí)需要撤銷其原有的訪問(wèn)權(quán)限。為此，伍祈應(yīng)等人[11]提出了一基于屬性基加密支持撤銷的可搜索加密方案，使用戶搜索權(quán)限的管理變得更加靈活。除此之外，一些研究人員[12]還將這項(xiàng)技術(shù)改進(jìn)后應(yīng)用到了移動(dòng)端。然而，基于ABE 的可搜索加密方案仍存在一定的局限性，例如當(dāng)用戶惡意泄露自己的私鑰時(shí)，目前的可搜索加密方案還不能確定泄密者身份，造成了潛在的安全隱患。

為此，本文提出了一種可問(wèn)責(zé)的多關(guān)鍵字可搜索加密方案，該方案有以下4點(diǎn)優(yōu)勢(shì)：

（1）可問(wèn)責(zé)。當(dāng)不法用戶惡意泄露私鑰時(shí)，可以通過(guò)運(yùn)行追蹤算法對(duì)泄密者進(jìn)行身份的確認(rèn)，并撤銷該用戶，保障了系統(tǒng)的安全。

（2）在線離線加密。受陳冬冬等人所提方案[13]的啟發(fā)，將加密階段拆分為離線加密和在線加密，以提升系統(tǒng)線上資源的利用率。

（3）多關(guān)鍵字搜索。用戶輸入關(guān)鍵字集來(lái)檢索目標(biāo)文件，防止查詢時(shí)返回過(guò)多不相關(guān)的文件，增強(qiáng)用戶搜索體驗(yàn)。

（4）可撤銷。當(dāng)用戶的屬性集發(fā)生改變時(shí)，或者被判定為泄密者時(shí)，可以撤銷其搜索權(quán)限。

2 相關(guān)技術(shù)

2.1 雙線性對(duì)

定義1（雙線性映射）令G1、GT是兩個(gè)階為素?cái)?shù)p的乘法循環(huán)群，G1的生成元為g，存在雙線性映射e:G1×G1→GT滿足：

（1）雙 線 性：?x,y∈Zp，?a,b∈G1，有e(ax,by)=e(a,b)xy。

（2）可計(jì)算性：?a,b∈G1，存在有效的算法計(jì)算e(a,b)。

（3）非退化性：?g∈G1，使e(g,g)≠1。

2.2 策略樹(shù)

本文用策略樹(shù)來(lái)描述訪問(wèn)控制策略。一棵策略樹(shù)中包括葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)，每一個(gè)非葉子節(jié)點(diǎn)f代表一個(gè)門(mén)限，其值為kf，子節(jié)點(diǎn)個(gè)數(shù)為nf。對(duì)子節(jié)點(diǎn)從左到右依次編號(hào)1,2,…,nf，其中1 ≤kf≤nf，當(dāng)節(jié)點(diǎn)f是或門(mén)時(shí)，kf=1，當(dāng)節(jié)點(diǎn)f是與門(mén)時(shí)，kf=nf。p(f)是節(jié)點(diǎn)f的父節(jié)點(diǎn)，index(f)是節(jié)點(diǎn)f的編號(hào)。每個(gè)葉子節(jié)點(diǎn)l都與屬性值相關(guān)，lvs(T)表示策略樹(shù)T的所有葉子節(jié)點(diǎn)的集合，Tf表示以節(jié)點(diǎn)f為根節(jié)點(diǎn)的策略樹(shù)T的子樹(shù)，attr(l)表示葉子節(jié)點(diǎn)l的屬性值。

如果策略樹(shù)T的葉子節(jié)點(diǎn)l的屬性值attr(l)∈S（S為用戶的屬性集），記Tl(S)=1，對(duì)于策略樹(shù)的非葉子節(jié)點(diǎn)f，如果存在|I|個(gè)子節(jié)點(diǎn)f′滿足Tf′(S)=1，且|I|≥kf，記Tf(S)=1。對(duì)于策略樹(shù)T的根節(jié)點(diǎn)r，如果Tr(S)=1，則說(shuō)明用戶的屬性集S滿足訪問(wèn)策略T。

為每個(gè)節(jié)點(diǎn)構(gòu)造多項(xiàng)式，采用自頂向下的遞歸算法。對(duì)根節(jié)點(diǎn)r，令qr(0)=s，并在其他kr-1 點(diǎn)處隨機(jī)選取，構(gòu)造出kr-1 次的多項(xiàng)式qr。對(duì)于非根節(jié)點(diǎn)f，令qf(0)=qpf(index(f))，其他kf-1 點(diǎn)處隨機(jī)選取，構(gòu)造出kf-1 次的多項(xiàng)式。由上述自頂向下的遞歸算法最終得到葉子節(jié)點(diǎn)l的多項(xiàng)式ql。

恢復(fù)秘密值s，采用自底向上的遞歸算法。如果屬性集{attr(h1),attr(h2),…,attr(hm)}滿足訪問(wèn)策略Tf，對(duì)于葉子節(jié)點(diǎn)l，計(jì)算Dl=e(g,g)qhj(0)；對(duì)于非葉子節(jié)點(diǎn)f，存在子節(jié)點(diǎn)集合的子集I使|I|=kf，j∈I，則Df=，其中，最后恢復(fù)Dr=e(g,g)s。

2.3 q'-SDH 假設(shè)

定義2（q′-SDH假設(shè)（strong Diffie-Hellman assumption））[14]G是階為素?cái)?shù)p，生成元為g的循環(huán)群。G中的q′-SDN 難題定義為：隨機(jī)選取x∈Zp，給定(g,gx,gx2,…,gxq′)，計(jì)算，其中c∈Zp。ε為一個(gè)算法A解決G中的q′-SDH 難題優(yōu)勢(shì)，當(dāng)，即一個(gè)多項(xiàng)式時(shí)間算法能以不可忽略的優(yōu)勢(shì)ε解決群中的q′-SDH 難題，則q′-SDH 假設(shè)成立。

3 系統(tǒng)模型與安全模型

3.1 系統(tǒng)模型

如圖1 所示，本文方案由5 個(gè)參與方組成，其中包括證書(shū)中心（certificate authority，CA）、審計(jì)中心（audit authority，AA）、數(shù)據(jù)屬主（data owner，DO）、用戶（users）和云服務(wù)器（cloud server，CS）。

Fig.1 System model圖1 系統(tǒng)模型

證書(shū)中心負(fù)責(zé)對(duì)系統(tǒng)進(jìn)行初始化建立，為用戶頒發(fā)私鑰和生成、更新版本信息；數(shù)據(jù)屬主負(fù)責(zé)加密待上傳文件，將生成的索引值和中間密文發(fā)送給云服務(wù)器；用戶根據(jù)搜索的關(guān)鍵字集生成搜索憑證和陷門(mén)值，并同關(guān)鍵字位置集一起發(fā)送給云服務(wù)器；云服務(wù)器負(fù)責(zé)驗(yàn)證用戶的屬性是否滿足訪問(wèn)策略，然后向?qū)徲?jì)中心請(qǐng)求搜索參數(shù)，匹配索引值和陷門(mén)值，接著向?qū)徲?jì)中心發(fā)送搜索憑證和陷門(mén)值，最后將得到的密文發(fā)送給用戶；審計(jì)中心負(fù)責(zé)通過(guò)與云服務(wù)器交互來(lái)審查用戶是否有權(quán)限訪問(wèn)密文，審查通過(guò)后，向用戶發(fā)送密文參數(shù)，同時(shí)也負(fù)責(zé)判定用戶所使用的私鑰是否存在被泄露、出售嫌疑，并對(duì)私鑰泄密者進(jìn)行追蹤問(wèn)責(zé)。

3.2 算法定義

本文方案具體包括以下10個(gè)算法：

Setup(λ,U)→(MSK,PK)：初始化算法由證書(shū)中心執(zhí)行。輸入安全參數(shù)λ和屬性域U，由完全可信的證書(shū)中心CA輸出系統(tǒng)公鑰PK和主密鑰MSK，并初始化一個(gè)問(wèn)責(zé)列表TA，其中主密鑰MSK由CA私有。

KeyGen(PK,MSK,id,S)→(SKid,V)：密鑰生成算法由證書(shū)中心運(yùn)行。輸入系統(tǒng)公鑰PK、主密鑰MSK、用戶的身份標(biāo)識(shí)id和該用戶的屬性集合S∈U，輸出對(duì)應(yīng)于(id,S)的用戶私鑰SKid和版本信息V=(id,vid)，并將該用戶的id插入到問(wèn)責(zé)列表TA中。

Offline.Encrypt(PK,M)→(CT,k)：離線加密算法（預(yù)加密算法）由數(shù)據(jù)屬主執(zhí)行。輸入系統(tǒng)公鑰PK和待加密文件M，用傳統(tǒng)的對(duì)稱加密算法對(duì)文件M進(jìn)行離線預(yù)加密，輸出預(yù)加密密鑰k和文件密文CT。

Online.Encrypt(PK,k,W,T)→(CTA,I)：在線加密算法由數(shù)據(jù)屬主在對(duì)文件進(jìn)行預(yù)加密之后運(yùn)行。輸入系統(tǒng)公鑰PK、文件預(yù)加密密鑰k、關(guān)鍵字集合W和數(shù)據(jù)屬主定義的訪問(wèn)結(jié)構(gòu)T。數(shù)據(jù)屬主利用CPABE 加密技術(shù)對(duì)預(yù)加密的密鑰k進(jìn)行在線加密，并建立索引I，生成中間密文CTK，最后將文件密文CT、索引I和中間密文CTK上傳至云服務(wù)器CS。

Trapdoor(PK,SKid,W′)→(TK,Z,TRW′)：陷門(mén)生成算法由用戶執(zhí)行。輸入系統(tǒng)公鑰PK、用戶私鑰SKid和搜索關(guān)鍵字集W′，生成陷門(mén)值TRW′和搜索憑證TK。同時(shí)，用戶根據(jù)搜索關(guān)鍵字集合W′=(w1′,w2′,…,wl′)中的每一個(gè)關(guān)鍵字處于加密算法中所給定的關(guān)鍵字集合W={w1,w2,…,wm}的位置生成相對(duì)位置集Z，最后用戶將陷門(mén)值TRW′、搜索憑證TK和位置集Z發(fā)送給云服務(wù)器。

Search(PK,TRW′,I)→(CT′)：搜索算法由云服務(wù)器執(zhí)行。當(dāng)用戶滿足訪問(wèn)控制策略時(shí)，云服務(wù)器向?qū)徲?jì)中心發(fā)送搜索憑證TK和中間密文CTK，審計(jì)中心根據(jù)遞歸算法進(jìn)行自底向上的計(jì)算，得到Dr，并返回給云服務(wù)器；云服務(wù)器對(duì)陷門(mén)值TRW′和索引值I進(jìn)行匹配，得到返回密文集CT′，并返回給用戶。同時(shí)，將返回密文集CT′對(duì)應(yīng)的搜索憑證TK和中間密文CTK發(fā)送給審計(jì)中心。

Audit(SKid,TK,CTK)→{0,1}：審計(jì)算法由審計(jì)中心運(yùn)行。輸入用戶私鑰SKid、搜索憑證TK和中間密文CTK，審計(jì)中心驗(yàn)證用戶是否有權(quán)訪問(wèn)返回密文集CT′，同時(shí)判定該用戶使用的私鑰是否有被泄露、販賣或非法盜用的嫌疑。若通過(guò)驗(yàn)證，審計(jì)中心將該返回密文集所對(duì)應(yīng)的參數(shù)ω、ω1和Dr發(fā)送給用戶；否則，該用戶將不能訪問(wèn)此文件。

Decrypt(SKid,CT′,ω,ω1,Dr)→(k)：解密算法由用戶執(zhí)行。輸入用戶私鑰SKid、返回密文CT′和密文參數(shù)，用戶解出預(yù)加密密鑰k，再用k解密文件，即完成了對(duì)文檔的解密。

Revoke(V)：用戶撤銷算法由證書(shū)中心和審計(jì)中心合作運(yùn)行。當(dāng)用戶的數(shù)據(jù)集合發(fā)生改變時(shí)，證書(shū)中心更新用戶的版本信息為V′=(id,vid′)，并發(fā)送給審計(jì)中心，用戶對(duì)應(yīng)于舊版本信息V=(id,vid)的私鑰SKid將不能通過(guò)審計(jì)，因此實(shí)現(xiàn)了用戶的撤銷。

Trace(PK,TA,SKid)→(id)：追蹤算法由審計(jì)中心執(zhí)行。輸入系統(tǒng)公鑰PK，問(wèn)責(zé)列表TA和用戶私鑰SKid，審計(jì)中心驗(yàn)證該私鑰是否合理，如果合理，輸出SKid對(duì)應(yīng)的身份id，當(dāng)有必要撤銷該用戶時(shí)，審計(jì)中心直接將該用戶的版本信息設(shè)置為V*=(id,0)。

3.3 可問(wèn)責(zé)性安全模型

定義3如果敵手A在任何多項(xiàng)式時(shí)間在下述游戲中獲勝的優(yōu)勢(shì)是可以忽略的，則稱本文方案是可問(wèn)責(zé)的。

（1）初始化：挑戰(zhàn)者C執(zhí)行初始化算法，將生成的公鑰PK發(fā)送給敵手A，主密鑰MSK私有。

（2）詢問(wèn)階段：敵手A向挑戰(zhàn)者C詢問(wèn)屬性集(id1,S1),(id2,S2),…,(idn,Sn) 所對(duì)應(yīng)的私鑰，對(duì)于一切i∈[n]，挑戰(zhàn)者C執(zhí)行密鑰生成算法，并將生成的私鑰SKidi返還給敵手A。

（3）私鑰偽造：敵手A輸出一個(gè)私鑰SK*。

敵手A在該游戲中獲勝的優(yōu)勢(shì)為Pr[Trace(PK,TA,SK*)?{id1,id2,…,idn}]。

4 方案構(gòu)造

本文提出了一種可問(wèn)責(zé)的多關(guān)鍵字可搜索加密方案，具體算法構(gòu)造如下。

Setup(λ,U)→(MSK,PK)：初始化算法。輸入安全參數(shù)λ和屬性域U，CA 首先選取一個(gè)以素?cái)?shù)p為階的雙線性群G，g為G的生成元，定義一個(gè)G群上的雙線性對(duì)e:G×G→GT，然后定義兩個(gè)哈希函數(shù)H1:{0,1}*→G和H2:{0,1}*→Zp，隨機(jī)選取α,β,a,b,c∈Zp，最后 輸 出 系 統(tǒng) 公 鑰PK=(G,GT,e,p,g,gα,e(g,g)β,ga,gb,gc,H1,H2)和主密鑰MSK=(α,β,a,b,c)，同時(shí)初始化一個(gè)問(wèn)責(zé)列表TA=?。

KeyGen(PK,MSK,id,S)→(SKid,V)：密鑰生成算法。輸入系統(tǒng)公鑰PK、主密鑰MSK、用戶的身份標(biāo)識(shí)id和該用戶的屬性集合S∈U。首先CA為用戶隨機(jī)選擇版本號(hào)vid∈Zp，生成版本信息V=(id,vid)，然后為用戶的屬性集S中的元素a1,a2,…,aj∈S隨機(jī)選取k1,k2,…,kj∈Zp，接著隨機(jī)選取r∈Zp和θ∈Zp{-α}（如果θ在問(wèn)責(zé)列表TA中已經(jīng)存在，則重新隨機(jī)選取θ），計(jì)算，，，最后將輸出的私鑰發(fā)送給用戶，將版本信息V發(fā)送至審計(jì)中心，將數(shù)組(θ,id)插入到問(wèn)責(zé)列表TA中。

Offline.Encrypt(PK,M)→(CT,k)：離線加密算法（預(yù)加密算法）。輸入系統(tǒng)公鑰PK和待加密文件M，數(shù)據(jù)屬主用傳統(tǒng)的對(duì)稱加密算法Encrypt()預(yù)加密文件M，輸出預(yù)加密密鑰k和文件密文CT=(Encrypt(M))。

Online.Encrypt(PK,k,W,T)→(CTK,I)：在線加密算法。輸入系統(tǒng)公鑰PK、文件預(yù)加密密鑰k、關(guān)鍵字集合W和數(shù)據(jù)屬主定義的訪問(wèn)策略T。數(shù)據(jù)屬主隨機(jī)選取t1,t2∈Zp，ST為策略樹(shù)T的所有葉子節(jié)點(diǎn)的屬性集合，attr(l)∈ST是每個(gè)葉子節(jié)點(diǎn)的屬性值，策略樹(shù)T自頂向下地生成多項(xiàng)式，步驟如下：

步驟1設(shè)根節(jié)點(diǎn)多項(xiàng)式為qr(0)=t2，節(jié)點(diǎn)r門(mén)限值為kr，隨機(jī)選擇其他kr-1 個(gè)不同節(jié)點(diǎn)，則可以得到根節(jié)點(diǎn)多項(xiàng)式qr(x)。

步驟2對(duì)于非根節(jié)點(diǎn)f，設(shè)qf(0)=qp(f)(index(f))，節(jié)點(diǎn)f門(mén)限值為kf，隨機(jī)選擇其他kf-1 個(gè)不同節(jié)點(diǎn)，則可以得到非根節(jié)點(diǎn)多項(xiàng)式qf(x)。

步驟3按上述遞歸算法最后可以得到葉子節(jié)點(diǎn)l的多項(xiàng)式ql(x)。

給定關(guān)鍵字集W={w1,w2,…,wm}，數(shù)據(jù)屬主從每個(gè)文件中提取關(guān)鍵字集，并且建立索引，計(jì)算，如果文件含有關(guān)鍵字wi，則令，否則令σi=1。

最后數(shù)據(jù)屬主將文件密文CT，索引I={σi(1 ≤i≤m),μ0,μ2,μ3}和中間密文CTK={ω0,ω1,ω2,μ0,μ1,μ2{(δl,ηl|attr(l)∈ST)}}上傳至云服務(wù)器。

Trapdoor(PK,SKid,W′)→(TK,Z,TRW′)：陷門(mén)生成算法。輸入系統(tǒng)公鑰PK、用戶私鑰SKid和搜索關(guān)鍵字集W′。用戶根據(jù)搜索關(guān)鍵字集合中的每一個(gè)關(guān)鍵字處于加密算法中所給定的關(guān)鍵字集合W={w1,w2,…,wm}的位置生成相對(duì)位置集Z，并隨 機(jī) 選 擇s∈Zp，計(jì) 算，r4=，同 時(shí) 對(duì) 每 個(gè) 屬 性 值aj∈S計(jì) 算，，最后用戶將搜索憑證陷門(mén)值、搜索憑證和位置集Z發(fā)送給云服務(wù)器。

Search(PK,TRW′,I)→(CT′)：搜索算法。輸入系統(tǒng)公鑰PK、陷門(mén)值TRW′和索引I，搜索過(guò)程如下。

步驟1云服務(wù)器驗(yàn)證用戶是否滿足訪問(wèn)策略，若通過(guò)驗(yàn)證，云服務(wù)器將中間密文CTK和搜索憑證TK發(fā)送給審計(jì)中心，請(qǐng)求Dr，否則搜索失敗。

步驟2審計(jì)中心自底向上地計(jì)算Dr。首先，驗(yàn)證每一個(gè)葉子節(jié)點(diǎn)l的屬性值attr(l)是否屬于用戶的屬性集S，若attr(l)∈S，計(jì)算，否則Dl=⊥。然后計(jì)算非葉子節(jié)點(diǎn)f的所有子節(jié)點(diǎn)f′的Df′，若節(jié)點(diǎn)f存在kf個(gè)子節(jié)點(diǎn)f′，記該子節(jié)點(diǎn)的集合為?f，若不存在，記Df′=⊥。接著計(jì)算Df=，其 中i=index(f′)，。用上述的遞歸算法最后計(jì)算出根節(jié)點(diǎn)的Dr=e(g,g)rsqr(0)=e(g,g)rst2，并發(fā)送給云服務(wù)器。

步驟3云服務(wù)器陷門(mén)值TRW′和索引值I驗(yàn)證式（1）是否成立，其中τ→i為搜索關(guān)鍵字下標(biāo)在給定的關(guān)鍵字集中的映射。若成立，則表明匹配到密文，將返回的密文集CT′發(fā)送給用戶，搜索憑證TK和密文密鑰CTK發(fā)送給審計(jì)中心；若等式不成立，輸出⊥。

Audit(SKid,TK,CTK)→{0,1}：審計(jì)算法。輸入用戶私鑰SKid、搜索憑證TK和中間密文CTK。審計(jì)中心首先驗(yàn)證該用戶使用的私鑰SKid中的K′與問(wèn)責(zé)列表中此用戶id所對(duì)應(yīng)的θ是否相等，如果不相等，則該私鑰有被泄露、販賣或者非法盜用的嫌疑，因此該用戶不能訪問(wèn)此文件，返回⊥。同時(shí)，需要對(duì)該用戶以及通過(guò)運(yùn)行追蹤算法定位到的私鑰所有者進(jìn)行問(wèn)責(zé)；如果相等，審計(jì)中心繼續(xù)驗(yàn)證式（2）是否成立，若等式成立，將該返回密文集所對(duì)應(yīng)的參數(shù)ω、ω1、ω2和Dr發(fā)送給用戶；若不成立，則該用戶沒(méi)有權(quán)限訪問(wèn)此文件，輸出⊥。

Decrypt(SKid,CT′,ω,ω1,ω2,Dr)→(k) ：解 密 算 法。輸入用戶私鑰SKid、返回密文CT′和密文參數(shù)ω、ω1、Dr，用戶用式（3）解出用CP-ABE技術(shù)加密的密鑰k，再用k解密文件密文CT，即完成了對(duì)文檔的解密。

Revoke(V)：用戶撤銷算法。當(dāng)用戶的數(shù)據(jù)集合發(fā)生改變時(shí)，證書(shū)中心更新用戶的版本信息為V′=(id,，并發(fā)送給審計(jì)中心，用戶對(duì)應(yīng)于舊版本信息V=(id,vid)的私鑰SKid將不能通過(guò)審計(jì)，因此實(shí)現(xiàn)了用戶的撤銷。只有當(dāng)用戶向證書(shū)中心重新申請(qǐng)授權(quán)且生成對(duì)應(yīng)于新版本信息的私鑰SKid′時(shí)，用戶才能解密被授權(quán)的密文。

Trace(PK,TA,SKid)→(id)：審計(jì)中心運(yùn)行追蹤算法。輸入系統(tǒng)公鑰PK，問(wèn)責(zé)列表TA和用戶私鑰SKid，首先審計(jì)中心驗(yàn)證該私鑰是否合理，如果私鑰SKid不合理，輸出⊥；如果私鑰SKid合理，即SKid的形式是SKid=(K,K′,K1,K2,{Xj,Yj}aj∈S)，并且能使式（4）～式（6）成立，在問(wèn)責(zé)列表中查找K′，輸出對(duì)應(yīng)的身份id，當(dāng)有必要撤銷該用戶時(shí)，審計(jì)中心將該用戶的版本信息設(shè)置為V*=(id,0)，并撤銷其屬性。

正確性：

5 安全性分析

本文方案是能夠確保文件安全的，數(shù)據(jù)屬主用傳統(tǒng)對(duì)稱加密算法對(duì)文件進(jìn)行離線預(yù)加密，再用密文策略屬性基加密方案對(duì)預(yù)加密文件的密鑰k進(jìn)行在線加密，當(dāng)用戶的屬性滿足訪問(wèn)策略時(shí)才可解密獲得密鑰k。同時(shí)，本文方案可以防共謀攻擊，即便用戶用私鑰共謀生成了搜索憑證，但該搜索憑證是不能通過(guò)審計(jì)的，用戶無(wú)法通過(guò)共謀來(lái)獲取文件信息。此外，本文是抗選擇關(guān)鍵字攻擊和具有可問(wèn)責(zé)安全性的，抗選擇關(guān)鍵字攻擊的證明與文獻(xiàn)[11]中的證明相似，本文不再進(jìn)行證明。本章將要證明本文方案基于q′-SDH 假設(shè)下是可問(wèn)責(zé)的。證明過(guò)程具體如下。

定理1若q′-SDH 假設(shè)成立，且私鑰詢問(wèn)次數(shù)qs≤q′，那么本文方案是可問(wèn)責(zé)的。

在證明定理1前，首先證明引理1。

引理1如果BB（Boneh-Boyen）[14]簽名方案在弱選擇消息攻擊下的存在性是不可偽造的，則本文方案是可問(wèn)責(zé)的。

證明對(duì)于本文方案，如果存在一個(gè)多項(xiàng)式時(shí)間敵手A，能夠以不可忽略的優(yōu)勢(shì)ε贏得下述問(wèn)責(zé)游戲，則可以構(gòu)造出一個(gè)仿真器B在弱選擇消息攻擊下，能夠以同樣的優(yōu)勢(shì)ε構(gòu)造一個(gè)BB簽名。游戲中挑戰(zhàn)者C與仿真器B進(jìn)行交互。

（1）初始化。挑戰(zhàn)者C將BB 簽名方案的公鑰PK*={p,g,G,ga}發(fā)送給仿真器B，仿真器B選擇隨機(jī)數(shù)α,β,a,b,c∈Zp，同時(shí)定義兩個(gè)哈希函數(shù)H1:{0,1}*→G和H2:{0,1}*→Zp，將公 鑰PK=(G,GT,e,p,g,gα,e(g,g)β,ga,gb,gc,H1,H2) 發(fā)送給敵手A，并初始化一個(gè)問(wèn)責(zé)列表TA=?。

（2）詢問(wèn)階段。敵手A向仿真器B發(fā)送(id1,S1),(id2,S2),…,(idi,Si),…,(idq,Sq)進(jìn)行q次私鑰詢問(wèn)，獲得對(duì)應(yīng)的私鑰。仿真器B選擇隨機(jī)數(shù)θi∈Zp（如果θi在問(wèn)責(zé)列表TA中已經(jīng)存在或者θi=-α，則重新隨機(jī)選取θi），向挑戰(zhàn)者C詢問(wèn)θi的BB 簽名。挑戰(zhàn)者將簽名發(fā)送給仿真器B。仿真器B為Si中的每個(gè)屬性隨機(jī)選取k1,k2,…,kj∈Zp，r∈Zp，計(jì)算Ki=,,，最后將輸出的私鑰發(fā)送給敵手A，將數(shù)組(θi,idi)插入到問(wèn)責(zé)列表TA中。

（3）私鑰偽造。敵手選擇一個(gè)私鑰SK*發(fā)送給仿真器B。假設(shè)敵手A在上述游戲中獲勝，那么有Trace(PK,TA,SK*)?(Λ,id1,id2,…,idq)，同 時(shí)SKid=(K,K′,K1,可以通過(guò)私鑰合理性檢驗(yàn)，并且K′?{θ1,θ2,…,θq}。則有：

設(shè)u為未知元，K2=gu。將K2帶入式（10）可得到，將K1帶入式（9）中可以得到。仿真器B計(jì)算，且K′∈Zp，因此得到是一個(gè)有效的簽名。因此仿真器B在弱選擇消息攻擊下，以優(yōu)勢(shì)ε對(duì)BB簽名進(jìn)行了存在性的偽造。 □

由文獻(xiàn)[14]可得出引理2。

引理2若q′-SDH 假設(shè)成立，且私鑰詢問(wèn)次數(shù)qs≤q′，那么在弱選擇消息攻擊下，BB 簽名是存在性不可偽造的。

最后，定理1可由引理1和引理2直接證出，因此本文方案基于q′-SDH 假設(shè)下是可問(wèn)責(zé)的。

6 實(shí)驗(yàn)分析

本章包括可問(wèn)責(zé)性驗(yàn)證和性能對(duì)比兩個(gè)實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境為L(zhǎng)inux系統(tǒng)Intel Core i5-6200U CPU 2.4 GHz和4 GB 內(nèi)存，實(shí)驗(yàn)代碼基于對(duì)cp-abe-0.11 庫(kù)[15]修改和編寫(xiě)，并且使用基于橢圓曲線y2=x3+x構(gòu)造的160 bit橢圓曲線群。

6.1 可問(wèn)責(zé)性驗(yàn)證

驗(yàn)證本文方案的可問(wèn)責(zé)性，即驗(yàn)證該方案能夠僅根據(jù)未知用戶的私鑰就可以追蹤到該用戶的身份信息id，并對(duì)其進(jìn)行問(wèn)責(zé)。實(shí)驗(yàn)方法如下：首先選擇4個(gè)授權(quán)用戶，其中用戶的主要相關(guān)參數(shù)取值和私鑰所屬對(duì)應(yīng)關(guān)系如表1 所示（θ為56 bit 的大素?cái)?shù)），接著運(yùn)行追蹤算法，隨機(jī)選取一個(gè)私鑰作為輸入，重復(fù)20 次，最后將每次輸入的私鑰和輸出的id對(duì)應(yīng)地記錄在表格中。

實(shí)驗(yàn)結(jié)果記錄情況如表2 所示，從表中可以看出，每次實(shí)驗(yàn)輸出的用戶id與輸入的用戶私鑰的對(duì)應(yīng)關(guān)系均同表1中二者的對(duì)應(yīng)關(guān)系一致，即根據(jù)用戶的私鑰正確追蹤到了該用戶的身份，因此該方案是可問(wèn)責(zé)的。

Table 1 Parameter value表1 參數(shù)取值

Table 2 Experimental result表2 實(shí)驗(yàn)結(jié)果

6.2 性能對(duì)比

6.2.1 理論對(duì)比分析

本節(jié)將從功能上和性能上對(duì)本文方案與近幾年比較典型的方案進(jìn)行理論對(duì)比分析。

功能對(duì)比如表3所示，除了文獻(xiàn)[16]方案，其他方案都支持多關(guān)鍵字查詢；本文方案和文獻(xiàn)[8]中的方案支持用戶撤銷，可靈活管理用戶權(quán)限；文獻(xiàn)[16]和文獻(xiàn)[8]中的方案采用與門(mén)訪問(wèn)結(jié)構(gòu)，表達(dá)能力比較弱，本文采用的樹(shù)訪問(wèn)結(jié)構(gòu)表達(dá)能力較強(qiáng)；在加密方面，文獻(xiàn)[7-8,10,16]方案均采用的是直接對(duì)文件進(jìn)行在線加密，當(dāng)文件較大時(shí)，計(jì)算負(fù)擔(dān)較重，而本文方案是對(duì)文件的離線預(yù)加密密鑰進(jìn)行在線加密，遠(yuǎn)小于對(duì)文件加密的計(jì)算量，有效地提升了系統(tǒng)的線上資源利用率；此外，本文方案是可問(wèn)責(zé)的，可以確定私鑰泄露者的身份，并將其撤銷，保障系統(tǒng)的安全。

Table 3 Functional comparison表3 功能對(duì)比

性能對(duì)比如表4 所示，其中N表示系統(tǒng)屬性個(gè)數(shù)，E和ET分別表示為G和GT上的指數(shù)運(yùn)算，S為用戶的屬性個(gè)數(shù)，用戶搜索關(guān)鍵字個(gè)數(shù)為t，數(shù)據(jù)屬主選取關(guān)鍵字的個(gè)數(shù)為m，其中t≤m。綜合表1 的功能對(duì)比可以看出，文獻(xiàn)[16]中的方案功能較少，文獻(xiàn)[8]的索引生成和陷門(mén)生成計(jì)算量與系統(tǒng)屬性相關(guān)，而系統(tǒng)屬性數(shù)目龐大，導(dǎo)致計(jì)算開(kāi)銷過(guò)大，文獻(xiàn)[7]和文獻(xiàn)[10]方案中的索引生成和陷門(mén)生成效率較高，但搜索的計(jì)算開(kāi)銷較大，且功能上不支持撤銷和問(wèn)責(zé)。因此，綜合考慮本文方案較其他方案有明顯優(yōu)勢(shì)。

Table 4 Performance comparison表4 性能對(duì)比

6.2.2 實(shí)驗(yàn)對(duì)比分析

本節(jié)實(shí)驗(yàn)將分別從索引生成時(shí)間隨關(guān)鍵字?jǐn)?shù)量的增長(zhǎng)的變化情況、陷門(mén)生成時(shí)間隨關(guān)鍵字?jǐn)?shù)量的增長(zhǎng)的變化情況和搜索時(shí)間隨用戶屬性數(shù)量的增長(zhǎng)的變化情況三方面對(duì)本文方案與文獻(xiàn)[7]、文獻(xiàn)[8]中的方案進(jìn)行仿真對(duì)比實(shí)驗(yàn)。分別運(yùn)行上述3 個(gè)方案的索引生成算法（本文的索引是通過(guò)運(yùn)行在線加密算法生成的，因此本文的索引生成算法即為在線加密算法）、陷門(mén)生成算法和搜索算法，記錄每個(gè)算法運(yùn)行的時(shí)間，得到實(shí)驗(yàn)數(shù)據(jù)。其中，實(shí)驗(yàn)數(shù)據(jù)取運(yùn)行20 次的平均值，得出數(shù)據(jù)用Origin lab 進(jìn)行仿真并繪制對(duì)比圖，對(duì)比結(jié)果如圖2、圖3、圖4所示。

Fig.2 Index generation time圖2 索引生成時(shí)間

Fig.3 Trapdoor generation time圖3 陷門(mén)生成時(shí)間

Fig.4 Search time圖4 搜索時(shí)間

圖2 為本文方案與文獻(xiàn)[7]、文獻(xiàn)[8]中的方案的索引生成時(shí)間隨關(guān)鍵字?jǐn)?shù)量變化的對(duì)比曲線。其中，系統(tǒng)屬性個(gè)數(shù)的取值為N=50，用戶屬性S=5，m的取值為{2,4,6,8,10,12,14,16,18,20}。由圖2 可以看出，文獻(xiàn)[8]中方案的索引生成時(shí)間僅與系統(tǒng)屬性個(gè)數(shù)有關(guān)，因此索引生成時(shí)間不隨關(guān)鍵字?jǐn)?shù)量的增加而改變，但系統(tǒng)屬性個(gè)數(shù)數(shù)目較大，其計(jì)算量遠(yuǎn)高于文獻(xiàn)[7]中的方案和本文方案；本文方案與文獻(xiàn)[7]的索引生成時(shí)間均與關(guān)鍵字?jǐn)?shù)量呈正比，且曲線接近，因此二者的計(jì)算開(kāi)銷大致相同。

圖3 為本文方案與文獻(xiàn)[7]、文獻(xiàn)[8]中的方案的陷門(mén)生成時(shí)間隨關(guān)鍵字?jǐn)?shù)量變化的對(duì)比曲線，其中系統(tǒng)屬性個(gè)數(shù)的取值為N=40，用戶屬性S=5，m的取值為{2,4,6,8,10,12,14,16,18,20}。從圖3 中可以看出，本文方案與文獻(xiàn)[8]中方案的陷門(mén)生成時(shí)間均不隨關(guān)鍵字?jǐn)?shù)量的變化而變化，但文獻(xiàn)[8]中方案的陷門(mén)生成時(shí)間與系統(tǒng)屬性數(shù)目相關(guān)，因此曲線明顯高于本文方案；文獻(xiàn)[7]中方案的陷門(mén)生成時(shí)間與關(guān)鍵字?jǐn)?shù)量呈正比，而本文方案與用戶屬性個(gè)數(shù)相關(guān)，因此在關(guān)鍵字?jǐn)?shù)量較少時(shí)，文獻(xiàn)[7]的陷門(mén)生成效率高，而當(dāng)關(guān)鍵字的數(shù)量較大時(shí)，本文方案的效率更高。

圖4 為本文方案與文獻(xiàn)[7]、文獻(xiàn)[8]中的方案的搜索時(shí)間隨關(guān)鍵字?jǐn)?shù)量變化的對(duì)比曲線，其中系統(tǒng)屬性個(gè)數(shù)的取值為N=40，用戶屬性個(gè)數(shù)S的取值為{2,4,6,8,10,12,14,16,18,20}。從圖4中可以看出，3個(gè)方案的搜索時(shí)間都與用戶屬性個(gè)數(shù)成正比，但文獻(xiàn)[7]的搜索計(jì)算量明顯高于其他二者，本文方案的搜索開(kāi)銷略高于文獻(xiàn)[8]，但相差不大。

綜合以上分析，本文實(shí)際性能的驗(yàn)證與理論性能分析一致，證明本文方案是高效可行的。

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

本文提出了一種可以對(duì)私鑰泄密者問(wèn)責(zé)的多關(guān)鍵字可搜索加密方案，一旦有用戶將自己的私鑰泄露或者販賣給他人，可以確定其身份，并將其撤銷，同時(shí)在q′-SDH 假設(shè)下證明了本文是具有可問(wèn)責(zé)安全性的；此外，用在線/離線加密提高系統(tǒng)效率，支持多關(guān)鍵字查詢提升用戶搜索體驗(yàn)。實(shí)驗(yàn)驗(yàn)證和理論分析表明，本文方案是實(shí)用、高效的。下一步將要研究適用于移動(dòng)云存儲(chǔ)的可搜索加密方案。