无高斯噪声的全同态加密方案

李明祥，刘 照，张明艳

(1.河北金融学院 金融研究所，河北 保定 071051；2.河北省科技金融重点实验室，河北 保定 071051； 3.河北省科技金融协同创新中心，河北 保定 071051)

无高斯噪声的全同态加密方案

李明祥1,2*，刘 照1,3，张明艳1,3

(1.河北金融学院 金融研究所，河北 保定 071051；2.河北省科技金融重点实验室，河北 保定 071051； 3.河北省科技金融协同创新中心，河北 保定 071051)

基于带舍入学习(LWR)问题，一个分级全同态加密方案最近被提出。LWR问题是带误差学习(LWE)问题的变型，但它省掉了代价高昂的高斯噪声抽样，因此与现有基于LWE问题的全同态加密方案相比，该基于LWR问题的全同态加密方案具有更高的计算效率。然而，该基于LWR问题的全同态加密方案在同态运算时需要输入用户的运算密钥。因此，基于LWR问题构造了一个新的分级全同态加密方案，该方案在同态运算时不需要输入用户的运算密钥。鉴于所提方案可应用于构造基于身份的全同态加密方案、基于属性的全同态加密方案等，它具有比最近所提出的基于LWR问题的全同态加密方案更广泛的应用场景。

全同态加密；分级全同态加密；带舍入学习问题；带误差学习问题；高斯噪声抽样

0 引言

在RSA(Rivest, Shamir, Adelman)公钥密码系统提出后不久，人们就提出了全同态加密(Fully Homomorphic Encryption, FHE)体制的思想[1]。在全同态加密体制中，有Dec(f(Enc(μ1),Enc(μ2),…,Enc(μk)))=f(μ1,μ2,…,μk)，其中f为任意函数/电路。在分级全同态加密(leveled FHE)体制中，系统参数不仅依赖于安全参数λ还依赖于电路深度L∈Z+。借助于全同态加密体制，人们可把计算外包给不可信的服务器，而不必担心个人隐私泄露问题。

2009年Gentry[2]基于格理论构造了第一个全同态加密方案。2011年Brakerski等[3]基于环上带误差学习(ring Learning With Errors, ring-LWE)问题[4]构造了一个全同态加密方案；Brakerski等[5]基于LWE问题[6]又构造了一个全同态加密方案。2012年Brakerski等[7]基于环上LWE问题构造了一个高效的分级全同态加密方案。2013年Gentry等[8]基于LWE问题构造了一个简单自然的分级全同态加密方案。

Banerjee等[9]在Eurocrypt 2012上定义了带舍入学习(Learning With Rounding, LWR)问题以及环上LWR(ring-LWR)问题，并在一定参数条件下给出了从LWE问题到LWR问题的归约，以及从环上LWE问题到环上LWR问题的归约。LWR问题是LWE问题的变型，它们的区别主要在于LWE问题需要进行高斯噪声抽样，而LWR问题不需要进行高斯噪声抽样。后来，Bogdanov等[10]又改进了从LWE问题到LWR问题的归约。目前，人们基于LWR问题已构造了一些公钥密码方案，如公钥加密方案[11]、身份基加密方案[12]等。

人们基于LWE问题已构造了许多全同态加密方案[3, 5, 7-8]，然而这些方案都需要进行高斯噪声抽样。因为高斯噪声抽样的计算开销很大，所以高斯噪声抽样是制约这些方案计算性能的瓶颈因素。而LWR问题无需进行高斯噪声抽样，故基于LWR问题构造全同态加密方案，从而摒弃耗时的高斯噪声抽样，不失为改善全同态加密方案计算性能的一条有效途径。因为LWR问题是LWE问题的变型，所以可比照现有基于LWE问题的全同态加密方案，而构造基于LWR问题的全同态加密方案。

