羅頌，陳鐘

(1. 重慶理工大學(xué) 計算機科學(xué)與工程學(xué)院，重慶 400054；2. 北京大學(xué) 信息科學(xué)技術(shù)學(xué)院軟件研究所，北京 100871)

1 引言

基于屬性的加密（ABE, attribute-based encryption）是基于身份的加密（IBE, identity-based encryption）[1～3]的泛化，即用戶的公鑰不再由某一個具體的身份（如E-mail，IP地址等）來代表，而是由一系列的屬性（如單位、職稱）來表示。在ABE中，密文或密鑰可以結(jié)合訪問控制策略，能夠?qū)崿F(xiàn)細粒度的訪問控制，因而非常適合復(fù)雜開放式網(wǎng)絡(luò)環(huán)境下對數(shù)據(jù)共享要求靈活可擴展的場合。ABE繼承了IBE的無證書特性，加密者僅需要使用接收者的屬性信息結(jié)合公共參數(shù)即可完成加密，避免了管理公鑰證書帶來的開銷。

基于屬性的加密最早源于基于模糊身份的加密（FIBE， fuzzy identity-based encryption），由Sahai和Waters[4]在2005年的歐密會上提出。模糊IBE又稱為門限ABE，密文可以對n個屬性進行加密，并設(shè)置門限t。當(dāng)用戶擁有的屬性與密文加密的屬性交集包含的屬性個數(shù)大于等于t時即可成功解密。ABE的正式定義由Goyal等人[5]給出，并分為2種類型：密鑰策略ABE和密文策略ABE。Goyal等人還給出了一個密鑰策略ABE方案。在密鑰策略ABE[4～6]中，用戶的密鑰與一個訪問結(jié)構(gòu)相聯(lián)系，而密文則附帶一些屬性。而在密文策略ABE[7,8]中，情形正好相反。用戶的密鑰附帶一些屬性，而密文則與訪問結(jié)構(gòu)相聯(lián)系。一般來說，密鑰策略ABE比較適合數(shù)據(jù)靜態(tài)的場景如付費電視、視頻點播等，而密文策略ABE適合用戶靜態(tài)的場景如廣播加密等。

Goyal等人[5]提出的密鑰策略ABE方案支持單調(diào)訪問結(jié)構(gòu)，能夠?qū)用軘?shù)據(jù)進行細粒度的訪問控制，但該方案僅具有選擇安全性，且不支持屬性的“非”操作。Ostrovsky等人[6]利用廣播撤銷機制實現(xiàn)表示“非”的密鑰策略ABE機制，使得策略表示更加靈活。但是該方案仍然是選擇性安全的，而且密文和用戶密鑰大小、加解密開銷都翻倍。Attrapadung與Imai[9]則提出了一個雙重策略的ABE方案，該方案允許密鑰策略和密文策略同時作用在加密數(shù)據(jù)上。楊曉元等人[10]研究了多授權(quán)機構(gòu)的密文策略ABE方案，提出了一個選擇性安全的多主密鑰密文策略ABE方案。Katz、 Sahai和Waters[11]進一步增強了策略的表示，提出了“謂詞加密”（predicate encryption），和“功能加密”（functional encryption）的概念，能夠?qū)崿F(xiàn)密鑰策略或者密文策略。

在Waters[12]提出雙重系統(tǒng)加密的證明技術(shù)后，Lewko等人[13]利用雙重系統(tǒng)加密技術(shù)，在合數(shù)階群上構(gòu)造了一個自適應(yīng)安全的密鑰策略ABE方案，該方案同樣支持單調(diào)訪問結(jié)構(gòu)，并且方案的安全性基于合數(shù)階群上靜態(tài)的困難性假設(shè)。

然而，由于基于合數(shù)階群的困難性假設(shè)一般基于大數(shù)分解的困難性[11]，因此在同樣的安全級別，合數(shù)階群要求比素數(shù)階群具有更大的尺寸，進而導(dǎo)致群上的一個關(guān)鍵運算且是最耗時的運算——雙線性對運算在合數(shù)階群和素數(shù)階群上差距表現(xiàn)的相當(dāng)驚人。文獻[14]指出，在80bit的AES安全性上，前者的雙線性對的單次運算時間是后者的50倍左右。因此，仍然有必要研究素數(shù)階群上的密鑰策略ABE方案的構(gòu)造。

