刘　青,李陶深，2,黄汝维,2

(1.广西大学计算机与电子信息学院, 广西南宁530004;2.广西高校并行与分布式计算技术重点实验室, 广西南宁530004)



云计算环境中基于策略的多用户全同态加密方法

刘青1,李陶深1，2,黄汝维1,2

(1.广西大学计算机与电子信息学院, 广西南宁530004;2.广西高校并行与分布式计算技术重点实验室, 广西南宁530004)

摘要:全同态加密技术是解决云环境隐私安全问题的有效方法。考虑云环境下用户多样性特征，提出基于策略的多用户全同态加密方案(PB-MUFHE)，该方案在全同态加密算法的基础上，通过在密文中设定适当的访问策略以及在密钥中设定属性，从而满足多用户密文的全同态运算以及多用户共享，并支持细粒度的访问控制。安全分析证明PB-MUFHE可以抵制共谋攻击，且在LWE困难度假设随机域模型下是IND-CPA安全的。性能评估表明：PB-MUFHE高效地实现密文数据的全同态运算，并能有效地支持访问控制和多用户共享。

关键词:云计算；全同态加密；多用户；基于属性加密；密文策略访问控制

云计算作为一种远程服务模式，云端数据在被检索和计算时，有泄露数据的危险。近年来，谷歌邮箱数据泄露，云存储服务商Dropbox账户被盗，苹果云服务iCloud用户照片泄露等事件的发生让人们对云计算的安全性产生了质疑，隐私安全问题严重制约了云计算的发展。通常，保护用户隐私的一种有效方法是加密，但目前大多数加密技术并不支持对密文的计算，因而不能满足云环境下的隐私安全需求。近年来，全同态加密技术发展迅速，它不仅满足传统加密功能，还满足对密文的计算。全同态加密技术支持密文运算、检索、排序，能够保证传输、内存、外存上的安全，被广泛应用于电子股票、医疗、安全多方计算等各个领域。理论上，全同态加密技术很适合解决云环境隐私安全问题。但是基于云环境的复杂性，用户多样性，针对单一数据接收用户的全同态加密方案可能不满足云环境安全需求。

考虑以下场景，公司员工基于他们的部门和员工等级被限制访问公司数据，而该公司选择委托云服务提供商的计算资源来完成公司的大型计算任务，公司中的数据发送者是独立的且不会意识到公司其他数据发送者的存在。为了遵守公司的隐私规范，每个数据发送者必须设定适当的访问策略来加密数据，且员工访问该数据必须满足加密数据认证条件。不同部门员工上传的加密数据之间可能会被发送者的子集或者其他授权人员进行计算或者其他处理。当计算后的数据返回给公司时，只有满足结果数据访问策略的员工才能有资格对结果数据进行访问。

针对上面场景，本文提出基于策略的多用户全同态加密方案(PB-MUFHE)，支持多用户的密文计算以及多用户共享，支持对密文细粒度的访问控制。该方案能够抵制共谋攻击，在LWE困难度假设随机域模型下满足IND-CPA安全，适于解决云环境下的隐私安全问题。

1相关研究工作

全同态加密的含义是在对明文加密后，能够在不解密的情况下，对密文进行任意运算，即对于任意有效的运算f及明文μ，有性质f(Enc(μ))=Enc(f(μ))。若f只满足加法运算或者乘法运算，则称为加法同态或乘法同态，只有同时满足加法同态和乘法同态并且满足紧凑性才能称为全同态。第一个全同态加密方案是Gentry于2009年提出的[1]，之后人们提出了一些全新构造或改进优化的全同态加密方案。

1.1全同态加密方案

文献[1～7]在假设稀疏子集和的前提下，基于压缩技术和同态自解(bootstrapping)技术实现了支持无限次全同态运算的纯(pured)全同态加密，这些方案构造方式复杂，密文计算复杂度高。文献[8～11]在容错学习(learning with error,LWE)问题或环LWE问题假设基础上，基于重线性化技术[8]、模尺寸还原技术[8]、密钥交换技术[9]、模交换技术[9-10]以及张量技术[11-12]等实现了支持多次全同态运算的层次(leveled)全同态加密，这些方案密文计算效率更高，安全性更高，但公钥尺寸大。以上方案的关注点是：密文的全同态运算次数和效率，公钥和密文尺寸大小；并且只设定单独的目标接受者，并不适合上面提到的场景，主要是未考虑在实际应用环境中可能涉及多用户需求，如访问控制、多用户共享以及多用户密文计算等。

