選擇性隱藏樹型訪問結構的CP-ABE方案

韓舒艷,努爾買買提·黑力力

(新疆大學 數學與系統科學學院,烏魯木齊 830046)

0 概述

云存儲作為一種網絡在線存儲模式,在提供數據存儲便利的同時,其引發的數據安全問題也給數據所有者帶來困擾。由于云存儲數據存放在由第三方托管的多臺虛擬服務器上,虛擬服務器可能向以進行商業欺騙和敲詐等活動謀取利益的未授權用戶提供數據,因此數據所有者通常將數據加密后存儲在云上,只有授權用戶才能訪問。Fuzzy-IBE[1]、KP-ABE[2]和密文策略屬性基加密(Ciphertext Policy Attribute Based Encryption,CP-ABE)[3]是數據加密的常用方案。在CP-ABE方案中,由于數據所有者擁有訪問控制主動權,能較好地解決云上安全存儲問題,因此該方案適用于云服務器。

當前在多數CP-ABE方案[4-6]中,訪問結構以明文形式嵌入到密文中,由于其可能含有敏感信息,因此需要被隱藏。文獻[7]提出兩種隱藏訪問結構CP-ABE方案,通過具有多值屬性的“與”門結構,實現保密消息和訪問結構功能。文獻[8]提出隱藏訪問結構CP-ABE方案并證明該方案在標準模型下絕對安全。文獻[9]在解密運算前提出匹配技術,減少不符合訪問結構用戶在解密過程中的開銷。文獻[7-9]均基于“與”門提出方案訪問結構。文獻[10]提出基于訪問樹的策略隱藏屬性加密方案并論證該方案具有安全性。文獻[11]提出表達能力較強的素數階群中隱藏屬性值CP-ABE方案且指出其安全類型為選擇性安全。文獻[12]提出素數階群中部分隱藏樹型訪問結構的CP-ABE方案,該方案經驗證完全安全。

本文在文獻[11,13]的基礎上,提出一種選擇性隱藏樹型訪問結構的CP-ABE方案[14-16]。采用互信息(Mutual Information,MI)方法提取敏感屬性,對含有原始屬性集信息的部分屬性進行隱藏,針對屬性隱藏導致用戶對自己解密能力無法提前判斷的情形,利用以最少匹配代價判斷解密能力的方法,使無解密能力的用戶盡早放棄解密。

1 敏感屬性提取

1.1 訪問結構

本文使用的樹型訪問結構T內部節點支持“與”(AND)門、“或”(OR)門和“門限”(tofn)門。假設數據所有者ua的數據T中全體屬性集為A={a1,a2,…,an}。訪問數據的用戶ut屬性集表示為S′。ua制定T,利用互信息方法篩選出包含原始屬性集A中絕大部分或者全部信息量的部分屬性,隱藏部分屬性,再將部分隱藏的T和密文一起分享到云服務器。ut根據未隱藏屬性不能推測出加密信息。

隱藏部分屬性的訪問樹如圖1所示。假設有一份醫療數據為(住院號:005 AND醫院:醫院A)OR(2 of{醫院:醫院B;醫生:心臟病專家;醫院科室:心臟病內科}),如果不隱藏屬性,則從T中可直接推測出醫院A住院號為005的患者有心臟病。但是該患者不愿公開病情,因此醫院在存儲該患者信息時,選出并隱藏“心臟病專家”和“心內科”這兩項包含較多敏感信息量的屬性,然后分享到云端。訪問者由隱藏部分屬性的訪問樹不能推測出患者有心臟病,從而達到保護患者病史隱私目的。從信息熵角度,屬性部分隱藏訪問樹與屬性完全隱藏訪問樹的保密效果相同。

圖1 隱藏部分屬性的訪問樹

1.2 敏感屬性提取算法

本文方案對T中屬性進行選擇性隱藏,選擇哪些屬性隱藏是重點考慮的問題。如果一個T中有n個屬性,則選擇性隱藏方案共有2n種,其中包括不隱藏全體屬性和隱藏全體屬性2種情形,本文著重考慮隱藏屬性個數0

選擇屬性隱藏需要客觀依據,本文借助特征提取方法選取需隱藏的屬性。目前,常用特征提取方法主要包括互信息[17]、期望交叉熵、信息增益、詞頻法、文本證據權、幾率比和卡方統計量等方法[18-20]。其中,互信息方法應用廣泛[21-23],本文采用該方法來選擇敏感屬性。

