一种基于LWE的BGN加密及门限加密方案

李菊雁，马春光,2，袁 琪,3

(1. 哈尔滨工程大学计算机科学与技术学院 哈尔滨 150001; 2. 中国科学院信息工程研究所信息安全国家重点实验室 北京 西城区 100093;3. 齐齐哈尔大学通信与电子工程学院 黑龙江 齐齐哈尔 161006)

基于容错学习(learning with error problem, LWE)的密码是一类备受关注的抗量子计算攻击的公钥密码体制[1]。BGN加密方案[2]描述了一种允许任意次加法和一次乘法的密文运算的加密系统，并且在密文的运算中，密文的规模没有增长。文献[3]基于LWE构造了一种简单的BGN加密方案GHV10，GHV10的解密算法需要用到陷门技术[4]。文献[5]构造了一种BGN加密方案，但是基于双线性配对和子集判定假设的。

加密方案BGV12[6]是一种全同态加密方案，加密的明文是比特，密文是向量。因为密文的乘法运算是向量的张量积，所以密文在运算后规模扩大。BGV12利用密钥交换、模转换等技术来控制噪音的增长和密文的规模，从而实现了全同态加密运算。如果为了实现密文的一次乘法运算仍然需要使用这些技术，那么BGV12就显得有些差强人意。本文利用BGV12的加密方案设计了一种变形的加密方案。加密的明文为矩阵(明文打包运算[7])，密文也为矩阵。因为密文的乘法运算是矩阵的乘法，而不是矩阵的张量积，所以密文的规模在运算后没有增大。

文献[8]基于RLWE构造了一种全同态加密算法ZXJXZ14，并扩展成一种门限加密方案。本文依据ZXJXZ14，也将设计BGN加密方案扩展成一种门限加密方案，并且同样能抵抗密钥泄露攻击。

1 预备知识

本文中的数、向量、矩阵分别记为x、x、X，向量的内积记为＜v,u＞，Ik表示k阶单位矩阵，AT表示矩阵A的转置，[k]表示集合{1,2,…,k}。对于概率分布D而言，x←D表示x依概率分布D选取，对于集合S，x←S表示x在集合S上均匀随机选取。||v||∞、||A||∞分别表示向量v及矩阵A中元素最大的量级。表示对数x向下和向上取整，[x]q表示x(modq)，[A]q表示对矩阵A的每一个元素分别模q。规定ℤq=(-q/2,q/2]∩ℤ。

定义 1(LWE问题[9])对于整数q=q(n)，向量上的误差分布χ=χ(n)，选取输出该分布记为As,χ。LWEn,m,q,χ的判定问题为：以不可忽略的优势来区分m个来自As,χ的取样和m个上的均匀随机取样。文献[9]在2005年证明了在量子归约下，LWE问题至少与worst-case的近似因子为(n/α)的SVP、SIVP 的变体一样困难，其中α是LWE实例中与扰动分布的方差有关的参数。文献[10-11]分别给出了从GapSVP到LWE一个经典归约。

定义 2(B界分布[12])对于一个定义在整数上的分布全体{χn}n∈N，如果是可忽略的，则{χn}n∈N称为B界的。

定理 1[12]设q=q(n)∈ℕ为素数的幂或者为不同poly(n)大小的素数的乘积，那么存在一个有效的取样B界分布χ，使得如果存在一个有效的算法解决参数为n,q,χ的一般情况的LWE困难问题，那么：

1)存在一个有效的量子算法在n维格上解决GapSVPO˜(nq/B)；

2)如果q≥(2n/2)，那么存在一个有效的经典算法在n维格上解决GapSVPO˜(nq/B)。

对于这两种情况，如果考虑以亚多项式的优势来区分，那么需要B≥(n)，并且最后的近似因子比(n1.5q/B)略大。

2 BGN加密方案

本节利用BGV12的加密方案设计了一种变形的加密方案。加密的明文为矩阵，密文也为矩阵。因为密文的乘法运算是矩阵的乘法，所以密文的规模在运算后没有增大。又因为该加密方案也支持任意次密文加法运算，所以为BGN加密方案。

2.1 BGN加密方案

BGN加密方案由五元组(E.Setup,E.SecretKeygen, E.PublicKeygen, E.Enc, E.Enc,E.Dec)构成。

初始化阶段E.Setup(1λ,1μ)：适应性地选择μ比特的模q，及参数

引理 1 (安全性)[5]：设参数m,n,q,χ，使得LWEm,n,q,χ成立，那么对任意的如果R∈{0,1}n×n，则(BR,AR)与上的均匀分布计算不可区分。

2.2 同态性

设密文：

则：

1)加法

对于适合的参数有：

2)乘法

2.3 参数设定

定理 2令n为安全参数，任意的设q＞6n2c+6为素数，那么上述加密方案支持密文的nc次加法和一次乘法运算。

证明：先考虑密文C为l≤nc个密文的和，记

因为

下面考虑密文C′为两个密文的乘积，这两个密文分别为l1,l2个密文的和，其中l1+l2≤nc，记

因为：