1.2支持访问控制和多用户共享的全同态加密方案

文献[12]基于近似特征向量技术实现了层次全同态加密方案，并提出基于身份、属性全同态加密技术以支持多用户共享，满足相同身份、属性密文计算。文献[13]构造了基于访问策略的全同态加密方案，支持多用户共享以及不同用户密文的运算，但该方案构造复杂。文献[14]提出基于身份的纯全同态加密方案，满足多用户共享和不同身份、不同属性密文计算，但该方案严重依赖不可区分性模糊能力，导致效率很低。文献[15]在文献[12]基础上提出基于多身份、多密钥的层次全同态加密方案，满足多用户共享，不同身份密文计算。文献[16]提出构造效率更高的基于身份全同态加密方案，满足了多用户共享以及相同身份密文计算。文献[17]基于密钥共享方式实现了多用户全同态加密，满足多用户共享，该方案采用对称加密方式容易使得密钥泄露。文献[18]基于抽象代数度量空间技术和加密代理技术构造了多用户全同态加密方案，满足多用户共享。

在以上的方案中，基于身份、属性加密方式与全同态加密的结合会更合适，原因在于：密钥共享方式安全性不够，容易串谋；加密代理方式计算开销大；基于身份、属性加密方式开销小，数据机密性好。对于密文计算问题，文献[12～16]提出的方案有两个缺陷：其一，包含属性、身份的密文参与了密文的计算，这些身份、属性信息增大了密文尺寸和公钥尺寸，降低了密文计算效率；其二，可以在未经数据拥有者许可下对任何密文进行计算，这有剽窃用户数据嫌疑。

针对云环境下用户多样性，权衡以上方案的利弊，本文将提出一种基于策略的多用户全同态加密方案。

2问题描述

2.1云环境中支持隐私保护的计算模型

云环境中支持隐私保护的计算模型如图1所示，它反映了数据拥有者、用户、认证中心以及云端之间的交互。模型的具体操作流程如下：

①认证中心使用setup算法生成云计算模型中的公共参数pp和主密钥msk。

②数据拥有者请求认证中心提供加密公钥支持，认证中心使用PubGen算法返回公钥给数据拥有者。数据拥有者使用Enc算法对敏感数据m(i)加密得到密文C(i)。然后将密文C(i)存储到云端。

③用户请求认证中心提供私钥或计算密钥支持，认证中心针对用户使用PrvGen算法返回私钥prvKey给用户。

④用户上传运算符号f，云端根据运算符号，使用Compute算法,对C(i)进行处理，得到结果密文Cresult。

图1　云环境中支持隐私保护的计算模型

⑤用户使用私钥prvKey，根据算法Dec验证解密权限，对Cresult进行解密，得到结果明文result。

在这个过程中，由于数据拥有者对敏感数据进行了加密，使得用户隐私得到保护，且满足密文计算。但这也带来一些新的问题：其一，云服务可以在未经数据拥有者授权情况下对任何密文进行计算处理，这有剽窃用户数据的嫌疑，假如云提供商拥有解密密钥，这相当于云环境下的内部攻击；其二，密文计算是否满足多用户密文计算，这关系到用户需求满意度；其三，该模型应用到大型组织时，对于多用户共享问题，不能很好地解决。因此，本文提出的基于策略的多用户全同态加密方案PB-MUFHE是解决这些矛盾的关键技术。

2.2基于策略的多用户全同态加密方案

定义1基于策略的多用户全同态加密方案基于策略的多用户全同态加密方案εpb-mufhe{Setup, PubGen, PrvGen, Enc, Dec, Compute}是由一组概率多项式时间(PPT)算法组成：

①启动算法Setup为所有用户生成公共参数pp以及主密钥msk, (pp,msk)←Setup(params),params是安全参数；

②公钥生成算法PubGen为数据拥有者生成公钥pubKey, pubKey←PubGen(pp),pp是公共参数；

③密钥生成算法prvGen为用户生成解密密钥prvKey和计算密钥evalKey, (prvKey, evalKey)←prvGen(pp,msk,attrs),attrs为一组属性串；

④加密算法Enc可能为概率算法，D为明文数据的定义域，对于数据μ∈D,C←Enc(pubKey, policy,μ), policy为访问策略，μ为明文数据；

⑤解密算法Dec为确定性算法，对于密文C，μ∪{⊥}←Dec(prvKey,C),⊥表示无解；