本文屬性提取過程從空集S開始,采用步進方式,每次選擇1個屬性。令:

(1)

(2)

第1次屬性選擇a1=al1,在只選擇1個屬性的情況下,a1=al1提供信息量最多。假設U為當前未被選擇的屬性集合,Sm-1為已選m-1個屬性組成的集合,相對于U中其他屬性,第m個屬性am與整個屬性集合A最大程度相關,同時與Sm-1中已選屬性最小程度冗余。根據無監督最小冗余-最大相關標準(UmRMR),設:

(3)

其中,UmRMR(ai)表示為:

(4)

相關度表示為:

(5)

冗余度表示為:

Red(ai;at)=Rel(at)-Rel(at|ai)

(6)

條件相關度表示為:

(7)

其中,第m個屬性選擇為am=alm。在選擇后續屬性時,采用類似方式逐個進行選擇。

定義1(敏感屬性) 定義訪問結構中屬性ai為敏感屬性,屬性之間互信息存在以下關系式:

(8)

其中,k為數據所有者ua規定的閾值。如果屬性之間互信息滿足式(8),則敏感屬性選取算法過程如下:

1)初始化:原始屬性集A={a1,a2,…,an},設定初始候選集S=?,Aδ為被選所有敏感屬性組成的集合。

2)預先計算:對于?ai,at∈A,計算信息熵H(ai)、互信息I(ai;at)、屬性ai的相關度Rel(ai)和冗余度Red(ai;at)。

3)通過式(1)找到屬性al1且U=Ual1,S={al1}。

4)根據式(3)找到屬性alm且U=Ualm,S=S∪{alm}。

6)輸出T中的Aδ。

經算法篩選出的敏感屬性集合{a1,a2,…,ad}記為Aδ,其中am=alm,m=1,2,…,d(d

2 用戶屬性快速匹配

屬性部分隱藏導致ut在解密前無法確定自己是否有解密能力,因此,在解密操作前,如果ut能提前判斷自己沒有解密能力,則其不再進行后續解密操作。本文結合訪問樹分析對用戶屬性進行快速匹配,以最少匹配代價判斷自己的解密能力,使無解密能力的ut盡早放棄解密。

定義2(極小集) 滿足T的最小屬性集合為極小集,其特點包括:1)極小集交集非空;2)極小集交集為空集。

定義3(屬性區分(Attribute Discrimination,AD)) 定義屬性在給定的極小集中出現頻次為屬性區分度。

定義4(優先匹配次序) 給定的訪問樹T中,設?a1,a2∈A,假設這兩個屬性對決定ut能否解密有必然關系,若AD(a1)>AD(a2),則優先匹配次序定義為a1?a2,其中,AD(a1)和AD(a2)分別表示a1和a2的區分度。

優先匹配次序在T的屬性匹配過程有以下性質:若ut使用優先匹配次序來匹配自己所擁有的屬性,則其總匹配次數最少,即ut能夠最早發現自己是否有繼續解密的必要。

對該性質分析如下:

特別地,當t=n時,滿足T的極小集S1={a1,a2,…,an}唯一。此時ut需將自身屬性與S1中屬性進行Hash值配對,且必須擁有S1中每個屬性才能解密。

圖2 極小集交集非空的訪問樹

2)若極小集交集為空集,對于極小集中沒有隱藏的屬性,ut通過目測部分了解自己是否滿足T,但不一定完全了解自己能否滿足T,這時ut解密能力由隱藏屬性決定。若隱藏屬性和公開屬性的區分度相同,則為減少計算利用公開屬性最大限度地排除部分極小集。若都是隱藏屬性,則根據T節點特征與其Hash值,先找出區分度最大的屬性以排除最多極小集,然后在剩余隱藏屬性中找出區分度最大的屬性,每次按照最大區分度方式尋找。將ut首先判斷的屬性假設為a1,理論上需要平均匹配(|S′|+1)/2次,若ut屬性中沒有a1,則直接排除有a1的極小集,由于極小集減少,因此ut是否有解密能力的不確定性也最大限度減少。而因為a1最先匹配,即所在的極小集最多,所以a1可在一次屬性匹配過程中可最大限度地過濾掉不符合條件的極小集。若ut經Hash值計算判斷自己屬性中有a1,則將a3看成公開屬性,余下極小集中最大區分度判斷屬性假設為a2,若沒有a2,則ut在排除完沒有a1極小集中再排除沒有a2的極小集,其是否有解密能力的不確定性在前者基礎上再次最大限度減少,從第2次匹配中可以看出,符合條件的極小集在進行下次匹配時其優先匹配次序將受到前一次匹配結果影響。以此類推,一直到ut確認自身有或沒有解密能力。