最近，Costache等[13]比照Brakerski等[7]提出的方案构造了一个基于环上LWR问题的分级全同态加密方案。Costache等之所以比照Brakerski等[7]提出的方案，主要是考虑到在基于LWE的全同态加密方案中，Brakerski等[7]所提方案的计算效率是比较高的。在基于LWE的全同态加密方案中，Gentry等[8]所提方案适用于比较多的场合，例如：基于Gentry等[8]提出的方案，人们构造了身份基全同态加密方案[14-17]、多密钥全同态加密方案[18-19]等；基于多密钥全同态加密方案[18-19]，研究者们又进一步构造了属性基全同态加密方案[20-21]。故而本文基于Gentry等[8]提出的方案构造了一个基于LWR问题的分级全同态加密方案。Gentry等[8]所提方案之所以比其他全同态加密方案适用于更多场合，主要是因为它在同态运算时不需要运算密钥evk参与，而其他全同态加密方案在同态运算时都需要运算密钥evk协助。本文所构造的全同态加密方案亦不需要运算密钥evk，因此基于本文所构造的方案，可以进一步构造身份基全同态加密方案、多密钥全同态加密方案以及属性基全同态加密方案等。

1 预备知识

1.1 困难问题

定义2B有界分布。一族Z上的分布{Xn}n∈N，如果Pre←Xn[|e|>B]≤negl(n)，其中B=B(n)，则称它为B有界分布。

对于从LWE问题到LWR问题的归约，Bogdanov等[10]又给出了一个比定理2更佳的归约结果。

1.2 向量分解技术

向量分解技术能保持向量的內积不发生变化。它包括以下转换操作：

对上述这些操作来说，显然有:

①〈BitDecompq(x),PowersOfTwoq(y)〉=〈x,y〉；

许多全同态加密方案[7-8, 25]都应用了向量分解技术。

1.3 密码定义

一个分级全同态加密方案包括密钥生成KeyGen、加密Enc、解密Dec和同态运算Eval四个多项式时间算法。其中，(pk,sk)←KeyGen(1λ,1L)输入安全参数λ和电路深度L，输出公钥pk和私钥sk；c←Enc(pk,μ)应用公钥pk加密消息μ∈{0,1}生成密文c；μ←Dec(sk,c)应用私钥sk解密密文c恢复消息μ∈{0,1}；cf←Eval(f,c1,c2,…,ck)输入电路f:{0,1}k→{0,1}和密文c1,c2,…,ck，输出密文cf。

通常，f为有限域GF(2)上的算术电路，只包含加法门和乘法门两种门电路，因而人们习惯上把Eval分成同态加法cadd←Add(c1,c2)和同态乘法cmult←Mult(c1,c2)。

分级全同态加密方案的标准安全性为语义安全性，即在选择明文攻击下的不可区分性(INDistinguishability under Chosen Plaintext Attack, IND-CPA)。

定义3 紧致性。如果一个分级全同态加密方案的解密电路不依赖于运算函数f，则称它是紧致的。

2 基础加密方案

首先，基于LWR问题构造一个标准公钥加密方案。

2.1 构造

Enc(pk,μ∈{0,1})：对于消息μ∈{0,1}，均匀选择矩阵R←{0,1}N×m，并输出密文C，即:

C=(Flattenp((μ·Il2|0)T+BitDecompp(R·uT))|

2.2 正确性

在密钥生成算法KeyGen中，有:

2.3 安全性

定理3 假设LWR问题是难解的，那么上述加密方案是IND-CPA安全的。

证明 考虑下列游戏，其中AdvGamei(A)代表敌手A在游戏i中的优势。

Game 0 该游戏为标准的IND-CPA游戏。

在Game 2中，挑战者所给出的公钥和密文都是均匀随机的，且与消息μ∈{0,1}无关，因此AdvGame 2(A)=0。故在Game 0中有AdvGame 0(A)≤nelg(λ)。即在LWR问题难解的假设下，上述加密方案满足IND-CPA安全性要求。

3 同态运算

接下来，分析有限域GF(2)上的同态加法和同态乘法运算。

1)Add(C1,C2)：输出密文C1与C2的和Cadd，即:

