云存儲中支持屬性撤銷的多關(guān)鍵詞可搜索加密方案

黃保華，黃丕榮，趙偉宏，彭 麗

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，南寧 530004）

0 概述

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，用戶對數(shù)據(jù)處理和數(shù)據(jù)存儲的需求日益增加。為滿足高效的數(shù)據(jù)處理能力和海量數(shù)據(jù)存儲的需求，選擇將個人或企業(yè)的數(shù)據(jù)外包給云存儲服務(wù)器是當(dāng)前流行的做法，但是當(dāng)用戶將數(shù)據(jù)存儲在云端時，服務(wù)器并非完全可信，有可能工作在半可信或者惡意的模型下。半可信模型是指服務(wù)器試圖通過與用戶的交互獲取敏感信息，惡意模型是指服務(wù)器除了會試圖獲取用戶信息，還有可能破壞協(xié)議的執(zhí)行或者破壞數(shù)據(jù)的完整性和正確性。在這種數(shù)據(jù)外包的背景下，不可避免地會帶來數(shù)據(jù)的隱私性和安全性等方面的問題。

為防止非授權(quán)用戶訪問數(shù)據(jù)進(jìn)行非法操作，在外包數(shù)據(jù)之前，可以先對其進(jìn)行加密，最后以密文的形式交由云服務(wù)器進(jìn)行存儲管理。但這樣會限制外包數(shù)據(jù)的可用性，加密后的數(shù)據(jù)不能再根據(jù)原來的明文索引進(jìn)行檢索，傳統(tǒng)的明文檢索方案不再可行。因此，在對密文數(shù)據(jù)進(jìn)行檢索的同時保證關(guān)鍵詞隱私，成為當(dāng)前亟待解決的問題，可搜索加密技術(shù)應(yīng)運(yùn)而生。

本文將密文策略基于屬性加密與關(guān)鍵詞搜索相結(jié)合，提出一種支持屬性撤銷的多關(guān)鍵詞可搜索加密方案。該方案支持連接關(guān)鍵詞搜索，可提供靈活的多關(guān)鍵詞搜索功能。針對可能存在的訪問策略動態(tài)變化問題，能夠?qū)^期非授權(quán)用戶進(jìn)行屬性撤銷操作，使其更接近于真實(shí)場景需求。相對于效率較低的樹形訪問結(jié)構(gòu)，本文采用具有強(qiáng)表達(dá)能力的線性秘密共享方案作為訪問結(jié)構(gòu)。

1 相關(guān)工作

可搜索加密代表性的方案是SONG等［1］在2000年提出的線性掃描算法，由于此方案每進(jìn)行一次檢索都要掃描單篇文檔的關(guān)鍵詞集合，檢索效率較低，并且容易暴露關(guān)鍵詞在文檔中的位置信息，因此易受到關(guān)鍵詞統(tǒng)計(jì)攻擊。其搜索開銷與文檔數(shù)、關(guān)鍵詞總數(shù)成正比，當(dāng)文檔數(shù)和關(guān)鍵詞總數(shù)特別大時，該方案在實(shí)際應(yīng)用中的搜索效率較低。此后學(xué)術(shù)界有很多研究人員從功能性、安全性、搜索效率等方面對可搜索加密方案進(jìn)行改進(jìn)。KAMAR 等［2］提出支持文檔動態(tài)更新和密態(tài)索引動態(tài)構(gòu)建的密文檢索方案，該方案在更新用戶數(shù)據(jù)時，不需要重構(gòu)索引，通過擴(kuò)展倒排索引，設(shè)計(jì)一個關(guān)鍵詞搜索字典，以此來達(dá)到次線性的搜索時間。CURMOLA 等［3］分別在自適應(yīng)的非自適應(yīng)模型下設(shè)計(jì)具有高安全性和高效率的對稱加密關(guān)鍵詞搜索方案。