極小集交集為空的訪問樹如圖3所示。其中,極小集分別為S1={a1,a3,a4}、S2={a1,a3,a5}、S3={a1,a4,a5}、S4={a2,a3,a4}、S5={a2,a3,a5}、S6={a2,a4,a5}和S7={a6,a7},屬性a3、a4、a5在極小集中出現4次,a1、a2出現2次,a6、a7出現1次,則優先匹配a3、a4、a5。假設其中隱藏屬性是a1、a4、a7,若隱藏屬性和公開屬性的區分度相同,則為減少計算,利用公開屬性最大限度地排除部分極小集,由于a3、a4、a5區分度相同,ut首先判斷a3,若其屬性中沒有a3,則直接排除極小集S1、S2、S4、S5,ut是否有解密能力的不確定性減少57%;若ut經Hash值計算判斷自己屬性中有a3,則將a3看成公開屬性。在余下的極小集中,a4、a5區分度相同,但a4隱藏,因此再判斷a5,若ut屬性中沒有a5,則排除極小集S3、S6,ut是否有解密能力的不確定性在前者基礎上又減少67%,然后判斷用戶屬性中是否存在a6和a7,其中a6通過目測可得知。對于a7,ut理論上只需平均匹配(|S′|+1)/2次便可得知自己是否擁有此屬性。若每次匹配次數最少,則整體匹配次數最少,即為最優匹配次序。采用優先匹配次序是為避免用戶耗費時間進行無效計算。

圖3 極小集交集為空的訪問樹

3 方案建立

3.1 相關定義

定義5(單調訪問結構) 設{p1,p2,…,pn}是一個集合,訪問結構A?2{p1,p2,…,pn}{?}是一個非空子集合。對?B,C,如果B∈A且B?C,則C∈A,那么A單調。

3.2 安全模型

以下通過挑戰者和敵手之間交互性游戲建立策略部分隱藏CP-ABE方案的安全模型,該游戲流程如下:

1)初始化:挑戰者運行初始化算法Setup(λ)生成公鑰PK和主密鑰MSK,并將公共參數發送給敵手。

2)階段1:敵手適應性地向挑戰者詢問屬性集A的密鑰,可選定一些屬性集γ1,γ2,…,γq進行密鑰查詢。挑戰者運行算法KeyGen生成密鑰SKut并發送給敵手,敵手可重復多次詢問密鑰。

3)挑戰:敵手向挑戰者提交2個等長的消息m0和m1,并訪問樹T0和T1(要求階段1查詢過的屬性集γ1,γ2,…,γq均不滿足T0和T1),挑戰者拋擲1枚公平硬幣b∈{0,1},計算c*=Encrypt(PK,mb,Tb),并將c*發送給敵手作為挑戰密文。

4)階段2:重復執行階段1,但要求屬性集γq+1,γq+2,…,γl不滿足待挑戰的訪問樹。

5)猜測:敵手輸出對密文c*的一個猜測值b′∈{0,1}。如果b′=b,則稱敵手贏得這個游戲。敵手在上述游戲中獲勝的優勢定義為:

(9)

定義8如果在任意多項式時間內,敵手贏得安全游戲的優勢可忽略,那么該部分策略隱藏CP-ABE方案安全。

3.3 系統結構描述

數據分享系統結構如圖4所示,具體如下:

1)密鑰生成中心(Key Generation Center,KGC):對系統生成公共和秘密參數,假設KGC為半可信。KGC執行其他實體分配的合法任務,但其可能試圖獲取加密數據。

2)云服務器:提供數據存儲和共享服務,實現部分解密。

3)數據所有者ua:擁有數據的用戶將自己數據共享到云服務器。ua制定T,并利用MI算法篩選出T中敏感屬性。在上傳數據前根據T、KGC生成的公鑰PKK和云服務器公鑰PKS加密數據。