⑥密文计算算法Compute可能为概率算法，对于密文集合{C1,C2, …,Cl}, Compute′(Dec(prvKey1,C1), Dec(prvKey2,C2), …, Dec(prvKeyl,Cl),op)←Dec(prvKey, Compute(op,C1,C2, …,Cl, evalKey1, evalKey2, …, evalKeyl)),op为运算符，Compute′是与Compute对应的对明文数据运算的算法。

定义2正确性基于策略的多用户全同态加密方案εpb-mufhe{Setup, PubGen, PrvGen, Enc, Dec, Compute}是正确的：

①∀μ∈D,∃Dec(prvKey, Enc(pubKey, policy,μ))=μ;

②∀{μ1,μ2,…,μl}(μi∈D), ∃Compute′(op,μ1,μ2, …,μl)=Dec(prvKey, Compute(op, Enc(pubKey1, policy1,μ1), Enc(pubKey2, policy2,μ2), …, Enc(pubKeyl, policyl,μl), evalKey1, evalKey2, …, evalKeyl))。

定义3安全性基于策略的多用户全同态加密方案εpb-mufhe{Setup,PubGen, PrvGen,Enc,Dec,Compute}是安全的：

①εpb-mufhe能够抵御共谋攻击；

②εpb-mufhe在LWE困难度假设随机域模型下是IND-CPA安全的。

3基于策略的多用户全同态加密方案(PB-MUFHE)

本文将构造一种基于策略的多用户全同态加密方案(PB-MUFHE)。该方案在确保数据拥有者和用户数据安全的前提下，支持密文的访问控制，多用户密文的加法、乘法运算以及多用户共享。下面详细介绍PB-MUFHE方案。

②PubGen(pp)。首先生成矩阵B←以及向量e←χm。再计算向量b=Bt+e。最后生成矩阵A=(b|B)。输出公钥pubKey=(mpk, Er, A)。

④Enc(pubKey, policy,μ)。该算法的具体步骤如下：

输出密文C= (Ct, Cμ)。

⑤Dec(prvKey,C)。该算法的具体操作步骤如下：

一种熏熏然的气息弥漫于湖畔的绿树之间，是这夏末植物的芬芳与醉湖水波氤氲在一起，令人心神激荡？还是高志明被刚才那股眼波撞击，醉了？

⑥Compute(policy,op,C1,C2, evalKey1, evalKey2)。算法的具体操作步骤如下：

首先调用policyDec算法验证计算密钥evalKey是否满足密文C1和C2的访问控制，满足则解密C1和C2的访问控制密文Ct，得到r1和r2，若不满足，则输出⊥。

4PB-MUFHE的正确性和安全性

定理1PB-MUFHE=(Setup,PubGen, PrvGen, Enc, Dec, Compute)是正确的，如果满足如下条件:

①∀μ∈Zq, ∃Dec(prvKey, Enc(pubKey, policy,μ))=μ;

②∀{μ1,μ2, …,μl∈Zq}，∃Compute′(μ1,μ2, …,μl,op)=Dec(prvKey, Compute(policy,op, Enc(pubKey1, policy1,μ1), Enc(pubKey2, policy2,μ2),…, Enc(pubKeyl, policyl,μl), evalKey1, evalKey2, …, evalKeyl))。

①Dec算法包括两部分：解密访问控制密文Ct和数据密文Cμ，解密Ct是解密Cμ的基础，只有解密Ct正确得到mr，才能正确解密Cμ。

