基于Binary LWE的全同态加密方案研究

doi:10.3969/j.issn.1671-1122.2015.07.007

信息网络安全 ›› 2015, Vol. 15 ›› Issue (7): 41-50.doi: 10.3969/j.issn.1671-1122.2015.07.007

基于Binary LWE的全同态加密方案研究

王志刚¹(), 马春光², 史晓倩¹

1. 哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨 150001
2. 哈尔滨工程大学国家保密学院,黑龙江哈尔滨 150001

收稿日期:2015-06-08 出版日期:2015-07-01 发布日期:2015-07-28
作者简介:
作者简介：王志刚（1992-）,男,新疆,硕士研究生,主要研究方向：信息与网络安全、机器学习;马春光（1974-）,男,黑龙江,教授,博士,主要研究方向：密码学、信息安全、传感网与物联网、网络编码;史晓倩（1990-）,女,黑龙江,硕士研究生,主要研究方向：信息与网络安全、密码学。
基金资助:
黑龙江省自然科学基金[F201229]

Research on Full Homomorphic Encryption Scheme Based on Binary LWE

Zhi-gang WANG¹(), Chun-guang MA², Xiao-qian SHI¹

1. College of Computer Science and Technology, Harbin Engineering University, Harbin Heilongjiang 150001, China
2. College of National Secrecy, Harbin Engineering University, Harbin Heilongjiang 150001, China

Received:2015-06-08 Online:2015-07-01 Published:2015-07-28

摘要/Abstract

摘要：

文章主要构造了一个基于Binary LWE的全同态加密方案,它是一种具有较短密钥尺寸和较小密文规模的全同态加密方案。全同态加密方案的密钥尺寸和密文规模过大、效率过低是阻碍全同态加密应用于实际的主要问题。文章对基础加密方案的关键技术进行了改进,之前的方案都是均匀随机选取一些集合加到LWE的一些随机选取的样本上,而文章所提出的方案则是将一些高斯错误加到从高斯分布中选取的一些LWE的样本上,这样就使得LWE的样本数从2nlogq降低到n+1,方案的私钥直接从{0,1}ⁿ集合中选取,不再使用二进制分解算法,并利用密钥转换技术,使得方案中的密文在经过张量乘法运算后的密文规模不会迅速膨胀,密钥尺寸较小。最后将方案安全性规约到搜索Binary LWE困难问题假设上,并给出安全性证明。

关键词: 全同态加密, Binary LWE, 密钥尺寸, 密文规模

Abstract:

The paper constructs a fully homomorphic encryption method based on Binary LWE with a shorter secret key and smaller cipher text. The main obstacle when doing implementation of the fully homomorphic encryption method is that the size of secret key and the scale of the cipher text are too big and that its efficiency is too low. This article improved the key technology of the basic encrypting method. In the previous methods, some collections chosen uniformly and randomly are added to LWE’s random samples. However, the method this article proposes will add some Gausian Error to the LWE samples chosen from Gausian Distribution. This will decrease the sample size of LWE from 2nlogq to n+1. And the private key of this method will be chosen directly from the set {0,1}ⁿinstead of the Binary decomposition algorithm. This method will adopt the key conversion technology to avoid the rapid expansion of the scale of the cipher text after tensor multiplication, and meanwhile get a smaller size of secret key. In the end, the article will attribute the security of the method to the assumptions of difficult problems when searching Binary LWE and then give a security proof.

Key words: fully homomorphic encryption, Binary LWE, size of secret keys, scale of cipher text

中图分类号:

TP309

王志刚, 马春光, 史晓倩. 基于Binary LWE的全同态加密方案研究[J]. 信息网络安全, 2015, 15(7): 41-50.

Zhi-gang WANG, Chun-guang MA, Xiao-qian SHI. Research on Full Homomorphic Encryption Scheme Based on Binary LWE[J]. Netinfo Security, 2015, 15(7): 41-50.

图/表 3

参考文献 20