2005 年，SAHAI 等［4］提出一種基于屬性的加密方案。在該方案中，用戶的密文和密鑰可以使用一組屬性來標(biāo)識，如用戶的性別、年齡、工作等信息可以視為一組屬性。只有解密者擁有的屬性符合嵌入密文的屬性組時，解密者才能正確解密密文。2008年，WATERS等［5］用線性秘密共享（Linear Secret-Sharing Scheme，LSSS）矩陣表示密文的訪問控制結(jié)構(gòu)，相比樹形的訪問控制結(jié)構(gòu)，LSSS 在擁有相同性能和功能情況下有更好的表達(dá)能力，該基于屬性的加密方案具有高效和可證明安全的特點(diǎn)。由于加密文件的訪問策略是動態(tài)變化的，用戶屬性也是動態(tài)變化的，為應(yīng)對這種屬性動態(tài)變化的需求，文獻(xiàn)［6-8］提出一種支持用戶屬性自動撤銷基于屬性加密的解決方案。由于基于屬性加密的加解密算法計(jì)算量大，對于移動設(shè)備等計(jì)算力受限的設(shè)備來說是沉重的計(jì)算負(fù)擔(dān)，也會加快設(shè)備電池的消耗，為平衡設(shè)備的計(jì)算量和加密方案的安全性之間關(guān)系，文獻(xiàn)［9］提出將復(fù)雜計(jì)算外包給第三方服務(wù)器的基于屬性加密方案，能在一定程度上減輕輕量型設(shè)備的計(jì)算負(fù)擔(dān)。以上的方案僅提供了數(shù)據(jù)加解密功能，并沒有實(shí)現(xiàn)加密數(shù)據(jù)的搜索和共享功能，將基于屬性加密運(yùn)用在關(guān)鍵詞搜索中是其應(yīng)用場景之一。

傳統(tǒng)的可搜索加密方案沒有考慮到用戶的搜索權(quán)限，不能對加密的文件進(jìn)行細(xì)粒度的訪問控制，并且由于運(yùn)用對稱加密技術(shù)，僅適用于一對多場景且存在泄露密鑰的風(fēng)險。結(jié)合基于屬性加密技術(shù)，可搜索加密方案能夠在實(shí)現(xiàn)關(guān)鍵詞搜索的同時，又能夠?qū)崿F(xiàn)加密文件的細(xì)粒度訪問控制。曹素珍等［10］借助區(qū)塊鏈技術(shù)防篡改、去中心化的優(yōu)勢，將密態(tài)索引存儲于區(qū)塊鏈，加密數(shù)據(jù)存儲于云服務(wù)器，構(gòu)造一個可驗(yàn)證基于屬性的多關(guān)鍵詞搜索方案，系統(tǒng)的密鑰可安全地在公開信道傳輸。MICHALAS 等［11］將對稱可搜索加密與基于屬性加密技術(shù)相結(jié)合，構(gòu)造一個混合加密的可搜索加密方案，該方案既具有對稱可搜索加密方案高效檢索的特點(diǎn)，又能對用戶進(jìn)行訪問控制。YIN 等［12］提出密文策略基于屬性（CPABE）的可搜索加密方案，由于該方案只能進(jìn)行單關(guān)鍵詞搜索，因此會使服務(wù)器返回的搜索結(jié)果包含大量不相關(guān)的內(nèi)容而浪費(fèi)網(wǎng)絡(luò)帶寬，或者因?yàn)檫M(jìn)行多輪搜索而增加通信開銷。宋衍等［13］提出一種基于屬性加密的支持關(guān)鍵詞任意連接的搜索方案，該方案使用多項(xiàng)式方程實(shí)現(xiàn)對非結(jié)構(gòu)化數(shù)據(jù)的多關(guān)鍵詞連接搜索，但不支持用戶的屬性撤銷。陳燕俐等［14］提出一個密文策略基于屬性加密的關(guān)鍵詞搜索方案，該方案支持用戶屬性撤銷但不支持多關(guān)鍵詞檢索，且屬性撤銷時需要同時更新用戶密鑰和密文信息。