4)用戶ut:訪問數據的實體[24],KGC和云服務器根據用戶屬性生成用戶密鑰,若ut屬性滿足加密數據中的T,則其能夠解密密文并獲得數據M。

圖4 數據分享系統結構

3.4 算法結構

本文在完全隱藏訪問結構方案[25]的基礎上,提出選擇性隱藏樹型訪問結構CP-ABE方案,該方案由Setup、KeyGen、Encryption、Decrypt等4個算法組成。上述算法步驟具體如下:

1)Setup(λ)→(PKK,MKK),(PKS,MKS):該算法由KGC進行。算法輸入安全參數λ,輸出KGC公鑰對PKK和密鑰對MKK以及云服務器的公鑰對PKS和密鑰對MKS。

2)KeyGen(MKK,A)→SKut:KGC將MKK和屬性集合A作為輸入,為ut輸出密鑰SKut。

3)Encryption(M,T,PKK,PKS)→CT:ua使用PKK、PKS和T對數據M進行加密,并輸出密文CT。

4)Decrypt(CT,SKut)→M:該算法由云服務器和ut來執行,以CT和SKut作為輸入,ut對云服務器部分解密的CT′用自己密鑰再次解密,并且輸出明文M。

3.5 方案設計

3.5.1 系統初始化

KGC選擇階為素數p的循環群G0,g為G0的一個生成元。選擇Hash函數H:{0,1}*→G0,H1:G1→{0,1}lb p,生成公共參數(G0,g,H,H1)。

3.5.2 密鑰生成

SKut=(D=g(α+rt)/β,?aj∈A,ai∈Aδ:Dj=

(10)

3.5.3 加密過程

(11)

為避免不必要的Hash配對,若ut花最小代價能判斷出自己沒有解密能力,則ut就不用去嘗試參與后續解密過程,這樣會減少ut與云服務器之間不必要的計算,從而降低時間成本。由于策略部分隱藏導致ut可能無法知道自己是否可以解密密文,針對因屬性部分隱藏導致ut對數據解密能力無法提前判斷的情況,本文提出以最少匹配代價判斷自己解密能力的方法,使無解密能力的ut盡早放棄嘗試解密。若此ut有解密能力,則繼續后續解密操作。

3.5.4 解密過程

(12)

否則,有DecryptNode(CT,SKut,x)=⊥。

如果x為非葉子節點,則考慮遞歸情況,對于節點x所有孩子節點z,令Fz=DecryptNode(CT,SKut,z)。假設Sx為孩子節點z集合,使Fz≠⊥。該算法計算如下:

(13)

查詢算法首先調用T根節點R上的函數。如果ut滿足T,則云服務器運行DecryptNode(CT,SKut,R)=e(g,g)rtτs。

ut從云服務器得到密文CT′后,用自己密鑰對密文進行解密。解密過程如式(14)所示,最終輸出M。

(14)

4 方案分析

4.1 安全性分析

在CP-ABE方案中,秘密信息必須嵌入密文中而非密鑰中。若攻擊者想解密就必須恢復e(g,g)αs,則應使密文中Cx同用戶密鑰中Di相匹配,這樣雖可獲得e(g,g)αs值,但易被e(g,g)rs盲化。此外,當且僅當用戶密鑰滿足密文中訪問樹時才能求出e(g,g)rs的值。用戶合謀攻擊無效,因為盲化每個用戶密鑰的盲因子均為隨機。該方案的數據機密性、抗合謀、策略保密性與完全隱藏訪問樹方案[25]相同。

4.2 安全性證明

使用一般雙線性群模型和隨機預言機模型來論證CP-ABE方案,該方案的安全類型為選擇明文攻擊的不可區分性安全[26]。

定義9(一般雙線性群模型) 考慮加法群Fp的2個隨機編碼ψ0和ψ1,即單射ψ0,ψ1:Fp→{0,1}m,其中m>3lbp。對于i=0,1,有Gi={ψi(x):x∈Fp}。于是得到G0和G1誘導群作用的預言,以及計算非退化雙線性映射e:G0×G0→G1的預言。H為隨機預言散列函數,G0為一般雙線性群。

定理1如上述定義ψ0、ψ1、G0和G1。對于任何敵手,設q為從查詢到哈希函數預言機、群G0和G1、雙線性映射e以及與CP-ABE安全游戲交互中接收到的元素總數的一個邊界。在CP-ABE安全游戲中,敵手優勢為O(q2/p)。

以下介紹改進CP-ABE游戲模擬的符號。設g=ψ0(1)(用gx表示ψ0(x),e(g,g)y表示ψ1(y))。

在設置系統時,模擬者從Fp中隨機選擇α和β,并將其與0～p-1之間整數關聯。如果β=0,事件發生的概率為1/p,則初始化中止。將公共參數h=gβ、e(g,g)α發送給敵手。

當敵手(或模擬者)要求對任意字符串i進行H評估時,從Fp中選擇新隨機值ti,模擬者提供gti作為對H(i)的響應。

當敵手提出挑戰,發出兩條消息M0,M1∈G1并訪問樹T時,模擬者執行以下操作:1)從Fp中選擇一個隨機的s;2)使用與T相關聯的線性秘密共享方案為所有相關屬性i構造s共享λi。根據秘密共享方案施加的線性條件,λi均由Fp中隨機且一致地選擇。特別地,對于某個l值,可通過均勻獨立地選擇l隨機值μ1,μ2,…,μl來完全模擬λi′s選擇,并讓λi成為μk′s和s的固定公共線性組合。λi通常看作是上述獨立隨機變量的線性組合。

