基于属性的BGN型密文解密外包方案

李镇林，张 薇，白 平，王绪安

(1.武警工程大学 电子技术系，西安 710086； 2.武警工程大学 信息安全保密重点实验室，西安 710086)

(*通信作者电子邮箱lizhenlin19921109@163.com)

基于属性的BGN型密文解密外包方案

李镇林1,2*，张 薇1,2，白 平2，王绪安2

(1.武警工程大学 电子技术系，西安 710086； 2.武警工程大学 信息安全保密重点实验室，西安 710086)

(*通信作者电子邮箱lizhenlin19921109@163.com)

云计算的安全问题是制约其发展的关键瓶颈，其中对云计算结果的访问控制是当前研究的一个热点。在经典的类同态BGN方案基础上，结合CP-ABE(Ciphertext-Policy Attribute-Based Encryption)型密文解密外包设计，构造了基于属性的BGN型密文解密外包方案，部分密文的解密被外包到云上进行，减小了用户的存储开销与计算开销，并且只有用户属性满足访问策略时，才会得到正确的解密结果。与现有的基于属性的外包方案相比，新方案能对密文进行任意次加法同态和一次乘法同态操作。最后，分析了方案的安全性。所提方案在子群判定问题假设下达到语义安全，在随机预言机模型下满足属性安全。

基于属性的加密；云计算；外包计算；同态加密；子群判定问题

0 引言

云计算(Cloud Computing)[1]概念的提出，将信息产业的发展带入了快车道。云服务在给用户提供海量存储服务和强大计算能力的同时，也推动了经济的发展，但云计算伴生的安全问题也日益凸显。Kaufman[2]指出，云的安全问题被认为是云服务实际应用面临诸多困难中最大的挑战，也是云服务亟待解决的最大难题。

如果用户以明文形式将敏感数据保存到云服务器，由于云端可能会复制甚至篡改这些信息，而用户根本无法得知云端的非授权行为，从而造成不可估计的损失，所以云是不能被无条件信任的。为了防止敏感数据的恶意泄露和非法访问，用户可以以密文形式对数据进行外包。

传统的云计算加解密模型无法实现对计算结果的细粒度访问控制。Shamir[3]在1984年提出了基于身份的加密(Identity-Based Encryption， IBE)，用户的公钥由与其身份相关的唯一标识生成，访问时服务器端不需要再查询用户的公钥证书。基于属性的加密(Attribute-Based Encryption， ABE)由Sahai等[4]提出，可以看作是对IBE的推广，在这种加密体制中，用户的密钥和密文与属性关联起来，只有属性满足访问控制策略时，用户才能合法解密，从而实现了对密文的细粒度访问控制。基于属性的加密体制具有良好的特性，引起了国内外密码学家的高度重视，近年来涌现出了大量相关研究成果[5-8]，同时它也被广泛运用到云计算安全算法的设计[9-11]当中，成为云计算中数据保护的重要工具。

本文基于由Boneh、Goh和Nissim提出的经典的类同态BGN[12]方案，利用文献[8]提出的CP-ABE(Ciphertext-Policy Attribute-Based Encryption)型密文解密外包设计，构造了一个基于属性的BGN型密文解密外包方案。在本文的构造中，部分密文的解密过程被外包到云上进行，大大降低了用户的计算量；用户的私钥与属性相关联，访问控制策略被嵌入到密文当中，当且仅当用户属性满足密文策略时才能正常解密，从而实现了对云计算结果的访问控制。同时，该方案支持对密文进行任意次加法同态操作和一次乘法同态操作。

1 预备知识

1.1 双线性映射

G和GT是两个阶为p的乘法循环群，g为群G的生成元，则双线性映射e:G×G→GT满足下列性质：

1)双线性性：对任意u,k∈G和a,b∈Zp，都有e(ua,kb)=e(u,k)ab。

2)非退化性：存在u,k∈G，使得e(u,k)≠1。

3)可计算性：存在有效算法使得对任意u,k∈G，都可以计算出e(u,k)。

1.2 访问结构

假设{P1,P2,…,Pn}是秘密共享的参与者集合，定义P=2{P1,P2,…,Pn}，访问结构Γ是{P1,P2,…,Pn}的非空子集，即Γ⊆P(∅}。访问结构的单调性定义如下：如果A∈Γ且A⊆B，则B∈Γ。同时，称该子集为一个授权子集，不能重构出共享秘密的子集为非授权子集。

