支持關鍵詞任意連接搜索的屬性加密方案

宋衍，韓臻，陳棟，趙進華

(1.北京交通大學計算機與信息技術學院，北京 100044；2.信息保障技術重點實驗室，北京 100072)

支持關鍵詞任意連接搜索的屬性加密方案

宋衍1,2，韓臻1，陳棟1,2，趙進華2

(1.北京交通大學計算機與信息技術學院，北京 100044；2.信息保障技術重點實驗室，北京 100072)

構建一種基于素數階雙線性群的可搜索加密方案。基于屬性加密，實現每個關鍵詞密文能夠被多個用戶私鑰搜索，顯著降低細粒度訪問控制帶來的網絡帶寬和發送節點的處理開銷。基于多項式方程，支持對關鍵詞的任意連接搜索，顯著提高連接搜索的靈活性。對方案的性能進行了分析，并與現有的連接關鍵詞搜索方案進行了比較。

可搜索加密；屬性加密；連接關鍵詞；多項式方程

1 引言

隨著云計算的快速發展，數據外包成為一種廣泛的應用形式。數據使用者只是享受云環境提供的數據服務，而不用購買和維護自己的信息系統。這樣一是能夠提高數據管理的專業化程度，改善數據應用效率，二是用戶能夠根據需要隨意地增加和裁減服務的功能和容量，降低信息化投入。但是用戶在享受云存儲服務的同時，需要將數據交由云端的服務提供者來進行存儲和處理。其最主要的特征是：數據與其所有者分離，處于所有者不可控的區域內[1]。

在不可控環境中，加密是保證數據安全的最有效方法。但是，加密破壞了原有數據的值和大小關系等，密文不再具有可供檢索的語義和統計特性，因此，針對明文的檢索技術并不能直接應用于密文。傳統的處理方式是：服務提供者將所有滿足訪問控制策略的密文都返回給請求者，由請求者解密后再進行明文的檢索。這種方法簡單易行，但是，一方面，云端的計算和存儲等資源優勢無法得到有效利用，另一方面，返回大量數據需要占用相當多的網絡帶寬，解密也會給請求者帶來很大的計算量，因此，對客戶機配置和網絡質量有很高的要求，同時其效率也是不能被接受的。

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

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

目前，絕大多數的連接關鍵詞搜索方案采用了Golle[6]的假設，設置關鍵詞域來對位搜索和被搜索的關鍵詞。這種方式對于結構化、語義確定的數據具有較高的搜索效率，如郵件的首部信息；但是，對于非結構化的數據，則很難用固定的關鍵詞域覆蓋所有文件的準確內容[16]。因此，在實用性上有一定限制。

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

針對以上2個問題，本文提出一種新的連接關鍵詞可搜索屬性加密方案，文檔無需按照關鍵詞域來設置關鍵詞，搜索運算時無需對位密文和陷門中的關鍵詞。方案基于屬性關聯實現搜索的細粒度訪問控制，基于多項式方程實現關鍵詞的任意連接搜索。具有較高的安全性，能夠抵御選擇關鍵詞攻擊（CKA,chosen keyword attack）。

2 預備知識

2.1 雙線性群及復雜性假設

假設p為素數，G1、G2和GT為p階循環群，g1、g2和 gT分別為其生成元。e∶ G1×G2→GT為雙線性映射，則有：

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

3)G1、G2和GT中的運算以及雙線性映射e都是在多項式時間內可完成的。

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

2.2 系統模型

系統包括4個參與角色，記為{UM,Serv,DO,DReq}。其中，UM 是授權管理機構，負責系統的初始化，并管理用戶的屬性及其密鑰生成；Serv是云端的服務提供者，負責數據的存儲和搜索；DO是數據擁有者，將自己的數據加密后交由Serv存儲和管理；DReq是數據請求者，向Serv請求數據搜索服務。UM是完全可信的，并且UM與DReq的對話是安全的；Serv是“誠實但狡猾”的，能夠忠實地執行規定的操作，但可能會竊取數據的信息，或與DReq發起共謀攻擊。方案的系統模型及工作流程如圖1所示。

1)UM管理所有用戶的屬性集合；UM調用初始化算法生成公開參數和主私鑰；公開參數用于數據加密、用戶私鑰生成、陷門生成和密文搜索算法，發布給系統的合法用戶；主私鑰用于生成用戶私鑰，由UM保存。

2)DO向UM申請系統的公開參數。

3)UM將公開參數返回給DO。

4)DO從文檔中選出關鍵詞集合，調用對稱算法加密文檔，對稱加密算法選用現有的 3DES或AES等即可。

5)DO制定訪問控制策略，調用屬性加密公鑰算法分別加密對稱加密密鑰和關鍵詞集合。

