可問責的多關鍵字可搜索加密方案*

裴樹軍，易 鑫，陳彥橦，苗 輝

哈爾濱理工大學 計算機科學與技術學院，哈爾濱150080

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

1 引言

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

可搜索加密技術在提出之后，即得到了廣泛的研究和迅速的發展[2]。在最早的可搜索加密技術中，用戶只能搜索自己加密存儲在云端的密文，實用性不強，因此Boneh等人[3]于2004年結合公鑰加密技術構造了一個可搜索加密方案，解決了其他用戶無法檢索密文數據的問題。

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

為此，本文提出了一種可問責的多關鍵字可搜索加密方案，該方案有以下4點優勢：

（1）可問責。當不法用戶惡意泄露私鑰時，可以通過運行追蹤算法對泄密者進行身份的確認，并撤銷該用戶，保障了系統的安全。

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

（3）多關鍵字搜索。用戶輸入關鍵字集來檢索目標文件，防止查詢時返回過多不相關的文件，增強用戶搜索體驗。

（4）可撤銷。當用戶的屬性集發生改變時，或者被判定為泄密者時，可以撤銷其搜索權限。

2 相關技術

2.1 雙線性對

定義1（雙線性映射）令G1、GT是兩個階為素數p的乘法循環群，G1的生成元為g，存在雙線性映射e:G1×G1→GT滿足：

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

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

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

2.2 策略樹

本文用策略樹來描述訪問控制策略。一棵策略樹中包括葉子節點和非葉子節點，每一個非葉子節點f代表一個門限，其值為kf，子節點個數為nf。對子節點從左到右依次編號1,2,…,nf，其中1 ≤kf≤nf，當節點f是或門時，kf=1，當節點f是與門時，kf=nf。p(f)是節點f的父節點，index(f)是節點f的編號。每個葉子節點l都與屬性值相關，lvs(T)表示策略樹T的所有葉子節點的集合，Tf表示以節點f為根節點的策略樹T的子樹，attr(l)表示葉子節點l的屬性值。

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

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

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

2.3 q'-SDH 假設

定義2（q′-SDH假設（strong Diffie-Hellman assumption））[14]G是階為素數p，生成元為g的循環群。G中的q′-SDN 難題定義為：隨機選取x∈Zp，給定(g,gx,gx2,…,gxq′)，計算，其中c∈Zp。ε為一個算法A解決G中的q′-SDH 難題優勢，當，即一個多項式時間算法能以不可忽略的優勢ε解決群中的q′-SDH 難題，則q′-SDH 假設成立。

3 系統模型與安全模型

3.1 系統模型

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

Fig.1 System model圖1 系統模型

證書中心負責對系統進行初始化建立，為用戶頒發私鑰和生成、更新版本信息；數據屬主負責加密待上傳文件，將生成的索引值和中間密文發送給云服務器；用戶根據搜索的關鍵字集生成搜索憑證和陷門值，并同關鍵字位置集一起發送給云服務器；云服務器負責驗證用戶的屬性是否滿足訪問策略，然后向審計中心請求搜索參數，匹配索引值和陷門值，接著向審計中心發送搜索憑證和陷門值，最后將得到的密文發送給用戶；審計中心負責通過與云服務器交互來審查用戶是否有權限訪問密文，審查通過后，向用戶發送密文參數，同時也負責判定用戶所使用的私鑰是否存在被泄露、出售嫌疑，并對私鑰泄密者進行追蹤問責。

3.2 算法定義

本文方案具體包括以下10個算法：

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

KeyGen(PK,MSK,id,S)→(SKid,V)：密鑰生成算法由證書中心運行。輸入系統公鑰PK、主密鑰MSK、用戶的身份標識id和該用戶的屬性集合S∈U，輸出對應于(id,S)的用戶私鑰SKid和版本信息V=(id,vid)，并將該用戶的id插入到問責列表TA中。

Offline.Encrypt(PK,M)→(CT,k)：離線加密算法（預加密算法）由數據屬主執行。輸入系統公鑰PK和待加密文件M，用傳統的對稱加密算法對文件M進行離線預加密，輸出預加密密鑰k和文件密文CT。

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

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

Search(PK,TRW′,I)→(CT′)：搜索算法由云服務器執行。當用戶滿足訪問控制策略時，云服務器向審計中心發送搜索憑證TK和中間密文CTK，審計中心根據遞歸算法進行自底向上的計算，得到Dr，并返回給云服務器；云服務器對陷門值TRW′和索引值I進行匹配，得到返回密文集CT′，并返回給用戶。同時，將返回密文集CT′對應的搜索憑證TK和中間密文CTK發送給審計中心。

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

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

Revoke(V)：用戶撤銷算法由證書中心和審計中心合作運行。當用戶的數據集合發生改變時，證書中心更新用戶的版本信息為V′=(id,vid′)，并發送給審計中心，用戶對應于舊版本信息V=(id,vid)的私鑰SKid將不能通過審計，因此實現了用戶的撤銷。

Trace(PK,TA,SKid)→(id)：追蹤算法由審計中心執行。輸入系統公鑰PK，問責列表TA和用戶私鑰SKid，審計中心驗證該私鑰是否合理，如果合理，輸出SKid對應的身份id，當有必要撤銷該用戶時，審計中心直接將該用戶的版本信息設置為V*=(id,0)。

3.3 可問責性安全模型

定義3如果敵手A在任何多項式時間在下述游戲中獲勝的優勢是可以忽略的，則稱本文方案是可問責的。

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

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

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

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

