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

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

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.

LV Hai-feng, DING Yong, DAI Hong-yan, LI Xin-guo. 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]	张艳硕, 袁煜淇, 李丽秋, 杨亚涛, 秦晓宏. 基于SM2的周期性可否认环签名方案[J]. 信息网络安全, 2024, 24(4): 564-573.
[2]	徐茹枝, 戴理朋, 夏迪娅, 杨鑫. 基于联邦学习的中心化差分隐私保护算法研究[J]. 信息网络安全, 2024, 24(1): 69-79.
[3]	刘芹, 王卓冰, 余纯武, 王张宜. 面向云安全的基于格的高效属性基加密方案[J]. 信息网络安全, 2023, 23(9): 25-36.
[4]	李增鹏, 王梅, 陈梦佳. 新形态伪随机函数研究[J]. 信息网络安全, 2023, 23(5): 11-21.
[5]	刘芹, 张标, 涂航. 基于twisted Edwards曲线的无证书盲签名方案[J]. 信息网络安全, 2022, 22(8): 19-25.
[6]	王超, 韩益亮, 段晓巍, 李鱼. 基于密钥封装机制的RLWE型认证密钥交换协议[J]. 信息网络安全, 2021, 21(6): 80-88.
[7]	刘子昂, 黄缘缘, 马佳利, 周睿. 基于区块链的医疗数据滥用监控平台设计与实现[J]. 信息网络安全, 2021, 21(5): 58-66.
[8]	刘峰, 杨杰, 齐佳音. 基于哈希证明系统的区块链两方椭圆曲线数字签名算法研究[J]. 信息网络安全, 2021, 21(1): 19-26.
[9]	李宁波, 周昊楠, 车小亮, 杨晓元. 云环境下基于多密钥全同态加密的定向解密协议设计[J]. 信息网络安全, 2020, 20(6): 10-16.
[10]	周昊楠, 李宁波, 车小亮, 杨晓元. 基于素数幂次阶分圆多项式环的多密钥全同态方案[J]. 信息网络安全, 2020, 20(5): 83-87.
[11]	王生玉, 汪金苗, 董清风, 朱瑞瑾. 基于属性加密技术研究综述[J]. 信息网络安全, 2019, 19(9): 76-80.
[12]	韩益亮, 王众. 基于多变量和LRPC码的抗量子密码方案研究[J]. 信息网络安全, 2019, 19(8): 36-43.
[13]	亢保元, 颉明明, 司林. 基于生物识别技术的多云服务器认证方案研究[J]. 信息网络安全, 2019, 19(6): 45-52.
[14]	刘文超, 潘峰, 杨晓元, 周潭平. 基于GPU的全同态加密软件库调试与分析[J]. 信息网络安全, 2019, 19(6): 76-83.
[15]	王耀杰, 钮可, 杨晓元. 基于生成对抗网络的图像隐藏方案[J]. 信息网络安全, 2019, 19(5): 54-60.