[1]	RIVEST R L, ADLEMAN L, DERTOUZOS M L.On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978: 169-179.
[2]	GOLDWASSER S, MICALI S.Probabilistic encryption[J]. Journal of Computer and System Sciences, 1984, 28(2): 270-299.
[3]	PAILLIER P.Public-key cryptosystems based on composite degree residuosity classes[J]. Advances in Cryptology-Eurocrypt, 1999: 223-238.
[4]	DAMGARD I, JURIK M.A generalisation, a simplification and some applications of paillier’s probabilistic public-key system[J]. Public Key Cryptography, 2001: 119-136.
[5]	BONEH D, GOH E, NISSIM K.Evaluating 2-DNF formulas on ciphertexts[C]//Second Theory of Cryptography Conference, Cambridge, 2005, 325-341.
[6]	GENTRY C.Fully homomorphic encryption using ideal lattices[J]. Proc Stoc, 2009, 2011, (4):169-178.
[7]	SMART N P, VERCAUTEREN F.Fully homomorphic encryption with relatively small key and ciphertext sizes[C]//13th International Conference on Practice and Theory in Public Key Cryptography, Paris, 2010: 420-443.
[8]	STEHLÉ D, STEINFELD R.Faster fully homomorphic encryption[C]//16th International Conference on the Theory and Application of Cryptology and Information Security, 2010: 377-394.
[9]	BRAKERSKI Z, VAIKUNTANATHAN V.Fully homomorphic encryption from ring-LWE and security for key dependent messages[C]//31st Annual Cryptology Conference, Santa, 2011, 505-524.
[10]	GENTRY C, HALEVI S.Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits[J]. Foundations of Computer Science Annual Symposium on, 2011, 47(10): 107-109.
[11]	DIJK M, GENTRY C, HALEVI S, VAIKUNTANATHAN V.Fully homomorphic encryption over the integers[C]//29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, 2010: 24-43.
[12]	BRAKERSKI Z, VAIKUNTANATHAN V.Efficient Fully Homomorphic Encryption from (Standard) LWE[C]//Foundations of Computer Science, IEEE Annual Symposium on. IEEE, 2011: 97-106.
[13]	GENTRY C, HALEVI S, PEIKERT C, et al.Ring Switching in BGV-Style Homomorphic Encryption[C]//8th International Conference, SCN 2012, Amalfi, 2012: 19-37.
[14]	BRAKERSKI Z, GENTRY C, HALEVI S.Packed Ciphertexts in LWE-based Homomorphic Encryption[J]. Lecture Notes in Computer Science, 2013: 1-13.
[15]	BAI S, STEVEN D.Lattice Decoding Attacks on Binary LWE[C]// 19th Australasian Conference on Information Security and Privacy, Wollongong, 2014: 322-337.
[16]	REGEV O.Lattice-based cryptography[C]//26th Annual International Cryptology Conference, Santa Barbara, 2006: 131-141.
[17]	吕海峰,丁勇,代洪艳,等. LWE上的全同态加密方案研究[J]. 信息网络安全,2015,(1):32-38.
[18]	GENTRY C, HALEVI S, SMART P.Fully Homomorphic Encryption with Polylog Overhead[C]//31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, 2012: 465-482.
[19]	BRAKERSKI Z. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP[R]. stanford edu, Advances in Cryptology-CRYPTO 2012 Lecture Notes in Computer Science, 20120518:231322, 2012.
[20]	REGEV O.On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the Acm, 2005, 56(6):84-93.

基于Binary LWE的全同态加密方案研究

Research on Full Homomorphic Encryption Scheme Based on Binary LWE

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 20

相关文章 8

编辑推荐

Metrics

本文评价

[1]	刘文超, 潘峰, 杨晓元, 周潭平. 基于GPU的全同态加密软件库调试与分析[J]. 信息网络安全, 2019, 19(6): 76-83.
[2]	宋新霞, 马佳敏, 陈智罡, 陈克非. 基于SEAL的虹膜特征密文认证系统[J]. 信息网络安全, 2018, 18(12): 15-22.
[3]	王嵘冰, 李雅囡, 徐红艳, 冯勇. 适合云服务环境的实数全同态加密方案[J]. 信息网络安全, 2018, 18(11): 49-56.
[4]	李增鹏, 马春光, 张磊, 张雯雯. 两类基于容错学习的多比特格公钥加密方案[J]. 信息网络安全, 2017, 17(10): 1-7.
[5]	李增鹏, 邹岩, 张磊, 马春光. 一种基于全同态加密的智能电网数据交换隐私保护方案[J]. 信息网络安全, 2016, 16(3): 1-7.
[6]	吕海峰, 丁勇, 代洪艳, 李新国. LWE上的全同态加密方案研究[J]. 信息网络安全, 2015, 15(1): 32-38.
[7]	. 可计算密文加密体制研究[J]. , 2014, 14(5): 78-.
[8]	吴旭东. 云计算数据安全研究[J]. , 2011, 11(9): 0-0.