Cadd=(Flattenp(Cadd,p)|Flattenq(Cadd,q))=

(Flattenp(C1,p+C2,p)|Flattenq(C1,q+C2,q))

2)Mult(C1,C2)：输出密文C1与C2的积Cmult，即:

Cmult=(Flattenp(Cmult,p)|Flattenq(Cmult,q))=

(Flattenp(C1·C2,p)|Flattenq(C1·C2,q))

Cadd·zT=(Flattenp(C1,p+C2,p)|

Flattenq(C1,q+C2,q))·(zp,zq)T=

(C1,p+C2,p)·zpT+(C1,q+C2,q)·zqT=

(C1,p·zpT+C1,q·zqT)+(C2,p·zpT+C2,q·zqT)=

Cmult·zT=(Flattenp(C1·C2,p)|

Flattenq(C1·C2,q))·(zp,zq)T=

C1·C2,p·zpT+C1·C2,q·zqT=

C1·(C2,p·zpT+C2,q·zqT)=C1·C2·zT=

根据定理2知道，在LWRn,q,p问题中有q≥p·B·nω(1)。为正确解密Cf，有p≥8(N+1)L·E，所以q≥8(N+1)L·E·B·nω(1)，即q/B≥8(N+1)L·E·nω(1)。又LWEn,q,X问题在q/B=2o(n)时，仍旧是难解的[27]，所以有L=o(n)，即L为多项式深度。即在LWRn,q,p问题难解的假设下，存在分级全同态加密方案。

4 性能比较

Costache等[13]提出的基于环上LWR的全同态加密方案，是比照Brakerski等[7]的基于环上LWE的全同态加密方案构造的。在Brakerski等[7]的方案中，不仅要生成公钥，还要生成同态运算密钥evk。而evk是对私钥进行加密的结果，其不能由用户的身份信息计算出来，因此，由Brakerski等[7]的方案无法进而构造身份基全同态加密方案等。本文提出的基于LWR的全同态加密方案，是比照Gentry等[8]的基于LWE的全同态加密方案构造的。在Gentry等[8]的方案中，不需要生成同态运算密钥evk。基于此，基于Gentry等[8]的方案能进而构造身份基全同态加密方案等。目前人们基于Gentry等[8]的全同态加密方案，已构造了身份基全同态加密方案[14-17]、多密钥全同态加密方案[18-19]和属性基全同态加密方案[20-21]等。因此Gentry等[8]的全同态加密方案比Brakerski等[7]的全同态加密方案应用场合更多。Costache等[13]所提的全同态加密方案亦要生成同态运算密钥evk，因此由Costache等[13]所提方案亦无法进而构造身份基全同态加密方案等。本文所提的全同态加密方案亦不需要生成同态运算密钥evk，由此基于本文所提方案亦能进而构造身份基全同态加密方案、多密钥全同态加密方案和属性基全同态加密方案等。因此本文所提方案比Costache等[13]所提方案应用场合更多。

5 结语

本文借鉴Gentry等[8]的全同态加密方案，构造了一个基于LWR的分级全同态加密方案，并证明了它的正确性、IND-CPA安全性和紧致性。目前Costache等[13]参照Brakerski等[7]的全同态加密方案，已构造了一个基于环上LWR的分级全同态方案。本文所提方案比Costache等[13]的方案应用场合更多。不过，由于Gentry等[8]的全同态加密方案比Brakerski等[7]的全同态加密方案的计算效率差一些，故而本文所提方案比Costache等[13]的方案的计算效率也差一些。因此，下一步致力于：1)以本文所构造的方案为基础，构造基于LWR问题的身份基分级全同态加密方案、多密钥分级全同态加密方案和属性基分级全同态加密方案；2)利用有关全同态加密性能优化技术，提高本文所构造的方案的计算性能。

References)

[1] RIVEST R L, ADLEMAN L, DERTOUZOS M L. On data banks and privacy homomorphisms [M]// Foundations of Secure Computation. Salt Lake City, UT: Academic Press, 1978: 169-179.

[2] 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.