1.3 线性秘密共享机制矩阵访问结构

一个定义在秘密共享参与者集合P上的线性秘密共享机制(Linear Secret Sharing Scheme，LSSS)[13]Π是指：

1)所有参与者的份额组成一个Zp上的向量。

1.4 BGN方案

BGN方案[12]能够支持任意次加法同态操作，在双线性映射下又能支持一次乘法同态操作，是同态加密概念[14]被提出后的首个类同态加密方案，2010年Gentry等[15]又在格上实现了BGN方案。方案描述如下：

BGN方案的同态性质分析：

1)加法同态：

C=C1C2hr=km1hr1·km2hr2·hr=km1+m2hr1+r2+r∈G

(2)乘法同态：

令k1=e(k,k)，h1=e(k,h)，则k1的阶为n，h1的阶为q1，并且一定有β∈Z使得h=kβq2，计算

1.5 基于属性的密文解密外包模型

基于属性的密文解密外包方案由Green，Hohenberger和Waters[8]提出。该方案针对传统的基于属性的加密方案增加了一个转换算法，将解密过程部分外包给第三方服务器，解密者只需对第三方服务器反馈的部分密文进行少量简单的运算即可以获知明文。这种外包设计思想充分利用了当下云计算强大的计算能力，大大提高了解密效率。传统的基于属性的加密模型和基于属性的密文解密外包模型分别如图1所示。

图1 传统的基于属性的加密模型和基于属性的密文解密外包模型Fig. 1 Traditional attribute-based encryption model and outsourcing scheme of ABE

在图1(a)所示的传统的基于属性的加密模型中，解密者必须全部下载ABE密文才能进行解密运算，其存储开销与计算开销显然是十分巨大的。针对上述缺点，文献[8]设计了图1(b)所示的外包模型，将ABE密文外包给云等第三方服务器，云再将计算得到的部分密文发送给解密者，解密者只需要下载少量数据并进行简单运算即可得出明文，这一过程的存储开销与计算开销相比传统模型将会减小很多。具体而言，针对经过加密存放在云服务器的原始ABE密文，解密者向云服务器发送一个转换密钥TK，云服务器利用转换密钥对原始ABE密文进行转换运算，得到部分解密的ABE密文，反馈给解密者，解密者只需利用私钥进行一次指数运算即可获知明文消息。

2 基于属性的BGN型密文解密外包方案

本章提出一种基于属性的BGN型密文解密外包方案，通过将BGN方案与基于属性的密文解密外包思想相结合，构造了能够实现对云计算结果访问控制的外包方案。方案由以下五个子算法组成：

PK=(n,g,k,h,e,e′(g,g)α,ga,F,H,G,G1)

密钥产生算法：输入主密钥MSK和属性S，随机选择t′∈Zp，输出：

算法随机选择z∈Zp，并令t=t′/z，输出转换密钥TK：

私钥即为SK=(q1,z,TK)。

算法最后输出部分密文CT′=(c,Q)。

解密算法：输入私钥SK=(q1,z,TK)和密文CT，如果密文不是部分密文，那么必须先运行转换算法将其转换为部分密文。如果转换算法输出为⊥，则解密算法也输出⊥。反之，利用(z,Q)计算出e′(g,g)sα=Qz，而后解密者再利用部分私钥q1计算cq1=(kmH(e′(g,g)αs)hR)q1=(kH(e′(g,g)αs)q1)m，通过Pollard’s lambda算法解密以kH(e′(g,g)αs)q1为底cq1的离散对数即可恢复出明文消息m。其中，最终步骤利用Pollard’s lambda算法进行的解密过程与BGN方案的解密过程是一样的。

3 方案分析

3.1 同态性质分析

本文方案是基于类同态BGN方案，所以它满足任意次加法同态和一次乘法同态性质，详细分析如下：

1)加法同态：对于两个部分密文c1=km1H(e′(g,g)αs)hR1∈G和c2=km2H(e′(g,g)αs)hR2∈G，计算：

c′=c1c2hR=(km1H(e′(g,g)αs)hR1)·(km2H(e′(g,g)αs)hR2)hR=

k(m1+m2)H(e′(g,g)αs)hR1+R2+R∈G

属性满足密文策略的合法解密者可以求出e′(g,g)sα的值，进而利用解密算法即可算出m1+m2。