針對移動設(shè)備計(jì)算力有限的情況，文獻(xiàn)［15-17］引入加解密離線/在線的思想，離線階段提前進(jìn)行了大部分的計(jì)算工作，有效減輕了客戶端的計(jì)算負(fù)擔(dān)，但是這些方案都不支持屬性的撤銷。SUN 等［18］提出可驗(yàn)證性的基于屬性的密文檢索方案，該方案支持用戶屬性撤銷，在多對多場景下授權(quán)機(jī)構(gòu)能對服務(wù)器返回的結(jié)果進(jìn)行驗(yàn)證，但該方案存儲開銷較大且計(jì)算效率不高。孫瑾等［19］提出結(jié)果可驗(yàn)證的多關(guān)鍵詞搜索加密方案，但該方案的訪問結(jié)構(gòu)使用的是效率較低的樹形結(jié)構(gòu)。鄧志輝等［20］提出基于雙線性對的可搜索加密方案，該方案能夠抵抗外部關(guān)鍵詞猜測攻擊，但是該方案不能支持用戶的訪問控制，也缺少實(shí)驗(yàn)進(jìn)行論證。

2 預(yù)備知識

2.1 雙線性映射及困難性假設(shè)

定義1（雙線性映射）G、GT表示階為素數(shù)p的乘法循環(huán)群，g∈G滿足下述要求，則其為有效的雙線性映射。

1）雙線性：?h1,h2∈G,a,b∈Zp,=e(h1,h2)ab。

2）非退化性：e(h1,h2)≠1。

3）可計(jì)算性：?h1,h2∈G，存在多項(xiàng)式時間計(jì)算e(h1,h2)。

定義2（q-DPBDHE 假設(shè)）令G、GT表示階為素數(shù)p的乘法循環(huán)群，g∈G為生成元，e：G×G→GT為有效的雙線性映射，隨機(jī)選取a,s∈Zp,T∈GT。給定元組：

q-DPBDHE 假設(shè)是指不存在多項(xiàng)式時間的算法以不可忽略的優(yōu)勢判定是否成立，其中T為GT中隨機(jī)元素，q-DPBDHE假設(shè)最早在文獻(xiàn)［21］給出定義和安全性證明。

2.2 訪問結(jié)構(gòu)

定義3（訪問結(jié)構(gòu)）令P={P1,P2,…,Pn}為用戶集合，訪問結(jié)構(gòu)A?2P是集合2P的一個非空子集。如果對于任意集合B和C，B∈A且B?C，有C?A，那么稱A是單調(diào)的訪問結(jié)構(gòu)。訪問結(jié)構(gòu)A中的集合稱為授權(quán)集合，否則稱為非授權(quán)集合。

2.3 線性秘密共享方案

若一組參與方P上的線性秘密共享方案Π 滿足下述條件，那么它是線性的。

1）每個參與方的線性共享份構(gòu)成一個Zp上的向量。

2）對于秘密共享方案Π，存在一個秘密共享份生成矩陣Ml×n，函數(shù)ρ：{1,2,…,l}→Pi將Ml×n中的第i行映射到參與方的集合中。令s∈Zp表示待共享的秘密值，隨機(jī)選取組成向量v=(s,r2,…,rn)。MvT表示秘密值s的l個共享份，其中λi=(MvT)i表示第i個共享份，將λi分配給參與方ρ(i)。

秘密共享方案滿足線性重構(gòu)性質(zhì)：令Π 表示一個線性秘密共享方案，S為其一個授權(quán)集，集合I定義為I：{i：ρ(i)∈S}?{1,2,…,l}，存在多 項(xiàng)式時 間算法計(jì)算{ωi∈Zp}i∈I，使對Π 上的有效共享份成立。

2.4 系統(tǒng)模型

系統(tǒng)中包括云服務(wù)器（Cloud Server，CS）、授權(quán)機(jī)構(gòu)（Authorized Authority，AA）、數(shù)據(jù)擁有者（Data Owner，DO）、數(shù)據(jù)使用者（Data User，DU）4 類實(shí)體。

1）CS：儲存加密的文件并提供關(guān)鍵詞的搜索服務(wù)。根據(jù)授權(quán)機(jī)構(gòu)的重加密密鑰，對加密的索引進(jìn)行重加密，以此達(dá)到更新訪問權(quán)限的目的。同文獻(xiàn)［14］的方案，假定云服務(wù)器誠實(shí)且好奇，即云服務(wù)器會誠實(shí)地執(zhí)行用戶提交的任務(wù)，但是可能會通過用戶提交的數(shù)據(jù)推斷出額外的信息。

