基于LSSS的隱藏策略屬性基加密方案

陳丹偉，湯 波

(南京郵電大學(xué) 信息安全系，江蘇 南京 210003)

0 引 言

近年來，訪問控制成為云計算研究的熱點(diǎn)問題，傳統(tǒng)的加密方法雖然能夠保護(hù)數(shù)據(jù)的隱私，但增加了系統(tǒng)對用戶細(xì)粒度訪問控制的難度。為了實現(xiàn)云環(huán)境下的細(xì)粒度訪問控制，2005年Sahai等[1]提出了基于屬性的加密體制的概念，在這種加密體制中加密者無需知道解密者的具體身份信息，而只需要掌握解密者一系列描述的屬性，然后在加密過程中用屬性定義訪問結(jié)構(gòu)對消息進(jìn)行加密，當(dāng)用戶的密鑰滿足這個訪問結(jié)構(gòu)時就可以解密該密文。

2006年，Goyal等將基于屬性的加密體制分為密文策略屬性基加密[2]和密鑰策略屬性基加密[3-7]兩種，但這些方案都未對訪問策略進(jìn)行隱藏，當(dāng)訪問策略本身就是敏感信息，同樣會泄露用戶的隱私信息。例如，在個人健康記錄系統(tǒng)中，某位患者的電子病歷只允許腦科專家訪問，那么從這條策略就能間接推斷出該患者很有可能腦部患有疾病，由此看出訪問策略同樣需要加以保護(hù)。因此，2008年 Nishide等[8]提出了一種可以隱藏部分訪問策略的加密方案，用多值屬性之間的與邏輯表示訪問策略，實現(xiàn)了同時保護(hù)消息和訪問結(jié)構(gòu)私密性的功能。2011年，Lai[9]等在合數(shù)階雙線性群的基礎(chǔ)上提出了一種隱藏訪問策略的CP-ABE方案，并證明其是完全安全的。2012年，王海斌等[10]提出一種素數(shù)階雙線性群的策略隱藏CP-ABE方案，使私鑰長度和解密算法中的雙線性配對運(yùn)算為固定值，方案中采用多值屬性與門的訪問結(jié)構(gòu)。2013年，Sreenivasa[11]等提出了一種匿名接收的CP-ABE方案，其采用與門的訪問結(jié)構(gòu)，并證明是完全安全的。2015年，宋衍等[12]提出一種基于訪問樹的策略隱藏屬性加密方案，并證明其是自適應(yīng)安全的。

以上的隱藏策略的屬性基加密方案大多采用與門或訪問樹的訪問結(jié)構(gòu)，在策略表達(dá)上有諸多限制，而LSSS矩陣在訪問策略表達(dá)上更強(qiáng)，可表達(dá)任意訪問策略，包括與門或門和門限，訪問結(jié)構(gòu)靈活。2011年，Waters[13]提出了一種基于LSSS訪問矩陣的CP-ABE方案，但方案中并沒有對訪問策略進(jìn)行隱藏。2012年，Lai等[14]提出了一種基于LSSS訪問矩陣隱藏部分訪問策略的CP-ABE方案。在借鑒上述方案的基礎(chǔ)上，文中提出一種基于LSSS隱藏訪問策略的CP-ABE方案，應(yīng)用合數(shù)階雙線性群來隱藏訪問策略，使用雙系統(tǒng)加密機(jī)制證明其安全性。

1 預(yù)備知識

本節(jié)介紹相關(guān)的基礎(chǔ)知識，包括合數(shù)階雙線性群、子群假設(shè)問題、訪問結(jié)構(gòu)以及線性秘密共享方案。

1.1 合數(shù)階雙線性群

應(yīng)用階為Q=p1p2p3的雙線性群，其中p1、p2、p3為三個不同的素數(shù)，G0和G1是兩個階為Q=p1p2p3的乘法循環(huán)群，Gpi是群G0的階為pi的子群，Gpi pj(i≠j)是群G0的階為pipj的子群。雙線性映射e:G0×G0→G1滿足如下性質(zhì)：

(1)雙線性：對于任意的u,v∈G0和a,b∈Zp，都有e(ua,vb)=e(u,v)ab。