2)乘法同态：令k1=e(k,k)，h1=e(k,h)，则k1的阶为n，h1的阶为q1，并且一定有β∈Z使得h=kβq2，计算：

同理，合法解密者能够算出m1m2。由于不存在有效算法使得e:G1×G1→G成立，所以本文方案只能进行一次乘法。

3.2 安全性分析

本文将从以下两个方面分析方案的安全性：一是证明方案在子群判定问题困难假设下满足语义安全；另一方面，在随机预言机模型下分析方案的属性安全。

3.2.1 语义安全分析

定义1 子群判定问题。定义算法G，输入安全参数τ∈Z+，输出元组(q1,q2,G,G1,e)，其中G,G1都是阶为n=q1q2的群，e:G×G→G1是双线性映射。输入参数τ，算法G运行如下：

1)生成两个随机的τ比特的素数q1,q2，令n=q1q2∈Z。

2)生成满足1.1节中定义的双线性映射群G,G1，其生成元为g，阶为n。

3)输出(q1,q2,G,G1,e)。

子群判定问题定义为：给定元组(q1,q2,G,G1,e)和元素x∈G，如果x的阶是q1，则输出“1”，否则输出“0”。也即在不清楚n的分解情况下，判定元素x是否属于G的一个子群。对于算法敌手A，解决该问题的优势定义为：

SD-AdvA(τ)=|Pr[A(n,G,G1,e,x)=1:(q1,q2,G,

G1,e)←G(τ),n=q1q2,x←G]-Pr[A(n,G,G1,

e,xq2)=1:(q1,q2,G,G1,e)←G(τ),n=q1q2,

x←G]|

定义2 称算法G满足子群判定假设，对任意多项式时间算法敌手A解决上述子群判定问题的优势SD-AdvA(τ)是可以忽略不计的。

证明 本文方案的安全性是建立在敌手算法A不能攻破子群判定问题的假设基础上。假设存在某一算法A能够以优势ε攻破本文方案的语义安全性，那么就一定存在敌手算法A能够以优势ε解决子群判定问题假设。详细的证明过程如下：

1)敌手算法A随机选择g∈G，将公钥(n,G,G1,e,g,x)发送给算法。

3)算法B输出关于b的猜测b′，如果b=b′，算法A输出“1”，否则输出“0”。

如果元素x是在群G中均匀分布，那么挑战密文C在群G中也是均匀分布，与b的选择无关，即Pr|b=b′|=1/2；如果x是群G的q1阶子群中的元素，那么根据假设就有Pr|b=b′|>1/2+ε，所以SD-AdvA(τ)>ε，这就意味着敌手算法A解决子群判定问题假设的优势ε是不可忽略的，与困难问题矛盾。

因此，方案在子群判定问题困难假设下达到了语义安全。

3.2.2 属性安全分析

对方案的属性安全分析借鉴文献[8]的方法，其安全模型如下：

Setup：挑战者运行初始化算法，将安全参数及公钥PK发送给敌手算法A。

Phase 1：挑战者新设一个空表T和一个空集D，并设置初始指针j=0。敌手算法A被允许重复以下任意查询。

·Create(S)：挑战者设置指针j:=j+1，运行密钥产生算法得到一组与属性S相关的密钥对(SK,TK)，挑战者将该密钥对存储在表T中，并记录为(j,S,SK,TK)。算法最终将转换密钥TK发送给敌手算法A。针对同一属性S，这一过程可以被重复查询。

·Corrupt(i)：如果在表T中存在第i项记录，即指针j≥i，那么挑战者就可得到该记录(j,S,SK,TK)的内容，并且修改D:=D∪{S}，而后将私钥SK发送给敌手算法A；如果在表T中不存在第i项记录，则输出⊥。

·Decrypt(i,CT)：如果在表T中存在第i项记录，那么挑战者就可得到该记录(j,S,SK,TK)的内容，并且挑战者将输入(SK,CT)进行解密得到的解密结果发送给敌手算法A；如果在表T中不存在第i项记录，则输出⊥。

Challenge：敌手算法A提交两个长度相等的消息m0和m1，此外敌手算法A再选择一个访问结构(M*,ρ*)，满足对于所有的S∈D，f(S,(M*,ρ*))≠1。挑战者以抛掷硬币的方式随机选择mb，并且在访问结构(M*,ρ*)下加密mb，将得到的密文CT*发送给敌手算法A。