2）AA：負(fù)責(zé)系統(tǒng)建立、用戶密鑰生成、根據(jù)訪問策略更新重加密密鑰、撤銷用戶屬性等工作，AA 是可信的第三方機(jī)構(gòu)。

3）DO：首先將文件加密，從該文件中提取m個關(guān)鍵詞，根據(jù)這些關(guān)鍵詞使用下文的索引生成算法生成索引，然后使用對稱加密算法將文件加密，最后將密態(tài)文件和索引一起放至CS 存儲，提供CS 原始數(shù)據(jù)以進(jìn)行搜索操作。

4）DU：根據(jù)需求向CS 發(fā)起關(guān)鍵詞搜索請求，并獲得相應(yīng)的檢索結(jié)果。

本文方案的工作流程如圖1 所示。

圖1 本文方案工作流程Fig.1 Working procedure of the proposed scheme

2.5 算法描述

一個支持用戶屬性撤銷的多關(guān)鍵詞搜索方案由以下6 個算法組成：

1）Setup(1λ,U)→(PK,MSK)。為系統(tǒng)建立算法，由AA 運(yùn)行，輸入安全參數(shù)λ和系統(tǒng)總體屬性集合U，輸出公鑰PK 和主密鑰MSK。

2）KeyGen(PK,MSK,S)→SK。算法輸 入公鑰PK、主密鑰和用戶屬性集S，輸出用戶的個人私鑰SK。

3）Index(PK,MSK,D,(M,ρ))→INDEX。算法輸入公鑰PK、用戶主密鑰MSK、文檔集合D和訪問結(jié)構(gòu)(M,ρ)，輸出加密索引INDEX。

4）Trapdoor(PK,SK,SKW)→TD。算法輸入公鑰PK、用戶私鑰SK 和查詢關(guān)鍵詞集合SKW，輸出查詢陷門TD。

5）ReEnc(INDEX,RK)→INDEX'。算法輸入加密索引INDEX 和重加密密鑰RK，輸出重加密索引INDEX'。