(2)非退化性：存在g∈G0,使得e(g,g)在G1中的階為Q。

(3)可計算性:對于任意的u,v∈G0，存在一個有效的算法以計算e(u,v)。

(4)子群正交性:對?gi∈Gpi,?gj∈Gpj(i≠j),有e(gi,gj)=1。

1.2 合數(shù)階子群判定假設(shè)

應(yīng)用Lewko中的子群判定假設(shè)[15]，后面會依賴這些假設(shè)證明方案的安全性。

假設(shè)1：給定一個雙線性群生成器Φ，定義如下分布：G=(Q=p1p2p3,G0,G1,e)←Φ，g1←Gp1，Z2←Gp2，D=(G,g1,Z2)，T1←Gp1p3，T2←Gp1。

定義算法Ψ攻破假設(shè)1的優(yōu)勢為：

Adv1Φ,Ψ(λ)=

|Pr[Ψ(D,T1)=1]-Pr[Ψ(D,T2)=1]|

假設(shè)2：給定一個雙線性群生成器Φ，定義如下分布：G=(Q=p1p2p3,G0,G1,e)←Φ，g1,Z1←Gp1，g2←Gp2，Z3←Gp3，D=(G,g1,g2,Z1Z3)，T1←Gp1p3，T2←Gp1。

定義算法Ψ攻破假設(shè)2的優(yōu)勢為：

Adv2Φ,Ψ(λ)=

|Pr[Ψ(D,T1)=1]-Pr[Ψ(D,T2)=1]|

定義算法Ψ攻破假設(shè)3的優(yōu)勢為：

Adv3Φ,Ψ(λ)=

|Pr[Ψ(D,T1)=1]-Pr[Ψ(D,T2)=1]|。

定理1：如果對于假設(shè)1、2和3，算法Ψ攻破它們的優(yōu)勢是可忽略的，那么就認(rèn)為該方案是安全的。

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

設(shè){P1,P2,…,Pn}是由n個參與者組成的實體集，集合A?2{p1,p2,…,pn}，如果對于?B,C，B∈A，B?C，有C∈A，那么A就是單調(diào)的。如果集合A是{P1,P2,…,Pn}的非空子集，即A?2{p1,p2,…,pn}{?}，那么A就是一個訪問結(jié)構(gòu)，包含在A中的集合稱為授權(quán)集，不包含在A中的集合就稱為非授權(quán)集。

1.4 線性秘密共享方案

一個定義在實體集P上的線性秘密共享方案∏(LSSS)滿足以下兩點(diǎn)：

(1)所有實體的共享組成Zp上的一個向量；

(2)存在一個l×n的∏的共享矩陣M和一個從{1,2,…,l}到P的映射,隨機(jī)選取v=(s,r2,…,rn)∈Zp,s∈Zp是需要共享的秘密，那么Mv是根據(jù)∏得到的關(guān)于s的l個共享組成的向量,其中(Mv)i屬于實體ρ(i)，記作λi。

2 基于LSSS隱藏策略的CP-ABE方案

2.1 CP-ABE方案的安全模型

該系統(tǒng)的安全模型基于選擇明文攻擊，稱為選擇明文攻擊游戲(IND-CPA)，定義模型的交互步驟如下：

(1)系統(tǒng)建立：挑戰(zhàn)者運(yùn)行系統(tǒng)初始化算法，生成系統(tǒng)公鑰PK和主私鑰MSK，并將PK發(fā)送給敵手。

(2)階段1：敵手向挑戰(zhàn)者進(jìn)行屬性集{S1,…,Sq1}的私鑰詢問，挑戰(zhàn)者使用密鑰生成算法生成私鑰{SK1,…,SKq1}，然后返回給敵手。

(3)挑戰(zhàn)階段：敵手提交兩個相同長度的明文消息M0和M1以及兩個訪問結(jié)構(gòu)(M0,ρ0)和(M1,ρ1)發(fā)送給挑戰(zhàn)者。挑戰(zhàn)者拋擲一枚公平硬幣β∈{0,1}，使用訪問結(jié)構(gòu)(Mβ,ρβ)對消息Mβ進(jìn)行加密，并將密文CT發(fā)送給敵手。