Phase 2：以上的Phase 1过程可以重复进行，但是敌手算法A不能：

·从挑战密文中直接获得私钥，算法A不能在Challenge中出现f(S,(M*,ρ*))=1的情况，也即是说在Corrupt这一步的查询中，满足f(S,(M*,ρ*))=1的属性S不能被添加到D中。

·查询得到了正确结果，也即Decrypt查询应在Phase 1中完成，除了当查询结果为m0或者m1时，挑战者用消息test来代替回答。

Guess：敌手算法A输出关于b的猜测b′。

定义3 如果敌手算法A在上述安全游戏中多项式时间内优势可以忽略不计，那么方案就在随机预言机模型下满足属性安全。

证明 在现实攻击中，由于满足访问结构的属性S都被排除在属性集合D之外，当敌手算法A对转换密钥TK及私钥SK进行查询时，得不到能够正确解密的相关密钥，只可能以等概率猜测b，即敌手算法A的安全优势多项式时间内优势可以忽略不计。

因此，方案就在随机预言机模型下满足属性安全。

3.3 性能分析

Green等在文献[8]中提出了基于属性的密文解密外包思想，并构造了一个密文策略的外包方案; Gentry等在文献[15]中利用容错学习问题(Learning With Errors， LWE)构造了一个BGN型的类同态加密方案。将本文构造的方案与文献[8，15]中的方案分别进行对比，主要比较方案类型、是否支持同态操作、是否支持访问控制、密文尺寸、解密时间开销等，结果如表1、表2所示。通过表1可以看出，相比文献[8]中的密文策略外包方案，本文方案能够支持对外包的密文进行同态操作，包括任意次加法同态和一次乘法同态操作。表2中，m代表明文空间大小，E代表进行一次指数运算所耗费的最大时间。通过表2可以看出，与文献[15]中利用容错学习问题构造的BGN型类同态方案相比，本文方案能够实现对加密结果的解密权限的控制，并且本文方案在密文尺寸和解密时间上都优于文献[15]的方案。

表1 与Green方案对比Tab. 1 Comparison with the Green scheme

表2 与Gentry方案对比Tab. 2 Comparison with the Gentry scheme

4 结语

本文通过将基于属性的密文解密外包的思想引入到BGN方案中，构造了一个适用于云计算环境的基于属性的BGN型密文解密外包方案；通过利用基于属性加密的方法，解决了云计算结果访问控制问题，并且解密过程的外包大幅度降低了用户的计算量，提高了用户解密效率。进一步的工作是探索基于属性的密文解密外包与全同态方案的结合，构造效率更高、更加实用的云环境下全同态基于属性的密文解密外包方案。

References)

[1] ERIC H. Head in the clouds [J]. Nature, 2007, 449(7156): 963.

[2] KAUFMAN L M. Data security in the world of cloud computing [J]. IEEE Security & Privacy, 2009, 7(4): 61-64.

[3] SHAMIR A. Identity-based cryptosystems and signature schemes [C]// CRYPTO 1984: Proceedings of the 1984 Workshop on the Theory and Application of Cryptographic Techniques, LNCS 196. Berlin: Springer-Verlag, 1984: 47-53.

[4] SAHAI A, WATERS B. Fuzzy identity-based encryption [C]// EUROCRYPT 2005: Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 3494. Berlin: Springer-Verlag, 2005: 457-473.

[5] PIRRETTI M, TRAYNOR P, MCDANIEL P, et al. Secure attribute-based systems [J]. Journal of Computer Security, 2010, 18(5): 799-837.

[6] NING J, DONG X, CAO Z, et al. White-box traceable ciphertext-policy attribute-based encryption supporting flexible attributes [J]. IEEE Transactions on Information Forensics and Security, 2015, 10(6): 1274-1288.

[7] ZHANG K, MA J, LIU J, et al. Adaptively secure multi-authority attribute-based encryption with verifiable outsourced decryption [J]. Science China Information Sciences, 2016, 59: 99105.

[8] GREEN M, HOHENBERGER S, WATERS B. Outsourcing the decryption of ABE ciphertexts [C]// SEC ’11： Proceedings of the 20th USENIX Conference on Security. Berkeley, CA： USENIX Association, 2011: 34.