4 方案構造

本文提出了一種可問責的多關鍵字可搜索加密方案，具體算法構造如下。

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

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

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

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

步驟1設根節點多項式為qr(0)=t2，節點r門限值為kr，隨機選擇其他kr-1 個不同節點，則可以得到根節點多項式qr(x)。

步驟2對于非根節點f，設qf(0)=qp(f)(index(f))，節點f門限值為kf，隨機選擇其他kf-1 個不同節點，則可以得到非根節點多項式qf(x)。

步驟3按上述遞歸算法最后可以得到葉子節點l的多項式ql(x)。

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

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

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

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

步驟1云服務器驗證用戶是否滿足訪問策略，若通過驗證，云服務器將中間密文CTK和搜索憑證TK發送給審計中心，請求Dr，否則搜索失敗。

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

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

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

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

Revoke(V)：用戶撤銷算法。當用戶的數據集合發生改變時，證書中心更新用戶的版本信息為V′=(id,，并發送給審計中心，用戶對應于舊版本信息V=(id,vid)的私鑰SKid將不能通過審計，因此實現了用戶的撤銷。只有當用戶向證書中心重新申請授權且生成對應于新版本信息的私鑰SKid′時，用戶才能解密被授權的密文。

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

正確性：

5 安全性分析

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

定理1若q′-SDH 假設成立，且私鑰詢問次數qs≤q′，那么本文方案是可問責的。

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

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

證明對于本文方案，如果存在一個多項式時間敵手A，能夠以不可忽略的優勢ε贏得下述問責游戲，則可以構造出一個仿真器B在弱選擇消息攻擊下，能夠以同樣的優勢ε構造一個BB簽名。游戲中挑戰者C與仿真器B進行交互。

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

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

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

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

由文獻[14]可得出引理2。

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

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

6 實驗分析

本章包括可問責性驗證和性能對比兩個實驗，實驗環境為Linux系統Intel Core i5-6200U CPU 2.4 GHz和4 GB 內存，實驗代碼基于對cp-abe-0.11 庫[15]修改和編寫，并且使用基于橢圓曲線y2=x3+x構造的160 bit橢圓曲線群。

6.1 可問責性驗證

驗證本文方案的可問責性，即驗證該方案能夠僅根據未知用戶的私鑰就可以追蹤到該用戶的身份信息id，并對其進行問責。實驗方法如下：首先選擇4個授權用戶，其中用戶的主要相關參數取值和私鑰所屬對應關系如表1 所示（θ為56 bit 的大素數），接著運行追蹤算法，隨機選取一個私鑰作為輸入，重復20 次，最后將每次輸入的私鑰和輸出的id對應地記錄在表格中。

實驗結果記錄情況如表2 所示，從表中可以看出，每次實驗輸出的用戶id與輸入的用戶私鑰的對應關系均同表1中二者的對應關系一致，即根據用戶的私鑰正確追蹤到了該用戶的身份，因此該方案是可問責的。

Table 1 Parameter value表1 參數取值

Table 2 Experimental result表2 實驗結果

6.2 性能對比

6.2.1 理論對比分析

本節將從功能上和性能上對本文方案與近幾年比較典型的方案進行理論對比分析。

功能對比如表3所示，除了文獻[16]方案，其他方案都支持多關鍵字查詢；本文方案和文獻[8]中的方案支持用戶撤銷，可靈活管理用戶權限；文獻[16]和文獻[8]中的方案采用與門訪問結構，表達能力比較弱，本文采用的樹訪問結構表達能力較強；在加密方面，文獻[7-8,10,16]方案均采用的是直接對文件進行在線加密，當文件較大時，計算負擔較重，而本文方案是對文件的離線預加密密鑰進行在線加密，遠小于對文件加密的計算量，有效地提升了系統的線上資源利用率；此外，本文方案是可問責的，可以確定私鑰泄露者的身份，并將其撤銷，保障系統的安全。

Table 3 Functional comparison表3 功能對比

性能對比如表4 所示，其中N表示系統屬性個數，E和ET分別表示為G和GT上的指數運算，S為用戶的屬性個數，用戶搜索關鍵字個數為t，數據屬主選取關鍵字的個數為m，其中t≤m。綜合表1 的功能對比可以看出，文獻[16]中的方案功能較少，文獻[8]的索引生成和陷門生成計算量與系統屬性相關，而系統屬性數目龐大，導致計算開銷過大，文獻[7]和文獻[10]方案中的索引生成和陷門生成效率較高，但搜索的計算開銷較大，且功能上不支持撤銷和問責。因此，綜合考慮本文方案較其他方案有明顯優勢。

Table 4 Performance comparison表4 性能對比

6.2.2 實驗對比分析

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

Fig.2 Index generation time圖2 索引生成時間

Fig.3 Trapdoor generation time圖3 陷門生成時間

Fig.4 Search time圖4 搜索時間

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

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

圖4 為本文方案與文獻[7]、文獻[8]中的方案的搜索時間隨關鍵字數量變化的對比曲線，其中系統屬性個數的取值為N=40，用戶屬性個數S的取值為{2,4,6,8,10,12,14,16,18,20}。從圖4中可以看出，3個方案的搜索時間都與用戶屬性個數成正比，但文獻[7]的搜索計算量明顯高于其他二者，本文方案的搜索開銷略高于文獻[8]，但相差不大。

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

7 結束語

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