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

陳丹偉，湯 波

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

0 引 言

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

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

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

1 預備知識

本節介紹相關的基礎知識，包括合數階雙線性群、子群假設問題、訪問結構以及線性秘密共享方案。

1.1 合數階雙線性群

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

(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 合數階子群判定假設

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

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

定義算法Ψ攻破假設1的優勢為：

Adv1Φ,Ψ(λ)=

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

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

定義算法Ψ攻破假設2的優勢為：

Adv2Φ,Ψ(λ)=

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

定義算法Ψ攻破假設3的優勢為：

Adv3Φ,Ψ(λ)=

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

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

1.3 訪問結構

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

1.4 線性秘密共享方案

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

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

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

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

2.1 CP-ABE方案的安全模型

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

(1)系統建立：挑戰者運行系統初始化算法，生成系統公鑰PK和主私鑰MSK，并將PK發送給敵手。

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

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

(4)階段2：重復執行階段1。

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

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

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

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

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

(1)系統建立算法(Setup)。

輸入：安全參數λ以及系統屬性個數N。

輸出：系統公鑰PK和主私鑰MSK。

(2)加密算法(Encryption)。

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

輸出：密文CT。

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

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

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

(4)解密算法(Decryption)。

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

e(g1,g1)αs

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

輸出：明文M。

2.3 正確性推導

e(g1,g1)αs

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

2.4 策略隱藏

不難看出，上式中存在Gp2中的隨機元素，所以敵手并不能確定密文CT由哪個訪問策略加密得到，因此通過Gp2能夠實現訪問策略的隱藏。

2.5 安全性證明

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

當用戶擁有的屬性集滿足訪問結構時，正常私鑰可以解密半功能密文，半功能私鑰可以解密正常密文，但半功能私鑰不能解密半功能密文。

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

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

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

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

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

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

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

系統建立：和2.2節中的系統建立算法一樣。

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

階段2：重復執行階段1。

猜測：敵手A輸出一個關于β的猜測β'。

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

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

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

系統建立：和2.2節中的系統建立算法一樣。

階段2：重復執行階段1。

猜測：敵手A輸出一個關于β的猜測β'。

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

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

系統建立：和2.2節中的系統建立算法一樣。

階段2：重復執行階段1。

猜測：敵手A輸出一個關于β的猜測β'。

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

至此，定理1證明完畢。

2.6 效率分析

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

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

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

表1 計算次數比較

表2 消息長度比較

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

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

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

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

圖1 加密時間對比曲線

3 結束語

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

[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] 王海斌,陳少真.隱藏訪問結構的基于屬性加密方案[J].電子與信息學報,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].通信學報,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.