因此，∀μ∈Zq, ∃Dec(prvKey, Enc(pubKey, policy,μ)=μ。

②Compute算法也包括三部分：对密文进行访问控制认证、建立新的访问控制以及密文加法和乘法运算。

对密文进行访问控制认证，由计算密钥evalKeyi对访问密文Ci访问控制部分密文Ct进行解密得到r1,r2, …,rl，该过程和命题(1)的证明过程相同。

综上所述，PB-MUFHE是正确的。

定理2PB-MUFHE是安全的，如果满足如下条件：

①PB-MUFHE能够抵制共谋攻击;

②设q=q(λ,L),m=m(λ,L)=O(nlogq),n=n(λ,L), 错误分布χ=χ(λ,L), PB-MUFHE在LWE困难度假设随机域模型下是IND-CPA安全的。

证明：

因此，PB-MUFHE能够抵制共谋攻击。

②初始游戏，包含一个IND-CPA攻击者A，优势AdvGame[A]表示A在Game中获胜的概率。

因此，PB-MUFHE是IND-CPA安全的。

综上所述，PB-MUFHE是安全的。

5PB-MUFHE的性能分析

本方案测试环境是在32位Ubuntu系统(内存1.5 G，CPU 2.27 GHz)，方案实现采用基于512位有限域的超奇异曲线y2=x3+x上的一个160位的椭圆曲线群作为双线性映射群。

①设参数q=216,n=16,m=256。图2和图3是实验测试数据图，从图2中可以看出，PB-MUFHE的加密时间随着访问策略的复杂而增加，密钥生成时间随着属性的复杂而增加。

②将本文方案中访问策略树中叶子结点个数设为2，密钥中属性个数设为1，根据参数n的取值不同，将本文的PB-MUFHE方案与文献[12]中提出的GSW方案进行加密、解密、密文乘法、加法运算的效率对比，对比结果分别如图4～图7所示。从图中可以看出，GSW方案除了在解密时间上明显优于本文方案外，在加密、加法运算和乘法运算上操作时间之间差距很小。本方案由于具有访问控制功能，效率肯定没有GSW方案高，但可以看出它们之间差距不是很大。

图2PB-MUFHE加密时间随访问策略树复杂度变化图

Fig.2Complexity diagram of PB-MUFHE time encryptionwith access policy tree

图3PB-MUFHE密钥生成时间随密钥中属性个数变化图

Fig.3Changes diagram of PB-MUFHE key generation time with the attribute numbers in the key

综合了以上对本文方案进行的正确性、安全性和操作性能的分析，可以看出本文提出PB-MUFHE方案融合了密文策略-基于属性加密和全同态加密功能，具有如下特点：

①支持对密文的多次加法和乘法同态运算，且满足不同用户之间密文的全同态运算。

②支持对密文细粒度的访问控制，云端加密数据在未授权情况下，对密文的运算将不满足同态性。

③满足多用户共享。

图4GSW方案和本文方案加密时间随参数n的变化图

Fig.4Encryption time comparison of GSW and PB-MUFHE with parametern

图5GSW方案和本文方案解密时间随参数n的变化图

Fig.5Decryption time comparison of GSW and PB-MUFHE with parametern

图6GSW方案和本文方案加法运算时间随参数n的变化图

Fig.6The addition operation time comparison of GSW and PB-MUFHE with parametern

图7GSW方案和本文方案乘法运算时间随参数n的变化图

Fig.7The multiplication operation time comparison of GSW and PB-MUFHE with parametern

本文结合函数加密和全同态加密机制，构造了一种基于策略的多用户全同态加密方案(PB-MUFHE)，有效地解决了云环境中的多用户密文计算、访问控制、多用户共享等问题。在安全性方面，PB-MUFHE方案能够抵制多用户共谋攻击，满足在LWE困难度假设随机域模型下IND-CPA安全性。在性能方面，PB-MUFHE方案能高效地实现密文数据的全同态运算。下一步工作中，首先考虑给方案加入密钥撤销机制，方便有效管理密钥；其次，使用多线性映射技术取代本方案中的双线性映射技术，使得方案有更高效的访问控制；最后将同态自解技术应用到本方案中，提高密文运算次数。

参考文献:

[1]GENTRY C.A fully homomorphic encryption scheme[D]. San Francisco: Stanford University, 2009.

[2]SMART N P, VERCAUTEREN F.Fully homomorphic encryption with relatively small key and ciphertext sizes[C]//Public Key Cryptography-PKC 2010.Germany:Springer Berlin Heidelberg, 2010:420-443.

[3]STEHLE D, STEINFELD R.Faster fully homomorphic encryption[C]//Advances in Cryptology-ASIACRYPT 2010. Germany:Springer Berlin Heidelberg, 2010:377-394.

[4]GENTRY C, SHAI H.Fully homomorphic encryption without squashing using depth-3 arithmetic circuits[C]//2011 52nd Annual IEEE Symposium on Foundations of Computer Science. Palm Spings, CA: IEEE, 2011:107-116.

[5]GENTRY C, HALEVI S, SMART N P.Better bootstrapping in fully homomorphic encryption[C]// Public Key Cryptography-PKC 2012.Germany:Springer Berlin Heidelberg, 2012:1-16.

[6]GENTRY C, HALEVI S.Implementing gentry’s fully-homomorphic encryption scheme[C]// Advances in Cryptology-EUROCRYPT 2011. Germany:Springer Berlin Heidelberg, 2011:129-148.

[7]SMART N P, VERCAUTEREN F.Fully homomorphic SIMD operations[J]. Designs, Codes and Cryptography, 2012, 71(1): 57-81.

[8]BRAKERSKI Z, VAIKUNTANATHAN V.Efficient fully homomorphic encryption from (standard) LWE[C]// Proceedings of the 52nd Annual Symposium on Foundations of Computer Science.Washington DC: IEEE Computer Society, 2011: 97-106.

[9]BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V.(Leveled) fully homomorphic encryption without bootstrapping[C]// Proceedings of the 3rd Innovations in Theoretical Computer Science Conference.NewYork: ACM Press, 2012: 309-325.

[10]汤殿华，祝世雄，王林，杨浩淼，范佳.基于RLWE的全同态加密方案[J]. 通信学报，2014，35(1):173-182.

[11]BRAKERSKI Z.Fully homomorphic encryption without modulus switching from classical GapSVP[C]// Advances in Cryptology-CRYPTO 2012.Germany:Springer Berlin Heidelberg, 2012: 868-886.

[12]GENTRY C, SAHAI A, WATERS B.Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based[C]// Advances in Cryptology-CRYPTO 2013.Germany:Springer Berlin Heidelberg, 2013: 75-92.

[13]CLEAR M, MCGOLDRICK C.Policy-based non-interactive outsourcing of computation using multikey FHE and CP-ABE[C]//2013 International Conference on Security and Cryptography.Reykjavik, Iceland:IEEE, 2013:1-9.

[14]CLEAR M, MCGOLDRICK C.Bootstrappable Identity-based fully homomorphic encryption[C]//Cryptology and Network Security. Germany:Springer Berlin Heidelberg, 2014:1-19.

[15]CLEAR M, MCGOLDRICK C.Multi-Identity and Multi-key Leveled FHE from Learning with Errors[C]// Advances in Cryptology -CRYPTO 2015. Germany:Springer Berlin Heidelberg, 2015:630-656.

[16]光焱，祝跃飞，费金龙，顾纯祥，郑永辉.利用容错学习问题构造基于身份的全同态加密体制[J]. 通信学报，2014，35(2):111-117.

[17]XIAO L L, BASTANI O, YEN I L.An efficient homomorphic encryption protocol for multi-user systems.IACR cryptology ePrint archive[EB/OL]. (2012-01-19)[2016-02-11]. http://eprint.iacr.org/2012/193.

[18]LI T, YE X J, WANG J M.Protecting data confidentiality in cloud systems[C]//The 4th Asia-Pacific Symposium on Internetware (Internetware 2012).New York：ACM Press, 2012:1-12.

(责任编辑梁碧芬)

收稿日期：2015-10-22；

修订日期：2016-01-14

基金项目：国家自然科学基金资助项目(61363067)；广西自然科学基金资助项目(2012GXNSFAA053226)

通讯作者：李陶深(1957—)，男，广西南宁市人，广西大学教授，博士生导师;E-mail: tshli@gxu.edu.cn。

doi:10.13624/j.cnki.issn.1001-7445.2016.0786

中图分类号:TP391

文献标识码:A

文章编号：1001-7445(2016)03-0786-10

Policy-based multi-user full homomorphic encryption method in cloud computing

LIU Qing1, LI Tao-shen1,2, WANG Ru-wei1,2

(1.School of Computer, Electronics and Information, Guangxi University, Nanning 53004, China;2.Guangxi Colleges and Universities Key Laboratory of Parallel and Distributed Computing,Nanning 530004, China)

Abstract:The full homomorphic encryption technology is an effectively way to solve the problem of cloud computing privacy and security. Considering user diversity in cloud environment, a policy based multi-user full homomorphic encryption scheme (PB-MUFHE) is proposed. On the basis of full homomorphic encryption algorithm, the scheme sets appropriate access policy in the encrypted data and sets the attribute in the key, which is not only to meet full homomorphic operation of the multi-user ciphertext and the multi-user share, but also to support for fine-grained access control Security analysis shows that PB-MUFHE can resist collusion attacks, and is proved IND-CPA security in the random fields model under the LWE harder assumption. Performance assessment demonstrates that PB-MUFHE ciphertext can efficiently implement data fully homomorphy operation and effectively support access control and multi-user shared.

Key words:cloud computing; full homomorphic encryption; multi-user; attribute based encryption; ciphertext policy access control

引文格式： 刘青,李陶深,黄汝维.云计算环境中基于策略的多用户全同态加密方法[J].广西大学学报(自然科学版)，2016，41(3)：786-795.