目前，關(guān)于素數(shù)階群上的各類密碼方案的構(gòu)造（包括IBE、ABE等）通常有2種方法。一種是根據(jù)應(yīng)用場景直接構(gòu)造，這也是常用的構(gòu)造方法；另外一種是將合數(shù)階群上的方案翻譯到素數(shù)階群上來。Freeman[14]研究了這種翻譯的可能性及困難性，之后由Lewko[15]基于對偶正交基實現(xiàn)了對Lewko-Waters IBE方案[16]在素數(shù)階群上的構(gòu)造。

本文在Lewko工作[15]的基礎(chǔ)上對密鑰策略ABE的構(gòu)造進行了深入研究，結(jié)合對偶正交基的技術(shù)，提出了一種新型的自適應(yīng)安全的密鑰策略ABE方案。該方案在素數(shù)階上構(gòu)造，支持單調(diào)訪問結(jié)構(gòu)，具有較高的計算效率。本文利用雙重系統(tǒng)加密的證明技術(shù)，在標準模型上證明了提出的方案在判定線性假設(shè)下是自適應(yīng)安全的。

2 背景知識

2.1 雙線性對

定義1 G，GT為p階的乘法循環(huán)群，p是素數(shù)。g是G的一個生成元，e:G×G→GT是一個雙線性映射，具有如下性質(zhì)。

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

2) 非退化性：e(g,g)≠1。注意到GT是素數(shù)階群, 這意味著e(g,g)是GT的生成元。

如果G中的運算及雙線性映射e都是多項式時間可計算的，稱G是一個雙線性群，e是一個雙線性對。

本文假定有一個有效的算法G來生成雙線性群。該算法以安全參數(shù)λ為輸入, 輸出一個四元組（p,G,GT,g∈G,e），其中g(shù)是G的一個生成元，log(p)=Θ(λ)。

2.2 對偶正交基

給定一個p?上的n維向量，g是G中的一個元素，定義為G上的一個n元組為

定義2 定維數(shù)n，如果np?上的2組基滿足如下條件

稱(B, B*)是G上一組n維對偶正交基。

2.3 困難性假設(shè)

定義敵手A打破子空間假設(shè)的優(yōu)勢為

如果對于任何多項式時間的敵手A，該優(yōu)勢都是可忽略的，稱群生成算法G滿足子空間假設(shè)，或者子空間假設(shè)在G上成立。

根據(jù)文獻[15]，子空間假設(shè)可以歸約到判定線性假設(shè)。

引理1 如果判定線性假設(shè)在G上成立，則子空間假設(shè)在G上也成立。

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

定義4 設(shè)｛P1,…,Pn｝是n個參與者的集合。稱集合A?2{P1,…,Pn}是單調(diào)的，如果?B,C有B∈A且B?C則C∈A。訪問結(jié)構(gòu)是｛P1,…,Pn｝的非空子集，即A?2{P1,…,Pn}{?}。特別的，當(dāng)A是單調(diào)時，稱A是單調(diào)訪問結(jié)構(gòu)。A中的元素稱為授權(quán)集合，其余不在A中元素稱為非授權(quán)集合。

定義5 與者集合P上的秘密共享方案Π稱為在?p上是線性的，如果

1) 每位參與者的份額是?p上的一個向量；

2) 存在?行n列矩陣A 稱為Π的共享生成矩陣。令函數(shù)ρ為矩陣A的第i行到參與者的映射函數(shù)，即ρ(i)∈P。設(shè)要共享的秘密為s∈?p，考慮向量，這里r2,…,rn是隨機選取的整數(shù)，則向量是秘密s關(guān)于Π的?個份額，第i個份額屬于參與者ρ(i)。

文獻[17]表明，單調(diào)訪問結(jié)構(gòu)與線性秘密共享方案是等價的，且每個線性秘密共享方案具有線性重構(gòu)的性質(zhì)。設(shè)Π是訪問結(jié)構(gòu)A對應(yīng)的線性秘密共享方案。令S∈A為一授權(quán)集，I?{1,…,?}為S的指標集，即I={i:ρ(i)∈S}。則存在多項式時間可計算的常數(shù){ωi∈?p}i∈I，當(dāng){λi}為秘密s關(guān)于Π 的有效共享時，有對于非授權(quán)集則不存在這樣的{ωi}。