(4)階段2：重復(fù)執(zhí)行階段1。

(5)猜測：敵手根據(jù)密文CT對β進(jìn)行猜測，得到預(yù)測β'。如果β'=β，則認(rèn)為敵手贏得了游戲。

攻擊者贏得上述游戲的概率為：

對于一個加密方案，如果在任意概率多項式時間內(nèi)，敵手在游戲中的優(yōu)勢是可忽略的，即其贏得游戲的概率都趨近于0，則稱該加密方案IND-CPA安全。

2.2 隱藏策略的CP-ABE方案描述

該方案主要包括四個算法：系統(tǒng)建立算法、加密算法、密鑰生成算法以及解密算法。詳細(xì)過程如下：

(1)系統(tǒng)建立算法(Setup)。

輸入：安全參數(shù)λ以及系統(tǒng)屬性個數(shù)N。

輸出：系統(tǒng)公鑰PK和主私鑰MSK。

(2)加密算法(Encryption)。

輸入：系統(tǒng)公鑰PK，待加密消息M以及LSSS對應(yīng)的(M,ρ)。

輸出：密文CT。

(3)密鑰生成算法(KeyGen)。

輸入：主私鑰MSK和用戶屬性集S。

過程：算法選擇一個隨機(jī)數(shù)t∈Zp，計算用戶的私鑰SK。

(4)解密算法(Decryption)。

輸入：密文CT以及用戶私鑰SK。

e(g1,g1)αs

然后通過密文C將明文M恢復(fù)；若S是一個非授權(quán)集，那么解密失敗。

輸出：明文M。

2.3 正確性推導(dǎo)

e(g1,g1)αs

最后通過C/e(g1,g1)αs即可恢復(fù)明文M。

2.4 策略隱藏

不難看出，上式中存在Gp2中的隨機(jī)元素，所以敵手并不能確定密文CT由哪個訪問策略加密得到，因此通過Gp2能夠?qū)崿F(xiàn)訪問策略的隱藏。

2.5 安全性證明

使用Waters等[16]提出的雙系統(tǒng)加密技術(shù)來證明本方案的安全性。由于需要借助兩個新的概念：半功能密文和半功能私鑰，所以首先給出它們的定義。

當(dāng)用戶擁有的屬性集滿足訪問結(jié)構(gòu)時，正常私鑰可以解密半功能密文，半功能私鑰可以解密正常密文，但半功能私鑰不能解密半功能密文。

文中借助一系列相鄰游戲的不可區(qū)分性來證明方案的安全性。假設(shè)敵手在一次游戲中共做了q次私鑰詢問，定義如下一些游戲：

Gamereal:這個游戲是真實的安全游戲，也就是密文和所有的私鑰都是正常的。

Game0:在這個游戲中，挑戰(zhàn)密文是半功能的，所有的私鑰是正常的。

Gamek,l:在這個游戲中，挑戰(zhàn)密文是半功能的，前k次的私鑰是半功能私鑰，剩下的私鑰都是正常的。

Gamefinal:在這個游戲中，所有的私鑰都是半功能私鑰，挑戰(zhàn)密文是對一個隨機(jī)消息加密生成的半功能密文。

引理1：如果存在一個多項式時間內(nèi)的算法Ψ在Gamereal和Game0上的優(yōu)勢滿足GamerealAdvΦ-Game0AdvΦ=ε，那么可以構(gòu)造一個多項式時間算法Ψ以ε的優(yōu)勢攻破假設(shè)1。

證明：給定假設(shè)條件D=(G,g1,Z2)。

系統(tǒng)建立：和2.2節(jié)中的系統(tǒng)建立算法一樣。

階段1：敵手A通過密鑰生成算法詢問私鑰。

階段2：重復(fù)執(zhí)行階段1。

猜測：敵手A輸出一個關(guān)于β的猜測β'。

如果T=T1∈Gp1p3，那么密文為半功能密文；如果T=T2∈Gp3，那么密文是正常密文。因此，若敵手A使GamerealAdvΦ-Game0AdvΦ=ε不可忽視，那么挑戰(zhàn)者B同樣能夠以不可忽略的優(yōu)勢區(qū)分Gp1和Gp1p3上的元素。