[3] BRAKERSKI Z, VAIKUNTANATHAN V. Fully homomorphic encryption from ring-LWE and security for key dependent messages [C]// CRYPTO 2011: Proceedings of the 2011 Annual International Cryptology Conference, LNCS 6841. Berlin: Springer, 2011: 505-524.

[4] LYUBASHEVSKY V, PEIKERT C, REGEV O. On ideal lattices and learning with errors over rings [C]// EUROCRYPT 2010: Proceedings of the 2010 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 6110. Berlin: Springer, 2010: 1-23.

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

[6] 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.

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

[8] GENTRY C, SAHAI A, WATERS B. Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based [C]// CRYPTO 2013: Proceedings of the 33rd Annual Cryptology Conference, LNCS 8042. Berlin: Springer, 2013: 75-92.

[9] BANERJEE A, PEIKERT C, ROSEN A. Pseudorandom functions and lattices [C]// EUROCRYPT 2012: Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 7237. Berlin: Springer, 2012: 719-737.

[10] BOGDANOV A, GUO S Y, MASNY D, et al. On the hardness of learning with rounding over small modulus [C]// Proceedings of the 2016 13th International Conference on Theory of Cryptography, LNCS 9562. Berlin: Springer, 2016: 209-224.

[11] DUAN R, GU C X. Public key encryption schemes based on learning with rounding problem [C]// MINES 2013: Proceedings of the 2013 5th International Conference on Multimedia Information Networking and Security. Washington, DC: IEEE computer society, 2013: 101-104.

[12] FANG F Y, LI B, LU X H, et al. (Deterministic) hierarchical identity-based encryption from learning with rounding over small modulus [C]// ASIA CCS 2016: Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security. New York: ACM, 2016: 907-912.

[13] COSTACHE A, SMART N P. Homomorphic encryption without Gaussian noise [EB/OL]. [2017- 04- 16]. https://eprint.iacr.org/2017/163.pdf.

[14] WANG F Q, WANG K P, LI B. An efficient leveled identity-based FHE [C]// NSS 2015: Proceedings of the 9th International Conference on Network and System Security, LNCS 9408. Berlin: Springer, 2015: 303-315.

[15] 康元基,顾纯祥,郑永辉,等.利用特征向量构造基于身份的全同态加密体制[J].软件学报,2016,27(6):1487-1497.(KANG Y J, GU C X, ZHENG Y H, et al. Identity-based fully homomorphic encryption from eigenvector [J]. Journal of Software. 2016, 27(6): 1487-1497.)

[16] 段然,顾纯祥,祝跃飞,等.NTRU格上高效的基于身份的全同态加密体制[J].通信学报,2017,38(1):66-75.(DUAN R, GU C X, ZHU Y F, et al. Efficient identity-based fully homomorphic encryption over NTRU [J]. Journal on Communications, 2017, 38(1): 66-75.)

[17] 戴晓明,张薇,郑志恒,等.基于容错学习的GSW-型全同态层次型IBE方案[J].计算机应用,2016,36(7):1856-1860.(DAI X M, ZHANG W, ZHENG Z H, et al. GSW-type hierarchical identity-based fully homomorphic encryption scheme from learning with errors [J]. Journal of Computer Applications, 2016, 36(7): 1856-1860.)

[18] CLEAR M, MCGOLDRICK C. Multi-identity and multi-key leveled FHE from learning with errors [C]// CRYPTO 2015: Proceedings of the 2015 Annual International Cryptology Conference, LNCS 9216. Berlin: Springer, 2015: 630-656.

[19] PEIKERT C, SHIEHIAN S. Multi-key FHE from LWE, revisited [C]// Proceedings of the 2016 Theory of Cryptography Conference, LNCS 9986. Berlin: Springer, 2016: 217-238.

[20] BRAKERSKI Z, CASH D, TSABARY R, et al. Targeted homomorphic attribute based encryption [C]// Proceedings of the 2016 Theory of Cryptography Conference, LNCS 9986. Berlin: Springer, 2016: 330-360.