模擬者選擇一個隨機數θ∈Fp,并構造如下加密密文:

(15)

C=hs

(16)

在群G0或G1中均沒有發生這種意外沖突。對于與不同有理函數η/ξ和η′/ξ′對應的同群中任何一對查詢,只有當非零多項式ηξ′-ξη′計算結果為零時才會發生沖突。本文中ηξ′-ξη′總次數最多為5,此類沖突發生概率為O(1/p)。在聯合約束下,任何此類沖突發生概率最多為O(q2/p)。因此,可以在不發生該沖突的情況下,保持質量概率為1-O(q2/p)。

由于θ僅以e(g,g)θ形式出現,而e(g,g)θ存在于G1中,因此v或v′在θ上唯一依賴性是具有γ′θ形式的相加項,其中γ′為常數。由此推斷存在v-v′=γαs-γθ,其中γ≠0為常數。將查詢v-v′+γθ=γαs添加到敵手查詢中,且需證明敵手不能構造查詢e(g,g)γαs。

(17)

為驗證敵手查詢多項式不是γαs形式,進行如下案例分析:

案例1存在某個j∈T,使得秘密共享集合Lj={λi′:?i:(i,i′)∈T′j}不允許秘密s重建。如果存在j∈T,則sr(j)項將不會取消,因此敵手查詢多項式不是γαs形式。

4.3 部分隱藏策略

4.4 性能分析

表1為3種同是樹型訪問結構但策略隱藏情況不同方案的對比情況。其中,L0和L1分別為群G0和群G1中元素長度,t為密文相關的屬性個數,k為用戶密鑰相關的屬性個數,e為雙線性對,exp為群運算中的指數,|R|為滿足T的用戶屬性個數,d為滿足T的用戶的感屬性個數,d

表1 不同方案的性能對比

由于樹型訪問結構比LSSS矩陣更直觀,策略可表達性更強,因此本文使用樹型訪問結構。由表1可以看出,完全公開訪問樹方案[3]的密鑰長度和公鑰長度較其他兩種方案更短,但其數據安全性更低。與完全隱藏訪問策略方案[24]相比,本文方案在加密和解密過程中指數運算和雙線性對運算減少,在安全性相同情況下減少了計算量。在同是樹型訪問結構情況下,本文方案比完全公開訪問結構方案安全性更高,比完全隱藏訪問結構方案計算量更少。

5 結束語

本文從訪問策略安全性和計算效率考慮,提出一種選擇性隱藏樹型訪問結構CP-ABE方案,利用互信息方法進行屬性提取,篩選和隱藏包含原始屬性集信息的部分屬性,采用以最少匹配代價判斷解密能力的方法,使無解密能力用戶盡早放棄嘗試解密。分析結果表明,該方案與已有的完全隱藏方案具有相同保密效果,且有效減少加密和解密算法的計算量,較完全公開訪問結構方案的策略安全性更高。下一步將研究更多樣化和智能化的敏感屬性提取算法,以減小算法計算量并提高CP-ABE方案的安全性。