2.5 密鑰策略ABE

定義6 密鑰策略ABE包含如下4個算法：系統(tǒng)建立（Setup），密鑰生成（KeyGen），加密（Encrypt）及解密（Decrypt）。

Setup(1λ,U) 該算法以安全參數(shù)λ和屬性集合U為輸入，輸出公鑰PK及主密鑰MK。

KeyGen(PK,MK,A) 該算法以公鑰PK、主密鑰MK及一個訪問結(jié)構(gòu)A為輸入，輸出與A相聯(lián)系的密鑰SK。

Encrypt(PK, M, S) 該算法以公鑰PK、明文消息M及接收者的屬性集S為輸入，輸出密文CT。

Decrypt(PK,CT,SK) 該算法以公鑰PK、以屬性集S加密的密文CT及與訪問結(jié)構(gòu)A相聯(lián)系的密鑰SK為輸入，如果S滿足訪問結(jié)構(gòu)A，即S|=A，則輸出明文M；反之，則輸出終止符⊥。

給出密鑰策略ABE的安全性定義。首先，定義一個挑戰(zhàn)者與敵手之間的游戲如下。

Setup挑戰(zhàn)者運行Setup算法， 將公鑰發(fā)送給敵手A。

Phase1 A提交一個訪問結(jié)構(gòu)A進行KeyGen查詢，挑戰(zhàn)者返回相應(yīng)的密鑰SK。A提可以重復(fù)該過程多項式次數(shù)。

Challenge A提交2個等長的消息0M，1M及屬性集合S。屬性集S必須不滿足之前提交的所有訪問結(jié)構(gòu)。挑戰(zhàn)者隨機選擇一個比特b，然后利用屬性集S加密消息M得到Encrypt(PK,bM,S)，并將其返回給挑戰(zhàn)者。

Phase2 重復(fù)Phase 1，但要求S不能滿足提交的訪問結(jié)構(gòu)。

Guess A輸出對b的猜測'b。

定義7 稱一個密鑰策略ABE方案是自適應(yīng)安全的，如果任何多項式時間的敵手在上面游戲中的優(yōu)勢都是可忽略的。

3 方案構(gòu)造

利用對偶正交基和線性秘密共享，給出一個密鑰策略ABE方案的構(gòu)造。將屬性視為參與者，假設(shè)要加密的消息M是TG上的元素，且在訪問結(jié)構(gòu)的生成矩陣A中，每個屬性只出現(xiàn)一次。

Setup(1λ, U) 給定安全參數(shù)λ及屬性集合U，算法先運行群生成算法G得到（p，G，GT，g∈G，e），并從隨機選取對偶正交基(,)*D D。設(shè)接著隨機選取對于每個屬性i∈U，隨機選擇最后算法發(fā)布公鑰主密鑰為α,

從而0/M C C= 。

4 安全性證明

本節(jié)將給出上節(jié)構(gòu)造的 ABE方案的安全性。使用文獻[12]介紹的雙重系統(tǒng)加密證明技術(shù)，定義了2個額外的結(jié)構(gòu)：半功能密文及半功能密鑰。半功能密鑰有2種形式，分別稱為第1類和第2類。它們并不出現(xiàn)在實際的方案中，僅用于方案的安全性證明。

半功能密文 通過如下步驟得到一組半功能密文：首先調(diào)用加密算法得到一組正常密文然后隨機選取，對 S中的每個屬性 i，同樣隨機選取，這些iz將被保存并用于生成第 1類的半功能密鑰。半功能密文為

第1類的半功能密鑰。通過如下步驟得到一組第1類的半功能密鑰：首先調(diào)用密鑰生成算法得到

第2類的半功能密鑰。第2類的半功能密鑰計算與第1類的半功能密鑰相似，但維持xK不變：首先調(diào)用密鑰生成算法得到一組正常密鑰然后選取隨機向量，并計算第2類的半功能密鑰為

注意到第1類或第2類的半功能密鑰均能解密正常密文，而正常密鑰也能解密半功能密文。但當(dāng)?shù)?類或第2類的半功能密鑰解密半功能密文時，解密過程將會出現(xiàn)一個擾動因子（注意第 1類中的iz與半功能密文選取的值相同），當(dāng)10u= 時，仍然可以解密半功能密文。此時，本文稱該半功能密鑰是象征性的。