[9] WAN Z, LIU J, DENG R H. HASBE: a hierarchical attribute-based solution for flexible and scalable access control in cloud computing [J]. IEEE Transactions on Information Forensics and Security, 2012, 7(2): 743-754.

[10] YANG K, JIA X, REN K, et al. DAC-MACS: effective data access control for multiauthority cloud storage systems [J]. IEEE Transactions on Information Forensics and Security, 2013, 8(11): 1790-1801.

[11] WANG S, ZHOU J, LIU J, et al. An efficient file hierarchy attribute-based encryption scheme in cloud computing [J]. IEEE Transactions on Information Forensics & Security, 2016, 11(6): 1265-1277.

[12] BONEH D, GOH E-J, NISSIM K. Evaluating 2-DNF formulas on ciphertexts [C]// TCC 2005: Proceedings of the 2005 Second International Conference on Theory of Cryptography. Springer Berlin Heidelberg, LNCS 3378. Berlin: Springer-Verlag, 2005: 325-341.

[13] WATERS B. Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization [C]// PKC ’11: Proceedings of the 14th International Conference on Public Key Cryptography, LNCS 6571. Berlin: Springer-Verlag, 2011: 53-70.

[14] RIVEST R L, ADLEMAN L, DERTOUZOS M L. On data banks and privacy homomorphisms [J]. Foundations of Secure Computation, 1978, 4(11): 169-179.

[15] GENTRY C, HALEVI S, VAIKUNTANATHAN V. A simple BGN-type cryptosystem from LWE [C]// EUROCRYPT 2010: Proceedings of the 2010 Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 6110. Berlin: Springer-Verlag, 2010: 506-522.

[16] MENEZES A J, VAN OORSCHOT P, VANSTONE S A. Handbook of applied cryptography [S]. Boca Raton, FL: CRC Press, 1999: 425-488.

This work is partially supported by the Natural Science Foundation of Shaanxi Province (2016JQ6037).

LIZhenlin, born in 1992, M. S. candidate. His main research interest is cryptology.

ZHANGWei, born in 1976, Ph. D., professor. Her research interests include cryptology, information security.

BAIPing, born in 1990, M. S. candidate. His main research interest is cryptology.

WANGXu’an, born in 1981, Ph. D., associate professor. His research interests include cryptology, information security.

BGNtypeoutsourcingthedecryptionofattribute-basedencryptionciphertexts

LI Zhenlin1,2*, ZHANG Wei1,2, BAI Ping2, WANG Xu’an2

(1.ElectronicTechniqueDepartment,EngineeringCollegeoftheChineseArmedPoliceForce,Xi’anShaanxi710086,China；2.KeyLaboratoryofInformationSecurity,EngineeringCollegeoftheChineseArmedPoliceForce,Xi’anShaanxi710086,China)

Cloud computing security is the key bottleneck that restricts its development, and access control on the result of cloud computing is a hot spot of current research. Based on the classical homomorphic encryption BGN (Boneh-Goh-Nissim) scheme, and combined with outsourcing the decryption of Ciphertext-Policy Attribute-Based Encryption (CP-ABE) ciphertexts, a BGN type outsourcing the decryption of ABE ciphertexts was constructed. In the scheme, partial decryption of ciphertexts was outsourced to the cloud, and only the users whose attributes meet the access policy could get the correct decryption result, thus reducing the storage and computation overhead of users. Compared with the existing outsourcing schemes of ABE, the proposed scheme can operate on ciphertexts for arbitrary additions and one multiplication. Finally, the security of the scheme was analyzed. The proposed scheme is semantically secure under the subgroup decision assumption, and its attribute security is proved under random oracle model.

attribute-based encryption; cloud computation; outsourcing computing; homomorphic encryption; subgroup decisional problem

TP309.7

A

2017- 03- 03;

2017- 05- 02。

陕西省自然科学基金资助项目(2016JQ6037)。

李镇林(1992—)，男，四川巴中人，硕士研究生，主要研究方向：密码学； 张薇(1976—)，女，陕西西安人，教授，博士，主要研究方向：密码学、信息安全； 白平(1990—)，男，内蒙古乌兰察布人，硕士研究生，主要研究方向：密码学； 王绪安(1981—)，男，湖北公安人，副教授，博士，主要研究方向：密码学、信息安全。

1001- 9081(2017)08- 2287- 05

10.11772/j.issn.1001- 9081.2017.08.2287