新型自适应安全的密钥策略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.