LWE上的全同态加密方案研究

doi:10.3969/j.issn.1671-1122.2015.01.006

信息网络安全 ›› 2015, Vol. 15 ›› Issue (1): 32-38.doi: 10.3969/j.issn.1671-1122.2015.01.006

LWE上的全同态加密方案研究

吕海峰^1,³(), 丁勇^1,², 代洪艳¹, 李新国³

1.桂林电子科技大学数学与计算科学学院,广西桂林 541004
2.西安电子科技大学ISN国家重点实验室,陕西西安 610061
3.深圳数字电视国家工程实验室股份有限公司,广东深圳 518057

收稿日期:2014-11-05 出版日期:2015-01-10 发布日期:2015-07-05
作者简介:
作者简介：吕海峰（1987-）,男,广西,硕士研究生,主要研究方向：密码学与信息安全;丁勇（1975-）,男,重庆,教授,博士,主要研究方向：密码学与信息安全;代洪艳（1988-）,女,安徽,硕士研究生,主要研究方向：密码学与信息安全;李新国（1976-）,男,河南,博士,主要研究方向：数字多媒体安全。
基金资助:
国家高技术研究发展计划[2012AA011705];广西自然科学基金[2013GXNSFBB053005];ISN国际重点实验室开放基金;广西无线宽带通信与信号处理重点实验室开放基金

Survey on LWE-based Fully Homomorphic Encryption Scheme

Hai-feng LV^1,³(), Yong DING^1,², Hong-yan DAI¹, Xin-guo LI³

1. School of Mathematics & Computing Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China
2. The State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an Shanxi 610061, China
3. Shenzhen Digital TV National Engineering Laboratory Co., Ltd., Shenzhen Guangdong 518057, China

Received:2014-11-05 Online:2015-01-10 Published:2015-07-05

摘要/Abstract

摘要：

文章介绍了全同态加密的研究历史和现状,分析了构建全同态加密方案的思想与方法,并且介绍和整理了全同态加密的一些主要技术。文章还综述了基于LWE的全同态加密方案,先是用重线性化技术构造一个部分同态加密方案,再利用维数模约减技术降低密文的尺寸和解密电路复杂度,结合bootstrappable技术获得全同态加密。文章研究的基于LWE的全同态加密方案主要从噪声、参数性能、安全性这三个方面进行具体分析。文章最后对该方案与整数上的全同态加密方案从性能、安全性两个方面进行比较,同时指出全同态加密方案的构建本质与亟待解决的关键问题,为进一步研究全同态加密提供参考性意见。

关键词: 全同态加密, LWE, 噪声, 参数及性能, 安全性

Abstract:

This paper introduced history and current situation in fully homomorphic encryption (FHE). We analyzed the idea and methods of constructing FHE scheme, and classified the main techniques that are used to construct FHE scheme. Then this paper summarized LWE-based fully homomorphic encryption scheme, firstly, a somewhat homomorphic encryption schemes is constructed by using a re-linearization technique, secondly, dimension-modulus reduction technique is utilized to reduce the size of ciphertexts and decryption circuit complexity, combined bootstrappable technology to achieve full homomorphic encryption. It mainly analyzed three aspects which from noise problem, parameters and performance as well as security. At last we compared with the fully homomorphic encryption over the integers, which from two aspects of performance and security, and point out the essence of the way to construct FHE and the main problems that need to be solved at present. We hope this paper can provide guidance for further in-depth study of fully homomorphic encryption.

Key words: fully homomorphic encryption, LWE, noise, parameters and performance, security

中图分类号:

TP309

吕海峰, 丁勇, 代洪艳, 李新国. LWE上的全同态加密方案研究[J]. 信息网络安全, 2015, 15(1): 32-38.

Hai-feng LV, Yong DING, Hong-yan DAI, Xin-guo LI. Survey on LWE-based Fully Homomorphic Encryption Scheme[J]. Netinfo Security, 2015, 15(1): 32-38.

图/表 2

参考文献 36