6)DO將文檔密文、對稱密鑰密文和關鍵詞集合密文組成數據密文，發送給Serv存儲。

7)DReq如果已經申請過用戶私鑰，則進入10)，否則向UM申請用戶私鑰。

8)UM調用私鑰生成算法，生成與用戶屬性集匹配的用戶私鑰。

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

10)DReq調用陷門生成算法，生成被搜索關鍵詞集合相應的陷門；陷門是關鍵詞集合的一個單向函數值，能夠用于關鍵詞的判斷，而不會泄露關鍵詞的信息。

11)DReq將自身的屬性集和陷門發送給Serv。

12)Serv首先根據DReq的屬性集篩選滿足訪問控制策略的數據密文，然后調用搜索算法，對搜索關鍵詞集合的密文和被搜索關鍵詞集合的陷門進行運算，驗證同時滿足訪問控制策略和搜索策略的數據密文；如果陷門所屬的DReq滿足密文的訪問控制策略，并且陷門的關鍵詞集合包含于密文所代表的關鍵詞集合，則結果為一個固定值，否則結果為隨機值。

13)將滿足要求的文檔密文和對稱密鑰密文返回給DReq。

14)DReq利用自己掌握的用戶私鑰，調用屬性加密公鑰算法，解密對稱密鑰；如果DReq滿足訪問控制策略要求，則能夠得出正確的對稱密鑰，接著調用對稱加密算法解密出文檔明文，否則，不能得出正確的對稱密鑰，無法解密出文檔明文。

圖1 系統模型及工作流程

在 12)中，雖然搜索算法能夠辨別出密文是否同時滿足訪問控制策略和搜索策略，但是由 Serv首先根據DReq的屬性集篩選滿足訪問控制策略的數據密文，則可以在計算之前就過濾掉不滿足訪問控制策略的數據密文，從而減少搜索算法的調用次數，降低計算開銷。

在9)中對用戶私鑰的公鑰算法加密，在4)、14)中對文檔的對稱算法加解密以及第5)、14)中對對稱密鑰的屬性算法加解密，均有成熟技術可用，這里不再做研究。因此，本文之后的章節將忽略對文檔及其對稱密鑰的處理，而只考慮關鍵詞的處理。經過簡化后，一個支持關鍵詞任意連接搜索的基于屬性加密方案由以下5種多項式時間算法組成。

1)Setup(1λ)→(pm,mk)∶ UM 執行該算法以初始化系統；輸入一個安全參數1λ，輸出一個公開參數pm和一個主私鑰mk。

2)KeyGen(Atts,mk,pm)→sk∶ UM 根據 DReq 提供的屬性集為其生成相應的用戶私鑰；輸入公開參數pm、主私鑰mk和DReq的屬性集Atts，輸出對應的私鑰sk。

3)Encrypt(pm,W,T)→cph∶ DO根據訪問控制策略加密文檔的關鍵詞集合；輸入公開參數 pm、文檔的關鍵詞集合W，以及訪問結構T，輸出密文cph。

4)TokenGen(sk,pm,W′)→tk∶ DReq 生成搜索陷門；輸入公開參數pm，用戶私鑰sk，關鍵詞集合W′，輸出關鍵詞集合的陷門tk。

5)Search(tk,cph)→1∶Serv根據陷門對密文進行搜索；輸入陷門tk和密文cph，若用戶的屬性集Atts滿足密文的訪問結構T，并且搜索的關鍵詞集合W′包含于文檔的關鍵詞集合W，則返回1，否則返回隨機值。

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

2.3 訪問控制

使用樹形結構表示訪問控制策略，具有清晰、簡便的優點[19]。訪問樹的內部節點代表關系（門），包括 and（與）、or（或）和 threshold（門限）；葉子節點代表屬性。假設numv為節點v下子節點的個數，kv為節點v的門限值，則有1≤kv≤numv。2種特別的情況是，當kv=1時，節點v代表關系or；當kv=numv時，節點v代表關系and。使用parent(v)表示節點v的父節點，ind(v)表示節點v在父節點下的索引號，lvs(T)表示訪問樹T中所有葉子節點組成的集合，att(v)表示葉子節點v所代表的屬性，Tv表示T中根為v的子樹。

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

1)當v是葉子節點時，如果att(v)∈Atts，則設置F(Atts,Tv)=1；否則F(Atts,Tv)=0。

2)當 v是內部節點時，假設v1,v2,…,vnum為v的子節點，如果存在一個子集 I?{1,…,numv}使|I|≥kv，并且對于?j∈I，有那么設置F(Atts,Tv)=1；否則，設置F(Atts,Tv)=0。