[21] HIROMASA R, KAWAI Y. Fully dynamic multi target homomorphic attribute-based encryption [EB/OL]. [2017- 05- 19]. https://eprint.iacr.org/2017/373.pdf.

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

[23] MICCIANCIO D, MOL P. Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions [C]// CRYPTO 2011: Proceedings of the 31st Annual International Cryptology Conference, LNCS 6841. Berlin: Springer, 2011: 465-484.

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

[25] BRAKERSKI Z. Fully homomorphic encryption without modulus switching from classical GapSVP [C]// CRYPTO 2012: Proceedings of the 32nd Annual Cryptology Conference, LNCS 7417. Berlin: Springer, 2012: 868-886.

[26] BARAK B, DODIS Y, KRAWCZYK H, et al. Leftover hash lemma, rivisted [C]// CRYPTO 2011: Proceedings of the 31st Annual International Cryptology Conference, LNCS 6841. Berlin: Springer, 2011: 1-20.

[27] LENSTRA A K, JR H W L, LOVSZ L. Factoring polynomials with rational coefficients [J]. Mathematische Annalen,1982, 261(4): 515-534.

This work is partially supported by the Key Research and Development Program of Hebei Province (16210701), the Scientific and Technological Research Project of Higher Education of Hebei Province (ZD2017228).

LIMingxiang, born in 1968, Ph. D., associate professor. His research interests include fully homomorphic encryption scheme.

LIUZhao, born in 1989, M. S., assistant. Her research interests include cloud computing security.

ZHANGMingyan, born in 1983, M. S., associate research fellow. Her research interests include Internet finance.

FullyhomomorphicencryptionschemewithoutGaussiannoise

LI Mingxiang1,2*, LIU Zhao1,3, ZHANG Mingyan1,3

(1.InstituteofFinance,HebeiFinanceUniversity,BaodingHebei071051,China;2.ScienceandTechnologyFinanceKeyLaboratoryofHebeiProvince,BaodingHebei071051,China;3.FinancialSynergyInnovationofScienceandTechnologyCenterinHebeiProvince,BaodingHebei071051,China)

Much lately, a leveled fully homomorphic encryption scheme was proposed based on the Learning With Rounding (LWR) problem. The LWR problem is a variant of the Learning With Errors (LWE) problem, but it dispenses with the costly Gaussian noise sampling. Thus, compared with the existing LWE-based fully homomorphic encryption schemes, the proposed LWR-based fully homomorphic encryption scheme has much higher efficiency. But then, the user’s evaluation key was needed to be obtained in the homomorphic evaluator of the proposed LWR-based fully homomorphic encryption scheme. Accordingly, a new leveled fully homomorphic encryption scheme was constructed based on the LWR problem, and the user’s evaluation key was not needed to be obtained in the homomorphic evaluator of the new fully homomorphic encryption scheme. Since the new proposed fully homomorphic encryption scheme can be used to construct the schemes such as identity-based fully homomorphic encryption schemes, and attribute-based fully homomorphic encryption schemes, the new proposed scheme has wider application than the lately proposed LWR-based fully homomorphic encryption scheme.

Fully Homomorphic Encryption (FHE); leveled Fully Homomorphic Encryption (FHE); Learning With Rounding (LWR) problem; Learning With Errors (LWE) problem; Gaussian noise sampling

2017- 06- 23;

2017- 08- 27。

河北省重点研发计划项目(16210701)；河北省高等学校科学技术研究项目(ZD2017228)。

李明祥(1968—)，男，山东济宁人，副教授，博士，主要研究方向：全同态加密方案； 刘照(1989—)，女，河北保定人，助教，硕士，主要研究方向：云计算安全； 张明艳(1983—)，女，湖北荆州人，副研究员，硕士，主要研究方向：互联网金融。

1001- 9081(2017)12- 3430- 05

10.11772/j.issn.1001- 9081.2017.12.3430

(*通信作者电子邮箱limingxiang@hbfu.edu.cn)

TP309.7

A