本文將方案的安全性歸約于(3, 1)—子空間假設(shè)，最終歸約于判定線性假設(shè)。證明過程使用雙重系統(tǒng)加密證明技術(shù)，利用混合爭論的方法，通過一系列游戲的兩兩不可區(qū)分性來證明系統(tǒng)的安全性。令q為攻擊者能夠進行密鑰查詢的最大次數(shù)。定義如下幾種游戲。(0)kq≤≤。

GameReal：該游戲為在第2節(jié)定義的真實游戲，即密文和密鑰都是正常的。

Gamek,1：該游戲與 G ameReal相似，區(qū)別在于挑戰(zhàn)密文為半功能密文，而前 k -1次密鑰查詢返回的是第2類的半功能密鑰，第k次密鑰查詢返回的是第1類的半功能密鑰，剩下的查詢返回正常密鑰。

Gamek,2：該游戲與 G ameReal相似，區(qū)別在于挑戰(zhàn)密文為半功能密文，而前k次密鑰查詢返回的是第2類的半功能密鑰，剩下的查詢返回正常密鑰。

GameFinal：此游戲與 G ameq,2相似，區(qū)別在于挑戰(zhàn)密文則是對一個隨機消息加密得到的一個半功能密文。

注意到 G ame0,1= Game0,2，在該游戲中所有密鑰是正常的，而挑戰(zhàn)密文是半功能密文。本文用Game0來代表這2個游戲。在游戲Gameq,2中，所有返回的密鑰都是第2類的，而在GameFinal，攻擊者的優(yōu)勢為0，因為此時是對一個隨機消息的加密。通過下列引理，證明這些游戲是兩兩不可區(qū)分的。

引理2 假設(shè)存在多項式時間算法A滿足

則我們可以構(gòu)造算法B以ε的優(yōu)勢攻破(3, 1)—子空間假設(shè)。

引理3 假設(shè)存在多項式時間算法A滿足

則我們可以構(gòu)造算法B以ε的優(yōu)勢攻破(3, 1)—子空間假設(shè)。

引理4 假設(shè)存在多項式時間算法A滿足

則我們可以構(gòu)造算法B以ε的優(yōu)勢攻破(3, 1)—子空間假設(shè)。

引理5 假設(shè)存在多項式時間算法A滿足

則可以構(gòu)造算法B以ε的優(yōu)勢攻破(3, 1)—子空間假設(shè)。

囿于篇幅，略去以上引理的證明。對于上節(jié)構(gòu)造的密鑰策略ABE方案，有如下結(jié)論。

定理1 如果判斷線性假設(shè)成立，則密鑰策略ABE方案是自適應(yīng)安全的。

證明 由引理2～引理5可知，如果(3, 1)—子空間假設(shè)成立，那么真實游戲GameReal與GameFinal是不可區(qū)分的。又因為GameFinal是對一隨機消息的加密，因此在信息論意義上，b的值對敵手是完全隱藏的，所以敵手在游戲GameReal中的優(yōu)勢是可忽略的。結(jié)合引理1，子空間假設(shè)可以歸約到判定線性假設(shè)，從而定理得證。

5 方案討論

在本文給出的方案中，屬性在密鑰中的訪問結(jié)構(gòu)只能出現(xiàn)一次，這限制了方案的靈活性。如果需要屬性是多用的，假設(shè)某屬性att出現(xiàn)的最大次數(shù)是k，可以將該屬性進行如下編碼：att:1，…，att:k，然后在加密和密鑰生成時從低到高使用att:1，…，att:k。這樣方案的安全性不變，仍是自適應(yīng)安全的，而屬性的總數(shù)從||U擴展到了||kU。

目前支持單調(diào)訪問結(jié)構(gòu)的自適應(yīng)安全的密鑰策略ABE方案除了本文提出的方案，還有Lewko等人提出的方案（文獻[13]）。表1對這2個方案在效率和安全性上做了簡單對比。

表1 方案對比