對于訪問樹T，本文將T的秘密共享算法表示為

算法從上至下為T中的每個內部節點v構造一個 kv?1次一元多項式 qv，并為每個內部節點和葉子節點賦值。

1)如果v是T的根節點，設置qv(0)=q，并為多項式qv隨機選取kv?1個系數。

2)如果v是T中除根節點外的其他內部節點，設置qv(0)=qparent(v)(ind(v))，并為多項式qv隨機選取kv?1 個系數。

3)如果 v是 T的葉子節點，設置 qv(0)=qpar-ent(v)(ind(v))。

根據訪問樹T的結構，算法從底向上執行如下步驟。

對于節點 v，如果 F(att(u1),…,att(um),Tv)=0，則繼續；

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

如果v是葉子節點，則存在一個uj，使uj=v；設置

3 方案設計

3.1 方案構造

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

1)Setup(1λ)。運行算法 G(1λ)獲得(p,G1,G2,GT,e)。隨機選取b,c,d∈Zp*，發布公開參數為

保存主密鑰為

2)KeyGen(Atts,mk,pm)。構造屬性集 Atts對應的私鑰。隨機選擇，計算對于每個 attj∈Atts，隨機選擇 rj∈Zp*，計算構造私鑰如下

3)Encrypt(pm,W,T)。加密關鍵詞集合 W={w1,…,wm}。隨機選取q∈Zp作為訪問樹T的秘密共享值，執行{qv(0)|v∈lvs(T)}←Share(T,q)，使T中的每個葉子節點 v得到一個關于 q的秘密共享值qv(0)，并為每個葉子節點計算和隨機選擇構造一個 m次多項式為

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

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

然后計算根節點的秘密值

3.2 正確性驗證

做如下計算

當搜索的關鍵詞集合包含于文檔的關鍵詞集合，即W′∈W時，有當屬性集Atts滿足訪問樹T，即F(Atts,T)=1時，有因此

4 方案分析

4.1 安全性分析

實現訪問控制的基本思想是：將每個陷門和密文分為 2部分：1)與關鍵詞明文相關聯；2)與屬性相關聯，陷門中的屬性表示DReq的屬性集，密文中的屬性表示DO的訪問控制策略。如果DReq的屬性集滿足DO的訪問控制策略，服務器能夠通過雙線性映射算法確定密文的關鍵詞集合是否包含陷門的關鍵詞集合。實現任意連接搜索的基本思想是：利用文檔的所有關鍵詞和2個隨機數構造一個次數等于關鍵詞個數的多項式，將多項式的系數以冪的形式發布；如果所搜索的關鍵詞都包含在文檔的關鍵詞集合中，則能夠利用拉格朗日插值公式還原出該隨機數，否則，返回結果不正確。

方案在私鑰生成、密文生成和陷門生成階段，分別使用隨機數將各組件關聯化和隨機化。以下從3個方面來說明或證明方案的安全性。

1)陷門不可偽造。DReq隨機選擇大數 s，使陷門的每個組件都是以s為指數的冪，如此以來，每個組件都通過s相關聯。在離散對數困難問題假設下，攻擊者無法通過已用陷門中的組件求解得到隨機數s的值，并偽造新陷門。當攻擊者隨機選擇s來偽造陷門時，只能構造陷門的組件H，還必須獲得用戶私鑰來構造陷門的組件tok0、tok1、A和B。

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

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

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

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

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

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

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

在挑戰階段，由于A不知道主密鑰，并且主密鑰的選擇與所有的關鍵詞無關，因此，從A的角度看來，密文中的組件Fi是均勻分布的，即構造的m次多項式 f(x)的系數是均勻分布的。在離散對數難題假設下，A無法從已經詢問過的密文和陷門中計算出主密鑰或者f(x)的系數。因此，在挑戰階段，A無法分辨出β是0還是1。

4.2 性能分析

本節將構造的方案與現有的支持連接關鍵詞子集搜索的加密方案在通信開銷、存儲開銷和計算開銷方面做詳細比較。其中，性能指標包括每個密文的長度和加密計算量，每個陷門的長度和計算量，以及DSP使用一個陷門針對一個密文進行搜索時的計算量。

密文長度關系到DO與DSP之間的通信開銷以及DSP的存儲開銷；陷門長度關系到DReq與DSP之間的通信開銷。加密計算量關系到DO的計算開銷，陷門計算量關系到DReq的計算開銷，搜索計算量關系到DSP的計算開銷。