6）Search(INDEX',TD)→SR。算法輸入重加密索引INDEX'和查詢陷門TD，輸出搜索結(jié)果SR。

2.6 安全模型

本文通過敵手A 和挑戰(zhàn)者C 之間的交互式攻擊游戲，給出本文方案的選擇關(guān)鍵詞攻擊下不可區(qū)分性（IND-CKA）安全模型。

初始化敵手A 提交待挑戰(zhàn)的訪問結(jié)構(gòu)(M*,ρ*)給挑戰(zhàn)者C。

系統(tǒng)建立挑戰(zhàn)者C 運(yùn)行系統(tǒng)建立算法，將生成的公鑰PK 和系統(tǒng)重加密密鑰RK 發(fā)送給敵手A。

階段1敵手A 發(fā)起以下詢問。密鑰詢問：敵手A 選取屬性集合S={S1,S2,…,Sn}，其中S不滿足訪問結(jié)構(gòu)(M*,ρ*)，挑戰(zhàn)者C根據(jù)A提交的S運(yùn)行密鑰生成算法，將生成的密鑰SK 發(fā)送給敵手A。陷門詢問：敵手A 向挑戰(zhàn)者C 詢問關(guān)鍵詞集合SKW 的陷門，C 將SKW 添加到關(guān)鍵詞列表LSKW中，C 生成SKW的陷門返回給A。

挑戰(zhàn)A 選擇2 個待挑戰(zhàn)的關(guān)鍵詞集合KW0、KW1，將其發(fā)送給C，要求LSKW中沒有(KW0KW1)∪(KW1KW0)中的任何關(guān)鍵詞子集。C 隨機(jī)選擇β∈{0,1}，生成挑戰(zhàn)索引indexKWβ。

階段2A 重復(fù)階段1 發(fā)起的詢問。要求在密鑰詢問過程中，S不滿足訪問結(jié)構(gòu)(M*,ρ*)，在陷門詢問過程中，不能詢問(KW0KW1)∪(KW1KW0)中任何關(guān)鍵詞子集的陷門。

猜測A 輸出對β的猜測β'，如果β=β'，則A 贏下這個游戲，A 在游戲中獲勝的優(yōu)勢被定義為

定義4如果任何多項(xiàng)式時間的A 以可以忽略的優(yōu)勢贏得以下安全游戲，則本文提出的基于屬性加密支持用戶屬性撤銷的多關(guān)鍵詞搜索方案是IND-CKA 安全的。

3 方案構(gòu)造

3.1 本文方案具體構(gòu)造

本文方案使用的部分符號描述如表1 所示。

表1 符號定義Table 1 Notations definition

本文方案具體構(gòu)造如下：

1）Setup(1λ,U)→(PK,MSK)。該算法 輸入安 全參數(shù)λ，設(shè)G是階數(shù)為素數(shù)p的循環(huán)群，g為其生成元，e：G×G→GT表示一個雙線性映射。首先AA 隨機(jī)選取α,a,b∈作為用戶的主密鑰MSK。U是系統(tǒng)的全體屬性集合，對于i∈U，AA 隨機(jī)選取fi,di∈，隨后計(jì)算出RK。算法輸出公共參數(shù)PK、主密鑰MSK 和重加密密鑰RK，如式（1）所示：

2）KeyGen(PK,MSK,S)→SK。該算法為用戶的秘鑰生成算法，由AA 運(yùn)行。算法輸入公共參數(shù)PK、主密鑰MSK 和用戶的屬性集合S。AA 隨機(jī)選取t∈，然后計(jì)算出K=gα gat和L=gt。對于x∈S，計(jì)算Kx=。算法輸出用戶私鑰SK={K,L,Kx}，如式（2）所示：

3）Index(PK,MSK,D,(M,ρ))→INDEX。該算法為索引的生成算法，由DO 運(yùn)行。輸入公共參數(shù)PK、主密鑰MSK、文件集合D=(d1,d2,…,dp)以及訪問結(jié)構(gòu) (M,ρ)。Ml×n為秘密生成矩陣，函數(shù)ρ：{1,2,…,l}→Pi將矩陣Ml×n中的第i行映射到參與方的集合中。DO 隨機(jī)選取向量v=(s,y2,…,yn)∈Zp，其中s為秘密分享值。對于i∈[1,l]，計(jì) 算λi=v.Mi。對于j∈[1,n]，DO 提取每個文件dj的m個關(guān)鍵詞，假設(shè)單個文件的關(guān)鍵詞集合KW={KW1,KW2,…,KWm}，構(gòu) 造m級多項(xiàng) 式 ：f(x)=d(x-H(KW1))(x-H(KW2))…(x-H(KWm))+s=am xm+am-1xm-1+…+a1x1+a0，aj對應(yīng)為m級多項(xiàng)式的系數(shù)。DO 隨機(jī)選取r1,r2,…,rl∈Zp，為每個 文件構(gòu) 造索引 項(xiàng)indexk={(Ml×n,ρ),C,C',{Ci,Di|i∈[1,U]},{Ej|j∈[0,m]}}，如 式（3）所 示。算法輸出加密索引INDEX={indexk|k∈[1,p]}。

4）Trapdoor(PK,SK,SKW)→TD。該階段為數(shù)據(jù)使用者的查詢階段，H：{0,1}*→G是一個抗碰撞的哈希函數(shù)。假設(shè)待查詢的關(guān)鍵詞集合為：SKW={SKW1,SKW2,…,SKWm'}（m'為查詢 關(guān)鍵詞的數(shù)量）。數(shù)據(jù)使用者分別計(jì)算K'和Fi|m'i=0，算法輸出關(guān)鍵詞的搜索陷門TD=(K',{Fi}m'i=0)，如式（4）所示：

5）ReEnc(INDEX,RK)→INDEX'。該階段為授權(quán)機(jī)構(gòu)根據(jù)數(shù)據(jù)使用者的屬性對索引的重加密階段。對于訪問結(jié)構(gòu)(Ml×n,ρ)，i∈[1,l]，如果ρ(i)∈S，則授權(quán)機(jī)構(gòu)根據(jù)重加密密鑰RK 計(jì)算如果ρ(i)?S，那么Di=D'i。算法輸出INDEX'={index'k|k∈[1,p]}。

6）Search(INDEX',TD)→SR。該階段為云服務(wù)器的搜索階段，在接收到數(shù)據(jù)使用者的搜索陷門TD后，云服務(wù)器首先檢查數(shù)據(jù)使用者的屬性集合S是否滿足數(shù)據(jù)擁有者制定的訪問結(jié)構(gòu)(Ml×n,ρ)，滿足時繼續(xù)執(zhí)行以下操作，否則返回⊥。

（1）令I(lǐng)={I：ρ(i)∈S}表示滿足訪問結(jié)構(gòu)的最小屬性集合，云服務(wù)器按照式（5）分別計(jì)算T1、T2、T3，其中

（2）驗(yàn)證等式T2=T1T3是否成立，若成立，則所檢索的文件包含用戶查詢的關(guān)鍵詞，若不成立，則該文件不是用戶檢索的文件。

3.2 方案正確性

本節(jié)從以下2 個方面對方案的正確性進(jìn)行論述：只有當(dāng)用戶的屬性集滿足數(shù)據(jù)擁有者構(gòu)造索引時所嵌入索引的訪問策略，則云服務(wù)器檢索行為才會繼續(xù)，否則停止檢索協(xié)議；只有當(dāng)數(shù)據(jù)使用者選取的多個關(guān)鍵詞都在數(shù)據(jù)擁有者設(shè)置的關(guān)鍵詞集合內(nèi)，才會返回正確的檢索結(jié)果，否則返回⊥。

1）訪問控制。根據(jù)線性共享方案的線性重構(gòu)性質(zhì)，若檢索用戶的屬性集合滿足嵌入密態(tài)索引INDEX的訪問策略，秘密值s能由有效的共享份λi重構(gòu)，即成立，否則秘密值s不能由共享份恢復(fù)。T1的值計(jì)算如下：

2）關(guān)鍵詞檢索。根據(jù)索引構(gòu)造的多項(xiàng)式f(x)=d(x-H(KW1))(x-H(KW2))…(x-H(KWm))+s。若 數(shù)據(jù)使用者選取的關(guān)鍵詞SKW={SKW1,SKW2,…,SKWm'}都在數(shù)據(jù)擁有者設(shè)置的關(guān)鍵詞集合KW={KW1,KW2,…,KWm}內(nèi)，則多項(xiàng)式f(x)的值才為s。T3的值計(jì)算如下：

從以上推導(dǎo)的結(jié)果可知：T1=e(g,g)ats，T3=e(g,g)αse(g,g)bs，所以T1T3=e(g,g)αse(g,g)atse(g,g)bs。

故本方案是正確的。

4 安全性分析與證明

本文方案實(shí)現(xiàn)屬性撤銷的步驟如下：

1）授權(quán)中心將撤銷的用戶屬性θ∈S發(fā)送給云服務(wù)器。

2）根據(jù)撤銷信息，云服務(wù)器更新用戶的屬性集合。

3）當(dāng)用戶對存儲在云服務(wù)器上的文件進(jìn)行關(guān)鍵詞搜索時，云服務(wù)器會根據(jù)用戶屬性集合運(yùn)用重加密算法對索引進(jìn)行重加密，最后再對重加密的索引進(jìn)行搜索。

下文證明提出的方案滿足陷門不可偽造性和關(guān)鍵詞隱私性。

陷門不可偽造性：當(dāng)攻擊者要偽造陷門TD 時，需要構(gòu)造出K'和Fi這2 個陷門的組成部分，要正確構(gòu)造出K'需要獲取用戶的私鑰，或者通過已有陷門推斷出用戶私鑰b的值，但是在離散對數(shù)困難問題的假設(shè)下，攻擊者無法求解出b的值。

索引隱私性：如果q-DBDHE 假設(shè)成立，并且挑戰(zhàn)矩陣M*的大小為l*×n*，其中l(wèi)*×n*≤q，則該方案滿足選擇模型下的IND-CKA 安全性。

證明假設(shè)本文方案在IND-CKA 安全游戲中是不安全的，那么存在一個多項(xiàng)式時間敵手A 能以不可忽略的優(yōu)勢贏得安全游戲，從而本文方案能構(gòu)造出一個多項(xiàng)式時間的仿真器S 利用A 攻破q-DBDHE假設(shè)。

初始化仿真器S 接收q-DBDHE 挑戰(zhàn)向量y和T，敵手A 將待挑戰(zhàn)的訪問結(jié)構(gòu)(M*,ρ*)和x*提交給仿真器S，其中M*有l(wèi)*行n*列，存在i使得ρ*(i)=x*。

系統(tǒng)建立 仿真器S 由以下步驟生成公共參數(shù)PK，仿真器S 隨機(jī)選 取α'∈Zp，令α=α'+aq+1，則。對于屬性1≤x≤U，S 隨機(jī)選取值zx，令X表示使得ρ*(i)=x所有i的集合，若ρ*(i)=x，仿真器S計(jì)算否則仿真器S 將公開參數(shù)PK=(g,e(g,g)α,ga,F1,F2,…,FU)發(fā)送給敵手。

階段1（密鑰詢問）敵手A 提交屬性集，其中該屬性集不滿足訪問結(jié)構(gòu)M*。首先S 隨機(jī)選取r,rk1,…,rkU∈Zp，w=(w1,w2,…,wn*)∈Zp，其 中w1=-1，對于所有使得ρ(i)∈S的i的集合，有令t為t=r+w1aq+w2aq-1+…+wn*aq-n*+1，有L=然后仿真器S計(jì)算K=如果不存在i使得ρ*(i)=x，則否則 存在i使得ρ*(i)=x，設(shè)X為使ρ*(i)=x成立的所有i的集合，計(jì)算：

陷門詢問：根據(jù)A 提交的屬性集，假設(shè)查詢的關(guān)鍵詞集合SKW={SKW1,SKW2,…,SKWm'}。S隨后執(zhí)行陷門生成算法Trapdoor，計(jì)算K'=K.gb，將生成的陷門TD=發(fā)送給A，將關(guān)鍵詞集合SKW 添加到列表LSKW中。

階段2階段2 與階段1 相同。但當(dāng)A 提交的屬性集合滿足(M*,ρ*)時，A 查詢的關(guān)鍵詞集合不能是集合的子集。

猜測A 輸出β'表示對隨機(jī)數(shù)β的猜測。根據(jù)敵手的猜測，如果β'=β，仿真器回答T=e(g,g)aq+1s，此時索引是有效索引，否則仿真器回答T為群GT中的一個隨機(jī)元素T∈GT，當(dāng)T為群中的一個隨機(jī)元素，關(guān)鍵詞對應(yīng)的索引是保密的，有

因此，當(dāng)多項(xiàng)式敵手以不可忽略的優(yōu)勢ε攻破方案的IND-CKA 時，則存在仿真器的優(yōu)勢 攻破q-DBDHE 假設(shè)。

5 方案分析

5.1 功能比較

表2 選取一些具有代表性的基于屬性的可搜索加密方案進(jìn)行對比。從表2 可以看出，對比方案中的文獻(xiàn)［12，18-19］均不能同時滿足表中列出的3 個功能性要求，即不能同時滿足屬性撤銷、支持多關(guān)鍵詞查詢和撤銷用戶屬性時不需要更新用戶密鑰等要求。本文方案能同時滿足以上3 個功能性要求且采用表達(dá)能力強(qiáng)的LSSS 作為訪問結(jié)構(gòu)，所以從功能性方面來比較，本文方案更占優(yōu)勢，使得本文方案更適于實(shí)際應(yīng)用。

表2 不同方案的功能對比Table 2 Function comparison of different schemes

5.2 存儲開銷比較

為便于比較，下文定義一些用于存儲開銷的符號：|G|表示在群G中元素的比特長度；|Zp|表示在域Zp中元素的比特長度；|S|表示系統(tǒng)中用戶擁有的屬性個數(shù)；|N|表示系統(tǒng)中總的屬性數(shù)量；m表示數(shù)據(jù)擁有者提取的關(guān)鍵詞數(shù)量；t為用戶提交的關(guān)鍵詞數(shù)量。表3 給出了存儲開銷對比，從表3 可以看出，本文方案在涉及客戶端操作的陷門生成算法的存儲開銷是對比方案中最小的，其能有效減輕通信帶寬。

表3 不同方案存儲開銷對比Table 3 Comparison of storage overhead of different schemes

5.3 計(jì)算開銷比較

群G和域Zp中的指數(shù)運(yùn)算和配對運(yùn)算比乘法運(yùn)算和哈更加耗時，所以，以下的分析比較只考慮指數(shù)運(yùn)算E和配對運(yùn)算P。從表4 可以看出，基本上所有方案算法的計(jì)算開銷與系統(tǒng)的屬性數(shù)量或者與用戶的屬性數(shù)量成線性關(guān)系，但當(dāng)t?|S|或者t?|N|時，也就是在系統(tǒng)屬性數(shù)量和用戶屬性數(shù)量固定的條件下，當(dāng)用戶提交的關(guān)鍵詞數(shù)量小于這兩者數(shù)量時，本文方案的陷門生成算法的計(jì)算效率更高。

表4 不同方案的計(jì)算開銷對比Table 4 Comparison of calculation overhead of different schemes

5.4 實(shí)驗(yàn)仿真

本文實(shí)驗(yàn)的硬件條件為：Intel Core i3-2348M 2.3 GHz @ CPU，4 GB RAM。操作系統(tǒng)為64 bit Ubuntu 18.04.3 LTS。實(shí)驗(yàn)基于Charm 架構(gòu)，選取SS512 橢圓曲線。本文選取系統(tǒng)總體屬性數(shù)量和用戶屬性數(shù)量為|N|=|S|∈[10,60]。

圖2（a）～圖2（c）分別描述了系統(tǒng)建立、密鑰生成和陷門生成的時間開銷。如圖2（a）所示，通過對比3 個方案可以看出，文獻(xiàn)［12］方案中系統(tǒng)建立算法的計(jì)算開銷為2E+P，是一個常數(shù)，而其他2 個方案的開銷隨著系統(tǒng)屬性個數(shù)N的增加而增長，本文方案的系統(tǒng)建立算法在對比方案中處于中等水平。如圖2（b）所示，3 個方案密鑰生成算法的時間代價都與系統(tǒng)屬性數(shù)量成線性增長關(guān)系，但是本文方案的時間開銷增長最慢，所以對于密鑰生成算法而言，本文方案效率是最高的。圖2（c）描述了陷門生成算法，本文方案的陷門生成只與用戶提交的關(guān)鍵詞數(shù)量相關(guān)。在給定關(guān)鍵詞數(shù)量t=20 時，本文方案陷門生成的時間開銷是一個常數(shù)，在t

圖2 不同方案時間開銷對比Fig.2 Comparison of time overhead of different schemes

6 結(jié)束語

本文提出一個基于屬性的可搜索加密方案。采用LSSS 作為訪問結(jié)構(gòu)，提供多關(guān)鍵詞搜索和用戶屬性撤銷的功能，適用于云存儲中數(shù)據(jù)的搜索與共享，并從陷門不可偽造性和關(guān)鍵詞隱私性兩方面對本文方案進(jìn)行安全性分析，從存儲開銷和計(jì)算開銷兩方面與現(xiàn)有方案進(jìn)行對比。理論分析和實(shí)驗(yàn)結(jié)果表明，該方案具有安全、高效、靈活等特點(diǎn)。但是本文方案并不支持用戶對搜索結(jié)果的正確性進(jìn)行驗(yàn)證，并且不能隱藏同為敏感信息的訪問策略，因此設(shè)計(jì)結(jié)果可驗(yàn)證、隱藏訪問策略、可動態(tài)更新的基于屬性加密的關(guān)鍵詞搜索方案將是下一步的工作。