引理2：如果存在一個多項式時間內(nèi)的算法Ψ在Gamek-1,1和Gamek,1上的優(yōu)勢滿足Gamek-1,1AdvΦ-Gamek,1AdvΦ=ε，那么可以構(gòu)造一個多項式時間算法Ψ以ε的優(yōu)勢攻破假設(shè)2。

證明：給定假設(shè)條件D=(G,g1,g2,Z1Z3)。

系統(tǒng)建立：和2.2節(jié)中的系統(tǒng)建立算法一樣。

階段2：重復(fù)執(zhí)行階段1。

猜測：敵手A輸出一個關(guān)于β的猜測β'。

如果T∈Gp1，那么密鑰為正常密鑰，進(jìn)行的游戲是Gamek-1,1；如果T∈Gp1p3，那么密鑰為半功能密鑰，進(jìn)行的游戲是Gamek,1。因此，若敵手A使Gamek-1,1AdvΦ-Gamek,1AdvΦ=ε不可忽視，那么挑戰(zhàn)者B同樣能夠以不可忽略的優(yōu)勢區(qū)分Gp1和Gp1p3上的元素。

引理3：如果存在一個多項式時間內(nèi)的算法Ψ在Gameq,1和Gamefinal上的優(yōu)勢滿足Gameq,1AdvΦ-GamefinalAdvΦ=ε，那么可以構(gòu)造一個多項式時間算法Ψ以ε的優(yōu)勢攻破假設(shè)3。

系統(tǒng)建立：和2.2節(jié)中的系統(tǒng)建立算法一樣。

階段2：重復(fù)執(zhí)行階段1。

猜測：敵手A輸出一個關(guān)于β的猜測β'。

如果T=T1=e(g1,g1)αs，那么生成的是Mβ的半功能密文；如果T=T2∈Gp1，那么生成的是隨機(jī)消息的半功能密文。因此，若敵手A使Gameq,1AdvΦ-GamefinalAdvΦ=ε不可忽視，那么挑戰(zhàn)者B同樣能夠以不可忽略的優(yōu)勢區(qū)分T1=e(g1,g1)αs和G1上的元素。

至此，定理1證明完畢。

2.6 效率分析

主要從算法的運(yùn)算量以及密文、密鑰、公鑰長度兩個方面來分析上述方案的效率。

算法執(zhí)行的時間主要分布在指數(shù)(Exp)和雙線性配對(Pairing)運(yùn)算上，所以主要分析這兩種運(yùn)算。加密算法主要涉及指數(shù)Exp運(yùn)算，而解密算法主要涉及Pairing運(yùn)算。

從計算次數(shù)以及消息長度兩個方面對比上述方案與基于LSSS隱藏策略的CP-ABE方案(簡稱Lai方案)[14]，結(jié)果見表1和表2。

表1 計算次數(shù)比較

表2 消息長度比較

從表1可以看出，對于系統(tǒng)建立階段，首先對N個屬性進(jìn)行處理，因此會多出N個指數(shù)運(yùn)算，在加密和密鑰生成階段，文中方案的指數(shù)運(yùn)算次數(shù)都為對比方案的一半，雙線性配對運(yùn)算次數(shù)則差不多，而解密階段兩個方案的運(yùn)算次數(shù)則相同。

從表2可以看出，文中方案會使得公鑰長度有所增加，但密文長度減少一半，總體來說，文中方案會增加一些系統(tǒng)存儲空間。

最后，通過仿真實驗，將文中方案與Lai方案在加密時間上作一個比較，結(jié)果如圖1所示。

從圖1可以看出，加密時間隨著訪問結(jié)構(gòu)中屬性個數(shù)的增加基本呈線性增長的趨勢，在相同的屬性個數(shù)下，文中方案所用加密時間要少于Lai方案，且屬性個數(shù)越多，相應(yīng)減少的時間也越多。

圖1 加密時間對比曲線

3 結(jié)束語

