一种基于LWR的属性全同态加密方案

ComputerScienceandApplication计算机科学与应用,2018,8(4),503-511PublishedOnlineApril2018inHans.://doi.org/10.12677/csa.2018.84056文章引用:张兴兰,卢玉顺.一种基于LWR的属性全同态加密方案[J].计算机科学与应用,2018,8(4):503-511.DOI:10.12677/csa.2018.84056Attribute-BasedFullyHomomorphicEncryptionBasedLWRXinglanZhang,YushunLu*DepartmentofInformation,BeijingUniversityofTechnology,BeijingReceived:Apr.4th,2018;accepted:Apr.21st,2018;published:Apr.28th,2018AbstractForthecurrentfully-homomorphicencryptionschemebasedonLWE(LearnWithErrors)struc-ture,Gaussianfunctionsamplingandpublickeysizearegenerallyneeded.ThispaperadoptstheefficientLWR(LearningWithRounding)toreplacethetraditionalLWEschemeandproposeskey-policy-attribute-basedfull-homomorphicencryption(LWR-ABFHE)schemeforend-to-enddataprotectioninmulti-userscloudenvironments.TheLWR-ABFHEschemeproposedinthispa-percanperformhomomorphiccomputingwhileperformingfine-grainedaccesstoencrypteddata,andachievetheeffectofhandlingmonotonicaccessstructuresonasetofauthorizationattributeswithoutsacrificingthecomputationalpowerofhomomorphicencryption.Inthispaper,theIND-CPAsecurityoftheproposedschemeunderLWRassumptionisproved.KeywordsLWR,LWE,Attribute-BasedEncryption,FullyHomomorphicEncryption,MonotonicAccessStructure一种基于LWR的属性全同态加密方案张兴兰，卢玉顺*北京工业大学，信息学部，北京收稿日期：2018年4月4日；录用日期：2018年4月21日；发布日期：2018年4月28日摘要针对目前基于LWE(LearnWithErrors)构造的全同态加密方案普遍需要高斯函数抽样以及公钥尺寸过*通讯作者。张兴兰，卢玉顺DOI:10.12677/csa.2018.84056504计算机科学与应用大等问题，本文采用高效的LWR(LearningWithRounding)替换传统的LWE方案，提出了多用户云环境中提供端到端数据保护的基于密钥策略–属性的全同态加密(LWR-ABFHE)方案。本文提出的LWR-ABFHE方案能够在对加密数据进行细粒度访问的同时执行同态计算，并且在不牺牲同态加密的计算能力情况下，达到在一组授权属性上处理单调访问结构的效果。本文在LWR假设下，证明了LWR-ABFHE方案在选择明文攻击下的安全性。关键词LWR，LWE，基于属性，全同态加密，单调访问结构Copyright©2018byauthorsandHansPublishersInc.ThisworkislicensedundertheCreativeCommonsAttributionInternationalLicense(CCBY).引言随着互联网的快速发展和云计算的普及，人们对数据隐私越来越重视。针对如何保证用户数据的私密性产生了很多加密方案，其中全同态加密占据主流的研究地位。全同态加密(FHE)是一种特殊的加密方案，可以解决云计算、电子商务等安全问题，因为它允许第三方对加密数据进行任何操作，而无需预先解密。2009年CraigGentry[1]实现了第一个全同态加密(FHE)方案，其允许对加密的密文数据执行任何加法和乘法的功能。自Gentry实现第一个全同态加密方案后，FHE方案逐渐成为了研究的热点，至今产生了各种相关的实现及优化。当前研究全同态加密的主流方案是基于LWE困难问题的安全性假设。因为LWE问题理论上可以量子规约到格上的求解SIVP困难问题和GapSVP困难问题，因此认为基于LWE的全同态加密方案具有牢固的安全性保证。2011年Brakerski等[2][3]提出基于LWE问题构造全同态加密方案的思想，方案利用“重线性化”技术实现密文之间的同态运算，但是同态过程需要用到额外的运算公钥evk，导致密文运算复杂而且效率低下；2012年Brakerski等人[4]基于LWE又提出了模不变的全同态方案，省略了模交换技术的消耗，但是该方案在保证安全性的前提下，模数q的取值很大，导致了较高的复杂度；2013年，Gentry[5]在Crypto国际会议中提出利用近似特征向量方法构造全同态加密方案。该方案的优势是密文之间乘积不会导致维数的膨胀，消除了秘钥交换技术。但是密文的同态计算由向量转换为矩阵之间的加法和乘法，计算复杂；文献[6][7]分别提出利用多键和舍弃自举技术等方案在一定程度上改进了全同态方案的效率，但是这些方案基于LWE问题都需要高斯噪声抽样，时间开销很大，计算上也存在瓶颈。所以消除高斯噪声带来的高昂实际代价很有必要，Bogdanov[8]和Costache[9]提出的LWR方案是LWE问题的变体，安全性与LWE问题一样困难，而且LWR问题消除了高斯函数抽样，显著提高了计算效率。为了支持多用户需求，到目前为止所回顾的所有方案都受到这样的事实的影响，即对同态加密方案的引入扩展对计算能力具有负面影响。Xiao等人方案[10]和Lopez方案[11]均通过密钥代理或CSP服务器来实现额外的密钥转换过程。同时，Gentry方案[5]和Clear-McGoldrick方案[12]能够提供对用户属性进行加密的细粒度控制访问。然而，Gentry方案[5]和ClearMcGoldrick方案[12]仅允许用相同属性加密的数据执行计算，因此无法支持多用户设置下的同态加密。尽管Clear-McGoldrick方案[13]能够支持多属性计算，但是它们的方案继承了Lopez方案[11]的性能瓶颈。本文提出的方案与现有的工作[5][11][12][13][14]之间的主要区别是三个方面。首先，利用LWR问题构造基于属性的全同态加密方案，不仅消除OpenAccess张兴兰，卢玉顺DOI:10.12677/csa.2018.84056505计算机科学与应用了高斯噪声抽样和运算秘钥，而且公钥尺寸更加小，具有更加高效的计算效率。其次，与现有的ABHE方案[5][12][13][14]相比，它们仅将其访问结构视为单一属性[5][12]；或者使用单个属性来表示一组“子属性”[13]；所提出的方案使用LSSS矩阵(G，p)在一组属性上表示单调访问结构。最后，所提出的LWR-ABFHE方案不是将同态加密和ABE方案直接融合成单个密文，而是将密文分解为两个子分量。第一个分量用公钥PK对数据进行加密；而第二个组件包含一组授权属性U。同态评估只涉及第一个组件。同时，第二个组件用于细化加密数据的访问控制。用户的秘密密钥SK通过一组授权属性与单调访问结构A关联。单调访问结构中的每个授权属性1A都拥有密钥SK的有效份额。因此，当且仅当1AA∈时，才能正确解密加密数据。另外，为了防止多个用户之间的共谋攻击，所提出的LWR-ABFHE方案扩展了密钥随机化技术[15][16]，以使用户的秘密密钥失效，其中多个用户不能将他们的属性集中在一起并重建一个有效的密钥。2.预备知识本文中用粗体小写字母表示向量，例如r；向量的第i个分量用r[i]表示；向量均以列向量形式表示，向量转置用Tr表示；表示向上取整，表示四舍五入取整；向量范数canx∞表示所有向量元素绝对值中的最大值。文中对数log默认底是2，向量加法和乘法运算均在模q或者模p意义下进行。2.1.LWE和LWR问题定义1.(LWE问题)选取整数n和2q≥，对于选定的向量nqZ∈s和随机均匀选择的向量nqZ←a，输出()1,,nqeZ++∈aas，其中e是服从离散高斯分布的噪音向量。LWE问题的本质就是从上述LWE函数生成的独立样本中恢复向量s。定理1.(LWE问题难解性假设)选取整数n，()mpolyn≤令()()0,1nαα=∈和素数()qqn=满足条件2nqα。如果存在一个攻击者A能够在多项式时间内破解,,,LWEnmqχ问题，则存在一个以nOα为近似因子的有效算法求解格上的GapSVP问题。定义2.(LWR问题)选取整数n，q和p，并且满足1n≥以及qp≥，定义LWR问题(带舍入学习)如下：对向量nqZ∈s，均匀随机选取nqZ←a，输出(),,npqpZZ∈×aas。,,LWRnqp问题的本质是区分若干抽样(),iiab与等量的均匀抽样(),niiqpcdZZ∈×。定理2.假设χ是任意qZ上B有界分布的LWR问题取样，而且χ可以有效的取样。令2Bqp.则对于求解任一分布上snqZ∈的LWR问题，我们认为困难程度等价于求解相同分布上snqZ∈的LWE问题。2.2.访问控制相关概念定义3.(单调访问结构)：令{}12,,,nUuuu=表示一组属性。如果对于任意的B、C满足条件B∈A并且BC⊆，意味着C∈A，则集合U⊆A是单调的。单调访问结构是{}12,,,nuuu的非空子集的单调集合A。A中的集合称为授权集合，而不在A中的集合称为未授权集合。一般来说，在CP-ABE方案中有三种方法来表示布尔公式，访问树和线性秘密共享方案(LSSS)。在本文中，访问策略是基于LSSS方法构建的，因为已经证明LSSS能够表达任何单调访问结构[17]。接下来，LSSS方案定义如下。定义4.线性秘密共享方案(LinearSecret-SharingSchemes(LSSS))：由访问策略形成的线性秘密共享矩阵的每一行对应一个属性值，即行向量与属性值形成一一映射的关系。如果满足以下两个性质，则在{}12,,,nUuuu=集合上的秘密共享方案Π称为线性的(通过qR)：张兴兰，卢玉顺DOI:10.12677/csa.2018.84056506计算机科学与应用1)每个属性的共享秘钥是在qR上形成的一个向量；2)存在Π的秘密共享矩阵，表示为矩阵nmqGR×∈，其中行标签()piU∈，[]in∀∈，给定一个秘密分享列向量()2,,,msrr=v，其中qsR∈是要共享的秘钥并且随机选择2,,mqrrR←，Gv表示根据Π的n个共享秘钥的向量。共享()iiGvδ=，即内积iGv⋅属于属性p(i)，其中p是从{}1,,n到U的函数。LSSS享有如下的线性重构性质[7]。假设Π是一个代表访问机构A的LSSS方案。设C∈A是一个授权的集合，并且{}1,2,,In⊂被定义为(){}:IipiC=∈。存在常数{}iqiIwR∈∈，使得iδ是依据Π的秘钥SK的有效分享，那么iiiIwsδ∈=∑。此外