基于环上容错学习和GSW的层次型全同态加密方案

摘要：针对目前全同态加密方案效率不高的问题，对GSW同态加密方案进行改进，提出基于环上容错学习和GSW的层次型全同态加密方案。首先，构造基于环上容错学习困难问题的基本公钥加密方案，利用近似特征向量方法使其具有加法、乘法同态性，进一步为简化噪声增长过程的分析而引入随机化函数技术；其次，证明了基本加密方案的正确性、安全性，并详细分析了同态加法、同态乘法和同态与非门操作的正确性；最后，根据密文对应噪声项的增长情况及困难问题的安全性设置方案安全参数，并利用快速傅里叶变换降低多项式乘法运算的计算复杂度，构造出层次型（Leveled）全同态加密方案。与GSW方案相比，新方案具有更小的公钥尺寸，且同态计算每个与非门的复杂度从（（nL）2.37）降低到（nL2）。

关键词：全同态加密；环上容错学习；随机化函数；噪声增长；层次型全同态

中图分类号：TP309.7 文献标志码：A

0引言

云存储与云计算平台的快速发展使用户可以外包存储、计算自身的数据，这样用户就能够节省投资费用，简化复杂的设置和管理任务。然而，私密信息、有价值的商业数据泄露成为其发展的一大障碍。全同态加密方案的提出为解决这个问题提供了一个途径。但目前的全同态加密方案复杂度较高，并不实用，这就要求提出效率更高更加实用的全同态加密方案。

全同态加密可以使接收到加密数据的第三方服务器（即云端）在加密数据上进行任意计算，而所得结果进行解密恰为加密数据对应明文进行相应计算的结果。2009年Gentry[1]提出了第一个基于理想格全同态的构想蓝图，在理论上实现了全同态；但构造复杂，效率很低。2010年van Dijk等[2]在Gentry的构造框架下，利用压缩解密电路技术提出基于整数的全同态加密方案――DGHV（DjikGentryHaleviVaikuntanathan），公钥长度为（λ10），复杂度较高。2012年Brakerski等[3]提出了基于GLWE（General Learning With Error）困难问题的层次型全同态加密方案，在新的构造中无需自举技术（bootstrapping），可同态地计算先验深度为多项式尺寸的电路。文献[3]中安全性基于环上容错学习问题（Ring Learning With Error， RingLWE）的方案可同态计算深度为L的算术电路，而每个门的计算复杂度仅仅为（λ・L3）；然而重线性化技术的使用代价较大，影响方案的效率。

2013年Gentry等[4]提出概念更为简单、渐进速度更快的基于容错学习（Learning With Error， LWE）问题的同态加密方案――GSW（GentrySahaiWaters）。不使用重线性化技术、密钥交换技术和模交换技术，提出新的近似特征向量技术。此方案构造的同态乘法不是二次增长型乘法，密文维数不会随同态运算次数的增加而增加。这里的同态乘法是自然的矩阵乘法，密文维数和最初密文维数相等且经过同态运算后的密文与原来的密文具有相同的形式。该方案不需要同态计算公钥，仅仅获取方案的基本参数就可对加密数据进行同态运算。这种优越性使得可以构造出第一个基于身份的全同态加密方案，这也为构造基于属性的全同态加密方案提供了思路。

2014年Brakerski等[5]进一步挖掘出GSW加密方案中，同态矩阵乘法新产生密文所对应的噪声为e1+poly（n）・e2，是以一种非对称的方式增长。这种噪声增长方式提供了一种同态地计算NC1电路的方法，使得方案可以同态计算本身的解密电路，但置换分支程序模拟电路的方法使同态运算次数变多，即同态解密变复杂。同年，AlperinSheriff等[6]提出噪声项随机均匀取自亚高斯分布的对称加密方案，本质上为GSW方案更为简单的变型。平化技术（flattening）使得GSW方案产生的密文矩阵的输入值为0或1，而文献[6]方案产生的密文矩阵的输入值为Zq中任意数，扩大了密文空间；并且构造随机化函数将其应用到对称加密方案以及同态乘法中，可在同态乘法运算的同时重随机化运算结果对应的噪声项。这样可更直观地更紧地分析噪声的增长情况，随后仅用循环群的知识提出新的快速自举方法。

本文在文献[6]提出的同态方案的基础上构造公钥加密方案，新的方案是基于RingLWEGSW的加密方案。环上的容错学习问题是容错学习问题的代数变形，困难程度相当但具有更好的性质。改进的方案提高了原GSW方案同态运算效率，变型后的同态加密方案更为简单，实际效率更高；同时证明了方案的正确性和安全性，给出了基于基本方案的同态加法运算，定义新的同态乘法运算，构造同态与非门运算，并证明了这三种运算同态解密的正确性；最后，分析噪声随同态运算增加而增长的情况，设置适合方案的参数，构造出层次型（leveled）全同态加密方案，并与DGHV和GSW方案进行比较。

4方案参数设置及效率