解密列出的是在同等條件下需要的雙線性對數(shù)目，因為雙線性對運算是解密中最為耗時的操作。盡管從數(shù)目上，本文方案需要進行3倍于Lewko等人方案的雙線性對運算，但是由于Lewko等人的方案是在合數(shù)階群上提出的，而合數(shù)階群上的對運算效率遠低于素數(shù)階群上的對運算（例如在80bit的AES安全性上，前者的單次對運算時間是后者的50倍左右[14]），所以在同等安全級別上，本文的方案會更有效率。此外，本文的方案安全性基于標準的判定線性假設(shè)，這也是方案文獻中[13]不能比擬的。

6 結(jié)束語

本文構(gòu)造了一個密鑰策略的ABE方案，該方案支持單調(diào)訪問策略，并能夠在標準模型上證明自適應(yīng)安全性。本文的方案基于對偶正交基構(gòu)造，利用雙重系統(tǒng)加密技術(shù)將安全性歸約于判定線性假設(shè)。與Lewko等人之前提出的同樣是自適應(yīng)安全的密鑰策略ABE方案相比，在同樣的安全性級別上，本文的方案更有效率。

[1] SHAMIR A. Identity-based cryptosystems and signatures schemes[J].Lecture Notes in Computer Science, 1985,196: 47-53.

[2] BONEH D, FRANKLIN M. Identity-based encryption from the weil pairing[J]. Lecture Notes in Computer Science, 2001, 2139:213-229.

[3] COCKS C. An identity based encryption scheme based on quadratic residues[A]. The 8th IMA International Conference on Cryptography and Coding[C]. Cirencester, UK, 2001.360-363.

[4] SAHAI A, WATERS B. Fuzzy identity-based encryption[J]. Lecture Notes in Computer Science, 2005,3494:457-473.

[5] GOYAL V, PANDEY O, SAHAI A, etal. Attribute-based encryption for fine-grained access control of encrypted data[A]. The 13th ACM Conference on Computer and Communications Security ACM[C]. Alexandria, VA, USA, 2006. 89-98.

[6] OSTROVSKY R, SAHAI A, WATERS B. Attribute-based encryption with non-monotonic access structures[A]. The 14th ACM Conference on Computer and Communications Security ACM[C]. Alexandria, VA,USA, 2007. 195-203.

[7] BETHENCOURT J, SAHAI A, WATERS B. Ciphertext-policy attribute-based encryption[A]. IEEE Symposium on Security and Privacy[C]. Oakland, California, USA,2007. 321-334.

[8] WATERS B. Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization[EB/OL]. http://eprint.iacr.org/,2008.

[9] ATTRAPADUNG N, IMAI H.Dual-policy attribute based encryption[A]. ACNS 2009[C]. France, 2009. 168-185.

[10] 楊曉元, 蔡偉藝, 陳海濱. 多主密鑰功能加密: 基于LMSSS的M-KP-ABE方案[J]. 計算機研究與發(fā)展, 2011, 48(8): 1363-1369.YANG X Y, CAI W Y, CHEN H B. Multiple-authority key functional encryption: a M-KP-ABE scheme based on LMSSS[J]. Journal of Computer Research and Development, 2011, 48(8): 1363-1369.

[11] KATZ J, SAHAI A, WATERS B. Predicate encryption supporting disjunctions, polynomial equations, and inner products[A]. Advances in Cryptology - EUROCRYPT 2008[C]. Istanbul, Turkey, 2008. 146-162.

[12] WATERS B. Dual system encryption: Realizing fully secure ibe and hibe under simple assumptions[A]. Advances in Cryptology -CRYPTO 2009[C]. Santa Barbara, California, USA, 2009. 619-636.

[13] LEWKO A, OKAMOTO T, SAHAI A, etal. Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption[A]. Advances in Cryptology-EUROCRYPT 2010[C].French, 2010. 62-91.

[14] FREEMAN D M. Converting pairing-based cryptosystems from composite-order groups to prime-order groups[A]. Advances in Cryptology- EUROCRYPT 2010[C]. French, 2010. 44-61.

[15] LEWKO A. Tools for simulating features of composite order bilinear groups in the prime order setting[EB/OL]. Cryptology ePrint Archive,Report 2011/490, http://eprint.iacr.org/. 2011.

[16] Lewko A, Waters B. New techniques for dual system encryption and fully secure hibe with short ciphertexts[A]. TCC 2010[C]. Zurich,Switzerland, 2010. 455-479.

[17] BEIMEL A. Secure Schemes for Secret Sharing and Key Distribution[D].Haifa: Israel Institute of Technology, 1996.