在云計算的數據外包環境中，DO和DReq所在終端的計算能力、通信能力和存儲能力可能受限。由于公開參數和用戶私鑰等信息的存儲量并不大，因此，公開參數長度和用戶私鑰長度對用戶終端的影響很小，可以忽略。但是，要求密文長度、密文計算量、陷門長度和陷門計算量盡可能小。由于所有的密文都存儲在DSP端，并由DSP進行搜索計算，因此，密文長度大時，導致DSP存儲開銷大，DSP的存儲能力需要相應提高；而搜索的計算量大時，則對于DSP固定的計算能力來說，將帶來響應時間長的問題。

算法建立、用戶私鑰生成是由UM預先實現的，它們同公開參數長度、用戶私鑰長度一樣，與用戶體驗無太大關系，這里就不做比較了。

記P和M分別為循環群中的指數運算（橢圓曲線的點乘運算）和乘法運算（橢圓曲線的點加運算），E為雙線性映射運算，H為從群Zp到群G和GT（或從群G和GT到群Zp）的編碼運算。|G|表示群G和GT中元素的長度，|p|表示域Zp中元素的長度。m為每個文檔的關鍵詞數量，t為搜索的關鍵詞的數量。v表示屬性個數，u表示具有訪問權限的DReq個數，i表示系統中的用戶屬性總數。

連接搜索時，搜索條件是文檔的關鍵詞集合包含陷門的關鍵詞集合。當搜索的關鍵詞的數量大于文檔的關鍵詞的數量時，必然沒有文檔滿足搜索條件。因此，搜索的關鍵詞數量和文檔的關鍵數量之間存在關系t≤m。

在訪問樹中，葉子節點代表屬性，通過代表關系的內部節點進行組合，確定具有訪問權限的DReq集合。這使訪問樹可以通過規模很小、數量固定的屬性集來表示規模巨大、不斷增加的授權用戶集。訪問樹中的用戶屬性個數與屬性總數之間有關系v≤i。i個用戶屬性可以定義2i種用戶，v個用戶屬性在通過and關系組合時，定義最少的允許訪問用戶數量，這時u=2i?v，通過or關系組合時，定義最多的允許訪問用戶數量，這時u=v2i?1。因此有2i?v≤u≤v2i?1，即在大多數情況下，u 遠大于或者大于v，并且隨著u的增加，v并不增加。

采用對稱密鑰加密關鍵詞時，雖然單次加密和搜索的效率較高，但在多用戶場景中，訪問控制實現困難，當更改用戶權限時，需要花費大量的通信開銷和計算開銷來更新密文和分發密鑰，因此一般只適用于搜索自己存儲在服務器中的數據。所以，這里沒有把這類方案[6,15]列入性能對比，如表1所示。

表1 多用戶環境下連接關鍵詞搜索方案的性能對比

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

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

此外，本文方案支持非域形式的關鍵詞連接搜索，在多文檔應用場景中，當文檔不斷增加、文檔類型不斷豐富時，無需根據文檔語義調整關鍵詞域，重新加密關鍵詞，即能夠支持非結構化數據的密文檢索，因而具有更廣闊的應用前景。

5 結束語

本文基于屬性加密和多項式方程提出了一種連接關鍵詞可搜索加密方案。方案實現了“一對多”通信模式，支持多用戶環境下的細粒度訪問控制，顯著減小了大用戶量時的密文長度和加密計算量；實現了關鍵詞的任意連接搜索模式，支持針對非結構化數據的連接關鍵詞檢索。只是在陷門長度和搜索運算量上，增加了相應的開銷。下一步將重點研究通過融入代理加密機制，使首次搜索時權限分量的計算結果，能夠用于以后的搜索請求，避免每次搜索時重復發送屬性部分和計算權限分量，從而減小陷門的計算量和長度，達到降低數據請求者的計算和通信開銷，以及減少搜索時運算量的目的。

[1]項菲,劉川意,方濱興,等. 云計算環境下密文搜索算法的研究[J].通信學報,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]. 軟件學報,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]王尚平,劉利軍,劉亞玲. 一個高效的基于連接關鍵詞的可搜索加密方案[J]. 電子與信息學報,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]. 計算機學報,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

國家自然科學基金資助項目（No.60973112）；北京市教育委員會學科建設與研究生培養基金資助項目（No.BMKY2011B06）

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

宋衍（1982-），男，湖北老河口人，北京交通大學博士生，主要研究方向為密態計算、安全數據庫等。

韓臻（1962-），男，浙江寧波人，博士，北京交通大學教授、博士生導師，主要研究方向為信息安全體系結構、可信計算等。

陳棟（1982-），男，山西運城人，北京交通大學博士生，主要研究方向為網絡安全、軟件工程等。

趙進華（1981-），男，山東菏澤人，信息保障技術重點實驗室副研究員，主要研究方向為密碼理論與應用。