[1]	GENTRY C.Fully homomorphic encryption using ideal lattices[C]//Proceedings of the 41st annual ACM symposium on Theory of computing. Bethesda, MD, USA; ACM. 2009: 169-178.
[2]	RIVEST R L, ADLEMAN L, DERTOUZOS M L.On data banks and privacy homomorphisms[J]. Foundations of secure computation, 1978,4(11): 169-180.
[3]	MICCIANCIO D.A first glimpse of cryptography's Holy Grail[J]. Communications of the ACM, 2010, 53(3): 96-96.
[4]	RIVEST R L, SHAMIR A, ADLEMAN L.A method for obtaining digital signatures and public-key cryptosystems[J]. Communication ACM, 1978, 21(2): 120-126.
[5]	GOLDWASSER S, MICALI S.Probabilistic encryption[J]. Journal of computer and system sciences, 1984, 28(2): 270-299.
[6]	ELGAMAL T.A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Trans Inf Theory, 1985, 31(4): 469-472.
[7]	PAILLIER P.Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[C]//STERN J. Advances in Cryptology—EUROCRYPT'99. Springer Berlin Heidelberg. 1999: 223-238.
[8]	Damgård I, JURIK M.A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System[C]//Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography. Springer-Verlag. 2001: 119-136.
[9]	AJTAI M S, DWORK C.A public-key cryptosystem with worst-case/average-case equivalence[C]//Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. El Paso, Texas, United States; ACM. 1997: 284-293.
[10]	REGEV O.New lattice-based cryptographic constructions[J]. JACM, 2004, 51(6): 899-942.
[11]	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.
[12]	COHEN J D, FISCHER M J.A robust and verifiable cryptographically secure election scheme[C]//Proceedings of the 26th Annual Symposium on Foundations of Computer Science. IEEE Computer Society. 1985: 372-382.
[13]	NACCACHE D, STERN J.A new public key cryptosystem based on higher residues[C]//Proceedings of the 5th ACM conference on Computer and communications security. San Francisco, California, United States;ACM. 1998: 59-66.
[14]	OKAMOTO T, UCHIYAMA S.A new public-key cryptosystem assecure as factoring[C]//NYBERG K. Advances in Cryptology.
[15]	BONEH D, GOH E J, NISSIM K.Evaluating 2-DNF Formulas on Ciphertexts[C]//KILIAN J. Theory of Cryptography. Springer Berlin Heidelberg. 2005: 325-341.
[16]	GENTRY C, HALEVI S, VAIKUNTANATHAN V.A Simple BGN-Type Cryptosystem from LWE[C]//GILBERT H. Advances in Cryptology-EUROCRYPT 2010. Springer Berlin Heidelberg. 2010:506-522.
[17]	ISHAI Y, PASKIN A.Evaluating Branching Programs on Encrypted Data[C]//VADHAN S. Theory of Cryptography. Springer Berlin Heidelberg. 2007: 575-594.
[18]	MELCHOR C, GABORIT P, HERRANZ J.Additively Homomorphic Encryption with d-Operand Multiplications[C]//RABIN T. Advances in Cryptology-CRYPTO 2010. Springer Berlin Heidelberg. 2010: 138-154.
[19]	SANDER T, YOUNG A, YUNG M.Non-Interactive CryptoComputing For NC1[C]//Proceedings of the 40th Annual Symposium on Foundations of Computer Science. IEEE Computer Society. 1999: 554-556.
[20]	ALBRECHT M, FARSHIM P, FAUG RE J-C, et al. Polly Cracker, Revisited[C]//LEE D, WANG X. Advances in Cryptology-ASIACRYPT 2011. Springer Berlin Heidelberg. 2011: 179-196.
[21]	YAO A C.Protocols for secure computations[C]//Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society. 1982: 160-164.
[22]	VAIKUNTANATHAN V.Computing Blindfolded: New Developments in Fully Homomorphic Encryption[C]//Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society. 2011: 5-16.
[23]	GOLDWASSER S, KALAI Y, POPA R, et al.How to Run Turing Machines on Encrypted Data[C]//CANETTI R, GARAY J. Advances in Cryptology-CRYPTO 2013. Springer Berlin Heidelberg. 2013: 536-553.
[24]	GOLDWASSER S, KALAI Y, POPA R A, et al.Reusable garbled circuits and succinct functional encryption[C]//Proceedings of the 45th annual ACM symposium on Symposium on theory of computing. Palo Alto, California, USA; ACM. 2013: 555-564.
[25]	VAN DIJK M, GENTRY C, HALEVI S, et al.Fully Homomorphic Encryption over the Integers[C]//GILBERT H. Advances in Cryptology -EUROCRYPT 2010. Springer Berlin/Heidelberg. 2010: 24-43.
[26]	SMART N P, VERCAUTEREN F.Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes[C]//NGUYEN P, POINTCHEVAL D. Public Key Cryptography-PKC 2010. Springer Berlin Heidelberg. 2010: 420-443.
[27]	STEHL D, STEINFELD R.Faster Fully Homomorphic Encryption[C]//ABE M. Advances in Cryptology-ASIACRYPT 2010. Springer Berlin Heidelberg. 2010: 377-394.
[28]	BRAKERSKI Z, VAIKUNTANATHAN V.Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages[C]//ROGAWAY P. Advances in Cryptology-CRYPTO 2011. Springer Berlin Heidelberg. 2011: 505-524.
[29]	CORON J-S, MANDAL A, NACCACHE D, et al.Fully Homomorphic Encryption over the Integers with Shorter Public Keys[C]//ROGAWAY P. Advances in Cryptology-CRYPTO 2011. Springer Berlin Heidelberg. 2011: 487-504.
[30]	CORON J S, NACCACHE D, TIBOUCHI M.Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers[C]//POINTCHEVAL D, JOHANSSON T. Advances in Cryptology-EUROCRYPT 2012. Springer Berlin Heidelberg. 2012: 446-464.
[31]	BRAKERSKI Z, VAIKUNTANATHAN V.Efficient Fully Homomorphic Encryption from (Standard) LWE[C]//Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society. 2011: 97-106.
[32]	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V.(Leveled) fully homomorphic encryption without bootstrapping[C]//Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. Cambridge, Massachusetts; ACM. 2012: 309-325.
[33]	BRAKERSKI Z.Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP[C]//SAFAVI-NAINI R, CANETTI R. Advances in Cryptology-CRYPTO 2012. Springer Berlin Heidelberg.2012: 868-886.
[34]	L PEZ-ALT A, TROMER E, VAIKUNTANATHAN V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C]//Proceedings of the 44th symposium on Theory of Computing. New York, New York, USA; ACM. 2012: 1219-1234.
[35]	GENTRY C, SAHAI A, WATERS B.Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[C]//CANETTI R, GARAY J. Advances in Cryptology -CRYPTO 2013. Springer Berlin Heidelberg. 2013: 75-92.
[36]	LYUBASHEVSKY V, PEIKERT C, REGEV O.On Ideal Lattices and Learning with Errors over Rings[C]//GILBERT H. Advances in Cryptology-EUROCRYPT 2010. Springer Berlin Heidelberg. 2010: 1-23.