考虑方案的效率及安全性因素，本文将分圆多项式次数n作为方案重要安全参数。因为q/B是安全规约因子，不可设置其关于n是指数级别的[13]。以及考虑到同态操作L层后得到密文可以正确解密，设置模数时将与L有关。若需构造L层全同态加密方案则根据密文噪声增长情况（2nl+1）LB′

在GSW方案中，同态加密每个门的复杂度为（（nL）ω），其中ω

5结语

新方案构造思路基于GSW，并利用了文献[6]中分析同态乘法噪声增长的方法，构造出基于环上容错学习问题（RingLWE）的层次型全同态加密方案。新方案的效率较GSW有所提高，每个门的计算复杂度降低，但层次型全同态加密方案可以计算的电路深度是先验的，并不能够同态地计算任意运算。构造一个纯的可以同态计算任意电路的全同态加密方案成为今后研究的重难点。

参考文献：

[1]

GENTRY C. Fully homomorphic encryption using ideal lattices [C]// STOC 2009： Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York： ACM， 2009： 169-178.

[2]

van DIJK M， GENTRY C， HALEVI S， et al. Fully homomorphic encryption over the integers [C]// EUROCRYPT 2010： Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2010： 24-43.

[3]

BRAKERSKI Z， GENTRY C， VAIKUNTANATHAN V.（Leveled） fully homomorphic encryption without bootstrapping [J]. ACM Transactions on Computation Theory， 2014， 6（3）： Article No. 13.

[4]

GENTRY C， SAHAI A， WATERS B. Homomorphic encryption from learning with errors： conceptuallysimpler， asymptoticallyfaster， attributebased [C]// CRYPTO 2013： Proceedings of the 33rd Annual Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2013： 75-92.

[5]

BRAKERSKI Z， VAIKUNTANATHAN V. Latticebased FHE as secure as PKE [C]// ITCS 14： Proceedings of the 5th Conference on Innovations in Theoretical Computer Science. New York： ACM， 2014：1-12.

[6]

ALPERINSHERIFF J， PEIKERT C. Faster bootstrapping with polynomial error[C]// CRYPTO 2014： Proceedings of the 34th Annual Cryptology Conference on Advances in Cryptology. Piscataway， NJ： IEEE， 2014： 297-314.

[7]

NAEHRIG M， LAUTER K， VAIKUNTANATHAN V. Can homomorphic encryption be practical？ [C]// CCSW11： Proceedings of the 3rd ACM Workshop on Cloud Computing Security Work Shop. New York： ACM， 2011：113-124.

[8]

MICCIANCIO D， PEIKERT C. Trapdoors for lattices： simpler， tighter， faster， smaller[C]// EUROCRYPT 2012： Proceedings of the 31st Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2012：700-718.

[9]

LYUBASHEVSKY V， PEIKERT C， REGEV O. On ideal lattices and learning with errors over rings [J]. Journal of the ACM， 2013， 60（6）： Article No. 43.

[10]

MICCIANCIO D. Generalized compact knapsacks， cyclic lattices， and efficient oneway functions [J]. Computational Complexity， 2007， 16（4）： 365-411.

[11]

REGEV O. The learning with errors problem [C]// Proceedings of the 2012 IEEE 27th Conference on Computational Complexity. Piscataway， NJ： IEEE， 2010， 41（3）：191-204.

[12]

BRAKERSKI Z. Fully homomorphic encryption without modulus switching from classical GapSVP [C]// CRYPTO 2012： Proceedings of the 32nd International Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2012： 868-886.

[13]

陈智罡， 王箭， 宋新霞. 全同态加密研究[J]. 计算机应用研究， 2014， 31（6）： 1624-1631.（CHEN Z G， WANG J， SONG X X. Survey on fully homomorphic encryption [J]. Application Research of Computers， 2014， 31（6）： 1624-1631.）

[14]

汤殿华， 祝世雄， 王林， 等. 基于RLWE的全同态加密方案[J]. 通信学报， 2014， 35（1）： 173-182.（TANG D H， ZHU S X， WANG L， et al. Fully homomorphic encryption scheme from RLWE[J]. Journal on Communications， 2014， 35（1）：173-182.）

[15]

BRAKERSKI Z， VAIKUNTANATHAN V. Fully homomorphic encryption from RingLWE and security for key dependent messages[C]// CRYPTO 2011： Proceedings of the 31th International Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2011：505-524.

[16]

REGEV O. On lattices， learning with errors， random linear codes， and cryptography [C]// STOC 2005： Proceedings of the 37th Annual ACM Symposium on Theory of Computing. New York： ACM， 2005： 84-93.

Background

This work is partially supported by the Guangxi Natural Science Foundation （2013GXNSFBB053005）， the Guangxi Development Plan of Science and Technology （14124004410）， the Innovation Project of Guangxi Graduate Education （XJYC2012020）， the Project of Guangxi Information and Science Center （201512）.

WANG Zhao， born in 1990， M. S. candidate. Her research interests include fully homomorphic encryption.

DING Yong， born in 1975， Ph. D.， professor. His research interests include information security， cryptology.

WANG Huiyong， born in 1977， Ph. D. candidate， lecturer. His research interests include publickey cryptology， network information security.