注：本方案与GHV10[3]相比较，对于任意的c=c(n)＞0，仅要求q＞6n2c+6为素数，而GHV10要求q＞220(c+4)3n3c+4log5n为素数。这意味着如果q的范围扩大，则能支持比c=c(n)＞0更大的运算。

3 扩展成门限加密方案

本节首先介绍密钥同态，然后构造门限加密方案，最后证明该方案能抵抗密钥泄露攻击。

3.1 密钥同态

因为：

3.2 门限加密方案

类似于文献[8]，本文也假设存在一个可信第三方F，F计算结合公钥、密钥，然后把计算后的结果发送给各个参与者(假设共k个参与者)，并同时保证密钥的安全性。为了保证语义安全，本文同样加入了干扰噪音。

密钥生成算法TE.SecretKeygen(1n)：取Si←输出

公钥生成算法 TE.PublicKeygen(S)：取计算Bi=[SiA+2Xi]q，输出

当F从k个参与者中接收到pki后诚实地计算故结合公钥为：

加密算法TE.Enc(pk，M)：对于明文M∈{0,1}n×n及公钥均匀取R∈{0,1}n×n及干扰噪音X*，输出密文

解密算法TE.Dec(sk,C)：各参与者把解密共享发送给F，F诚实地计算并输出明文M。

正确性可由以下运算得出。

3.3 结合密钥的安全性

可以仿照文献[8]的游戏来证明结合密钥的安全性，即攻击者不能以显著优势区分在诚实公钥下的加密密文与均匀选取的假密文，证明省略。

4 结 束 语

本文基于BGV12，设计了一种基于LWE的BGN加密方案。与GHV10比较，有较好的参数规模，即对于任意的c=c(n)＞0，GHV10要求q＞220(c+4)3n3c+4log5n为素数，而本文仅要求q＞6n2c+6为素数。与BGV12比较，因为不再需要用到密钥交换、模转换等技术，一次乘法同态运算更高效。与ZXJXZ14类似，将BGN加密也扩展成一种门限加密方案，允许所有参与者共同解密一个密文而没有泄露明文的任何信息，并且能抵抗密钥泄露攻击。最后值得注意的是，类似于GHV10中的扩展及应用，同样可以把本文的加密方案扩展成身份基加密(也需要利用陷门T)、Two-Out-of-Two加密等。

本文得到信息安全国家重点实验室开放课题(2016-MS-10)的资助，在此表示感谢。

[1]王小云, 刘明洁. 格密码学研究[J]. 密码学报, 2014, 1(1)：13-27.WANG Xiao-yun, LIU Ming-jie. Survey of lattice-based cryptography[J]. Journal of Cryptologic Research, 2014,1(1)： 13-27.

[2]BONEH D, GOHE J, NISSIM K. Evaluating 2-DNF formulas on ciphertexts[C]//Proceedings of Second Theory of Cryptography Conference, TCC 2005. Cambridge, MA,USA： Springer, 2005： 325-341.

[3]GENTRY C, HALEVI S, VAIKUNTANATHAN V. A simple bgn-type cryptosystem from LWE[C]//Proceedings of Advances in Cryptology-EUROCRYPT 2010. Riviera,French： Springer, 2010： 506-522.

[4]MICCIANCIO D, PEIKERT C. Trapdoors for lattices：Simpler, tighter, faster, smaller[C]//Proceedings of Advances in Cryptology-EUROCRYPT 2012. Cambridge, UK：Springer, 2012： 700-718.

[5]ZHANG Wei. A BGN-type multiuser homomorphic encryption scheme[C]//Proceedings of 2015 International Conference on Intelligent Networking and Collaborative Systems. Taipei, Taiwan, China： IEEE, 2005： 268-271.

[6]BRAKERSHI Z, GENTRY C, VAIKUNTANATHAN V.(Leveled)fully homomorphic ncryption without bootstrapping[C]//Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. Cambridge,Massachusetts： ACM. 2012： 309-325.

[7]HIROMASA R, ABE M, OKAMATO T. Packing messages and optimizing bootstrapping in GSW-FHE[C]//Proceedings of Public-Key Cryptography-PKC 2015.Gaithersburg, MD, USA： Springer, 2015： 699-715.

[8]ZHANG Xiao-jun, XU Chun-xiang, JIN Chun-hua, et al.Efficient fully homomorphic encryption from RLWE with an extension to a threshold encryption scheme[J]. Future Generation Computer Systems, 2014(36)： 180-186.

[9]REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]//Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing.Baltimore, MD, USA： ACM, 2005： 84-93.

[10]PEIKERT C. Public-key cryptosystems from the worst-case shortest vector problem[C]//Proceedings of the 41st Annual ACM Symposium on Theory of Computing.New York： ACM, 2009： 333-342.

[11]BRAKERSKI Z, LANGLOIS A, PEIKERT C, et al.Classical hardness of learning with errors[C]//Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing. New York： ACM, 2013： 575-584.

[12]GENTRY C, SAHAIY A, WATERS B. Homomorphic encryption from learning with errors： Conceptually-simpler,asymptotically-faster, attribute-based[C]//Proceedings of Advances in Cryptology-CRYPTO 2013. Santa Barbara,CA, USA： Springer, 2013： 75-92.