在現(xiàn)有CP-ABE方案的基礎(chǔ)上，提出了一種基于LSSS隱藏策略的CP-ABE方案。該方案使用LSSS來表示訪問結(jié)構(gòu)，使得策略表達(dá)更為靈活，通過3素數(shù)合數(shù)階雙線性群來構(gòu)造方案，實現(xiàn)了訪問策略的隱藏，保護(hù)了訪問策略中的敏感信息；同時，從指數(shù)和雙線性配對運(yùn)算次數(shù)和密文、密鑰長度等方面對該方案進(jìn)行了效率分析。結(jié)果表明，該方案提高了加密效率，但也增加了密文、密鑰等消息的長度，因此如何減小消息長度從而減少系統(tǒng)存儲空間是今后進(jìn)一步研究的工作。

[1] SAHAI A, WATERS B. Fuzzy identity-based encryption[C]//Annual international conference on the theory and applications of cryptographic techniques.Berlin:Springer-Verlag,2005:457-473.

[2] GOYAL V,PANDEY O,SAHAI A,et al.Attribute-based encryption for fine-grained access control of encrypted data[C]//Proceedings of the 13th ACM conference on computer and communications security.New York,NY,USA:ACM,2006:89-98.

[3] BETHENCOURT J,SAHAI A,WATERS B.Ciphertext-policy attribute-based encryption[C]//IEEE symposium on security and privacy.[s.l.]:IEEE,2007:321-334.

[4] CHEUNG L,NEWPORT C.Provably secure ciphertext policy ABE[C]//Proceeding of the ACM conference on computer and communications security.New York,NY,USA:ACM,2007:456-465.

[5] GOYAL V,JAIN A,PANDEY O,et al.Bounded ciphertext policy attribute based encryption[C]//Proceedings of the 35th international colloquium on automata,languages and programming,part II.Berlin:Springer-Verlag,2008:579-591.

[6] IBRAIMI L,TANG Q,HARTEL P.Efficient and provable Secure ciphertext-policy attribute-based encryption schemes[C]//Proceedings of the 5th international conference on information security practice and experience.Berlin:Springer-Verlag,2009:1-12.

[7] EMURA K,MIYAJI A,NOMURA A,et al.A ciphertext-policy attribute-based encryption scheme with constant ciphertext length[C]//IS-PEC 2009.Berlin:Springer-Verlag,2009:13-23.

[8] NISHIDE T, YONEYAMA K, OHTA K. Attribute-based encryption with partially hidden encryptor-specified access structure[C]//Proceedings of the 6th international conference on applied cryptography and network security.Berlin:Springer-Verlag,2008:111-129.

[9] LAI J Z,DENG R H,LI Y J.Fully secure cipertext-policy hiding CP-ABE[C]//Proceedings of the 7th information conference on security practice and experience.Berlin:Springer-Verlag,2011:24-39.

[10] 王海斌,陳少真.隱藏訪問結(jié)構(gòu)的基于屬性加密方案[J].電子與信息學(xué)報,2012,34(2):457-461.

[11] RAO Y S,DUTTA R.Recipient anonymous ciphertext-policy attribute based encryption[C]//Proceedings of the 9th international conference on information systems security.New York,NY,USA:Springer-Verlag New York,Inc.,2013.

[12] 宋 衍,韓 臻,劉鳳梅,等.基于訪問樹的策略隱藏屬性加密方案[J].通信學(xué)報,2015,36(9):119-126.

[13] WATERS B.Ciphertext-policy attribute-based encryption:an expressive,efficient,and provably secure realization[C]//Proceedings of the 14th international conference on practice and theory in public key cryptography.Berlin:Springer-Verlag,2011:53-70.

[14] LAI J,DENG R H,LI Y.Expressive CP-ABE with partially hidden access structures[C]//Proceedings of the 7th ACM symposium on information,computer and communications and security.New York,NY,USA:ACM,2012.

[15] LEWKO A, OKAMOTO T, SAHAI A, et al.Fully secure functional encryption:attribute-based encryption and (hierarchical) inner product encryption[C]//Proceedings of the 29th annual international conference on theory and applications of cryptographic techniques.Berlin:Springer-Verlag,2010:62-91.

[16] LEWKO A,WATERS B.New techniques for dual system encryption and fully secure hibe with short ciphertexts[C]//7th theory of cryptography conference.Berlin:Springer-Verlag,2010.