LWE上的全同态加密方案研究

Survey on LWE-based Fully Homomorphic Encryption Scheme

RichHTML

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 36

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王生玉, 汪金苗, 董清风, 朱瑞瑾. 基于属性加密技术研究综述[J]. 信息网络安全, 2019, 19(9): 76-80.
[2]	韩益亮, 王众. 基于多变量和LRPC码的抗量子密码方案研究[J]. 信息网络安全, 2019, 19(8): 36-43.
[3]	亢保元, 颉明明, 司林. 基于生物识别技术的多云服务器认证方案研究[J]. 信息网络安全, 2019, 19(6): 45-52.
[4]	刘文超, 潘峰, 杨晓元, 周潭平. 基于GPU的全同态加密软件库调试与分析[J]. 信息网络安全, 2019, 19(6): 76-83.
[5]	王耀杰, 钮可, 杨晓元. 基于生成对抗网络的图像隐藏方案[J]. 信息网络安全, 2019, 19(5): 54-60.
[6]	李明祥, 王洪涛. 基于格的身份基矩阵加密方案[J]. 信息网络安全, 2019, 19(1): 34-41.
[7]	左黎明, 胡凯雨, 张梦丽, 夏萍萍. 一种具有双向安全性的基于身份的短签名方案[J]. 信息网络安全, 2018, 18(7): 47-54.
[8]	高洪涛, 陆伟, 杨余旺. 基于自适应调节核函数的图像显著区域提取方法[J]. 信息网络安全, 2018, 18(2): 54-60.
[9]	宋新霞, 马佳敏, 陈智罡, 陈克非. 基于SEAL的虹膜特征密文认证系统[J]. 信息网络安全, 2018, 18(12): 15-22.
[10]	王嵘冰, 李雅囡, 徐红艳, 冯勇. 适合云服务环境的实数全同态加密方案[J]. 信息网络安全, 2018, 18(11): 49-56.
[11]	姜红, 亢保元, 李春青. 改进的保护身份的云共享数据完整性公开审计方案[J]. 信息网络安全, 2018, 18(10): 85-91.
[12]	齐健, 陈小明, 游伟青. 基于fuzzing测试的网络协议安全评估方法研究[J]. 信息网络安全, 2017, 17(3): 59-65.
[13]	黄鹏, 曾贵华. 连续变量量子密钥分发实际安全性研究进展[J]. 信息网络安全, 2017, 17(11): 7-12.
[14]	李增鹏, 马春光, 张磊, 张雯雯. 两类基于容错学习的多比特格公钥加密方案[J]. 信息网络安全, 2017, 17(10): 1-7.
[15]	刘学芬, 孙荣辛, 夏鲁宁, 李伟. 面向MySQL的安全隐患检测方法研究[J]. 信息网络安全, 2016, 16(9): 1-5.