标题 | 利用LWR构造基于身份的全同态加密方案 |
范文 | 张兴兰 卢玉顺![]() ![]() ![]() 摘 要:针对目前基于LWE(Learn With Errors)构造全同态加密方案普遍需要高斯函数抽样、公钥尺寸过大等问题,提出利用高效的LWR(Learning With Rounding)替换传统的LWE,构造基于LWR(Learning With Rounding)的身份基全同态加密方案,对方案的安全性进行严格证明。LWR问题是LWE问题的变体,消除了LWE问题利用高斯函数抽样生成噪声的过程,具有更高的计算效率以及更小公钥和密文尺寸。 关键词:LWR;LWE;基于身份;全同态加密;高斯函数 DOIDOI:10.11907/rjdk.181219 中图分类号:TP309.7 文献标识码:A 文章编号:1672-7800(2018)010-0200-04 英文摘要Abstract:In order to solve the problem that the LWE-based fully homomorphic encryption scheme generally needs samples of Gaussian function and oversized public key,a new LWR (Learning With Rounding) algorithm is proposed to replace the traditional LWE problem and construct a LWR With Rounding,and the safety of the program is strictly proved.The LWR problem is a variant of the LWE (Learn With Errors) problem,which eliminates the process of generating noise of LWE in using Gaussian function. The sampling has higher computational efficiency and public key and ciphertext is of smaller size. 英文关键词Key Words:LWR; LWE; identity-based encryption; fully homomorphic encryption; Gaussian noise sampling 0 引言 随着互联网技术的快速发展和云计算的普及,人们对数据隐私的保护越来越重视。针对如何保证用户数据的私密性有很多加密方案,其中全同态加密占据主流的研究地位。全同态加密(FHE)是一种特殊的加密方案,可以解决云计算、电子商务等安全问题。它允许第三方对加密数据进行任何操作而无需预先解密。Craig Gentry[1]于2009年实现了第一个真正意义上的全同态加密(FHE)方案,该方案允许对密文数据执行任何加法和乘法功能。 自Gentry实现第一个全同态加密方案后,FHE方案逐渐成为研究热点,至今产生了各种方案。当前研究全同态加密主体思路是基于LWE的安全性假设。因为LWE理论上可以规约到格上求解SIVP和GapSVP问题,因此基于LWE的全同態加密方案具有牢固的安全保证。2011年Brakerski等[2-3]采用基于LWE的思想构造全同态加密方案,方案使用“重线性化”方法实现密文之间的同态加法和乘法运算。但同态过程需用到额外的同态计算公钥evk,导致密文计算复杂且效果不佳;2012年Brakerski[4]基于LWE提出了模q不变的全同态方案,省略了模数转换技术的消耗,但欲保证安全,该方案模数q的取值很大,导致较高的复杂度;2013年,Gentry[5]在Crypto国际会议中提出利用近似特征向量方法构造FHE方案。该方案的优势是密文之间乘积不会导致维数扩张,消除了秘钥交换技术。但是密文的同态计算为向量转换为矩阵之间的加法和乘法,计算复杂;文献[6,9]分别提出利用多键和舍弃自举技术等方案,在一定程度上改进了全同态方案效率,但这些方案基于LWE问题都需高斯噪声抽样,时间开销大,计算上也存在瓶颈。Bogdanov[7]提出的LWR问题是LWE问题的变体,安全性与LWE问题一样困难,而且LWR问题消除了高斯函数抽样,显著提高了计算效率,Fang等[10]基于LWR构造了身份基加密方案。 基于id的加密方案(IBE)是使用用户id作为唯一的标记来生成主公钥,用户的私钥由第三方机构利用主私钥和身份id生成,从而消除了公钥证书的相关计算开销,可更加有效地管理秘钥sk,减小sk尺寸。文献[11-16]都是基于id构造改进的全同态加密方案,然而这些思想是LWE问题的困难性假设,时间效果存在瓶颈。COSTACHE等[8]基于LWR构造了分级FHE方案,优势是更小的公钥和密文长度,以及更小的计算模数,但在密文计算同态运算时需要运算秘钥evk,导致较高的时间代价。本文提出了利用LWR困难假设构造基于id的全同态加密方案,首先构造了高效的基于LWR的IBE方案,然后基于特征向量思想,将该高效LWR-IBE方案转化为基于身份的全同态加密方案,不仅消除了高斯噪声抽样和运算秘钥,而且公钥尺寸更小,加解密过程更加高效。 1 预备知识 3 效率分析 本文提出的LWR-IBE方案比传统的基于LWE问题构造的IBE方案具有更小的公钥尺寸和密文尺寸。借鉴Wang等[12]采用高效的陷门生成算法构造身份id,消除了加密过程LWE进行高斯函数抽样的高昂时间开销,比Wang等[12]有更高效的加解密效率。 基于LWR-IBE构造的LWR-IBFHE方案,借鉴光焱等[16]提出的利用LWE问题构造基于id的FHE体制,以及COSTACHE等[8]采用LWR构造的无高斯噪声的加密方案。但光焱等[16]的方案中,秘钥生成过程采用了陷门矩阵的逆运算,光焱等[16]和COSTACHE等[8]的方案中同态计算过程用到了同态运算秘钥evk,这些都导致方案的低效。本文方案利用特征向量的方法,摒弃了运算秘钥,使计算复杂度降低。因为本文方案的密文都是矩阵,因此密文的乘积不会导致密文维数增大,具有更低的复杂度和更高的效率。 4 结语 基于容错学习的全同态加密方案是研究热点,但这类方案隐含的公钥尺寸过大和代价高昂的高斯噪声抽样成为影响其效率的瓶颈。本文提出的基于LWR的LWR-IBFHE方案,依据用户id加密,有效避免了和id相关的计算开销,带舍入学习问题的构造在保证安全性的基础上降低了公钥尺寸,计算效率更高。 本文提出的设计方案局限性在于仅证明了选择明文下的安全性,而在云计算越来越普及的环境下,如何设计满足密文安全的加密方案尤为重要,文献[17]、[18]提出了CCA1下安全的FHE方案构想。本方案实现了满足同一身份id的同态计算,今后将进一步研究多身份id的密文同态计算,以及构造CCA1安全的身份基全同态加密方案。 参考文献: [1] GENTRY C.A fully homomorphic encryption scheme[M].Stanford: Stanford University Press,2009. [2] BRAKERSKI Z,VAIKUNTANATHAN V.Fully homomorphic encryption from ring-LWE and security for key dependent messages[C].Cryptology Conference,2011:505-524. [3] BRAKERSKI Z,VAIKUNTANATHAN V.Efficient fully homomorphic encryption from (Standard) LWE[C].Foundations of Computer Science.IEEE,2011:97-106. [4] BRAKERSKI Z.Fully homomorphic encryption without modulus switching from classical gapSVP[J].Lecture Notes in Computer Science,2012(7417):868-886. [5] GENTRY C,SAHAI A,WATERS B.Homomorphic encryption from learning with errors:conceptually-simpler,asymptotically-faster,attribute-based[C].Advances in Cryptology-CRYPTO 2013.Springer Berlin Heidelberg,2013:75-92. [6] CLEAR M,MCGOLDRICK C.Multi-identity and multi-key leveled FHE from learning with errors[C].Advances in Cryptology -- CRYPTO 2015.Springer Berlin Heidelberg,2015:630-656. [7] BOGDANOV A,GUO S,MASNY D,et al.On the hardness of learning with rounding over small modulus[C].Proceedings,Part I,of the 13th International Conference on Theory of Cryptography,2016:209-224. [8] COSTACHE A,SMART N P.Homomorphic encryption without Gaussian noise[EB/OL].[2017-03-16].https://eprint.iacr.org/2017/163.pdf. [9] BRAKERSKI Z,GENTRY C,VAIKUNTANATHAN V.(Leveled) Fully homomorphic encryption without bootstrapping[J].Acm Transactions on Computation Theory,2014,6(3):1-36. [10] FANG F,LI B,LU X,et al.Hierarchical identity-based encryption from learning with rounding over small modulus[C].ACM on Asia Conference on Computer & Communication Security,2016:907-912. [11] AGRAWAL S,DAN B,BOYEN X.Efficient lattice (H)IBE in the standard model[C].International Conference on Theory and Application of Cryptographic Techniques ,2010:553-572. [12] WANG J,WANG C.Full secure identity-based encryption scheme over lattices in the standard model[C].International Conference on p2p,Parallel,Grid,Cloud and Internet Computing,2016:412-415. [13] 王威力,胡斌,趙秀凤.一种高效的多身份全同态加密方案[J].山东大学学报:理学版,2017,52(5):85-94. [14] 汤永利,胡明星,刘琨,等.新的格上基于身份的全同态加密方案[J].通信学报,2017,38(5):39-47. [15] HE J,LI B,LU X,et al.KDM and selective opening secure IBE based on the LWE problem[C].ACM International Workshop on Asia Public-Key Cryptography.ACM,2017:31-42. [16] 光焱,祝跃飞,费金龙,等.利用容错学习问题构造基于身份的全同态加密体制[J].通信学报,2014(2):111-117. [17] YASUDA S,KITAGAWA F,TANAKA K.Constructions for the IND-CCA1 secure fully homomorphic encryption[EB/OL].http://www.doc88.com/p-6803897907202.html [18] RAN C,RAGHURAMAN S,RICHELSON S,et al.Chosen-ciphertext secure fully homomorphic encryption[EB/OL].http://www.docin.com/p-1518991708.html (责任编辑:杜能钢) |
随便看 |
|
科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。