新型自適應安全的密鑰策略ABE方案

羅頌，陳鐘

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

1 引言

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

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

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

在Waters[12]提出雙重系統加密的證明技術后，Lewko等人[13]利用雙重系統加密技術，在合數階群上構造了一個自適應安全的密鑰策略ABE方案，該方案同樣支持單調訪問結構，并且方案的安全性基于合數階群上靜態的困難性假設。

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

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

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

2 背景知識

2.1 雙線性對

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

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

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

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

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

2.2 對偶正交基

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

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

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

2.3 困難性假設

定義敵手A打破子空間假設的優勢為

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

根據文獻[15]，子空間假設可以歸約到判定線性假設。

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

2.4 訪問結構

定義4 設｛P1,…,Pn｝是n個參與者的集合。稱集合A?2{P1,…,Pn}是單調的，如果?B,C有B∈A且B?C則C∈A。訪問結構是｛P1,…,Pn｝的非空子集，即A?2{P1,…,Pn}{?}。特別的，當A是單調時，稱A是單調訪問結構。A中的元素稱為授權集合，其余不在A中元素稱為非授權集合。

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

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

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

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

2.5 密鑰策略ABE

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

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

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

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

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

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

Setup挑戰者運行Setup算法， 將公鑰發送給敵手A。

Phase1 A提交一個訪問結構A進行KeyGen查詢，挑戰者返回相應的密鑰SK。A提可以重復該過程多項式次數。

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

Phase2 重復Phase 1，但要求S不能滿足提交的訪問結構。

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

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

3 方案構造

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

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

從而0/M C C= 。

4 安全性證明

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

則可以構造算法B以ε的優勢攻破(3, 1)—子空間假設。

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

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

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

5 方案討論

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

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

表1 方案對比

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

6 結束語

本文構造了一個密鑰策略的ABE方案，該方案支持單調訪問策略，并能夠在標準模型上證明自適應安全性。本文的方案基于對偶正交基構造，利用雙重系統加密技術將安全性歸約于判定線性假設。與Lewko等人之前提出的同樣是自適應安全的密鑰策略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]. 計算機研究與發展, 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.