两类基于容错学习的多比特格公钥加密方案

doi:10.3969/j.issn.1671-1122.2017.10.001

信息网络安全 ›› 2017, Vol. 17 ›› Issue (10): 1-7.doi: 10.3969/j.issn.1671-1122.2017.10.001

• • 下一篇

两类基于容错学习的多比特格公钥加密方案

李增鹏, 马春光(), 张磊, 张雯雯

哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨 150001

收稿日期:2017-08-10 出版日期:2017-10-10 发布日期:2020-05-12
作者简介:
作者简介：李增鹏（1989—）,男,山东,博士研究生,主要研究方向为密码学与信息安全;马春光（1974—）,男,黑龙江,教授,博士,主要研究方向为密码学与信息安全;张磊（1982—）,男,黑龙江,博士研究生,主要研究方向为隐私保护;张雯雯（1993—）,女,黑龙江,硕士研究生,主要研究方向为隐私保护。
基金资助:
国家自然科学基金[61472097]

Two Types LWE-based Multi-bit Lattice-based Encryption Schemes

Zengpeng LI, Chunguang MA(), Lei ZHANG, Wenwen ZHANG

College of Computer Science and Technology, Harbin Engineering University, Harbin Heilongjiang 150001, China

Received:2017-08-10 Online:2017-10-10 Published:2020-05-12

摘要/Abstract

摘要：

作为后量子密码的经典困难问题,LWE多用于设计各种基于格的公钥加密算法和密码协议。GENTRY等人基于LWE假设提出了对偶版本的Regev加密方案,即GPV加密方案,进一步推动了格公钥密码的发展。当前的密码算法构造多利用Regev方案或GPV方案作为基础密码学组件。然而,现有的基于格公钥加密方案的研究多集中在单比特加密,对于多比特加密的格公钥加密方案,通常采用两种简单的方式得到,或者通过直接对矩阵加密获得,或者通过累加迭代单比特加密方案获得。以上两种计算开销大且效率低下。文章受LI等人构造的多比特全同态加密方案启发,分别构造了两类新的公钥,使其公钥中包含了多个LWE实例,而不再只含有一个LWE实例。进而利用两种新的公钥,分别以Regev加密方案和GPV加密方案作为基础密码学组件,构造了两类格基多比特加密方案,并在LWE假设下,证明两个方案是选择明文安全的。

关键词: 格基密码, 容错学习, 多比特加密, 全同态加密

Abstract:

As a classical hard problem of post quantum cryptography, LWE was used to design various public-key encryption algorithms and cryptographic protocols based on lattice. Based on LWE assumption, Gentry proposed a dual version of the Regev encryption scheme, which further promoted the development of public key cryptography. It causes that most existing cryptographic algorithm constructions use Regev scheme or GPV as the basic cryptography building block. However, most existing researches on lattice-based public key encryption scheme focus on the single bit encryption, but two simple methods usually were used to obtain the multi bit encryption, i.e., either encrypting the matrix directly, or, iterating single bit encryption schemes. These two kinds of calculation are costly and inefficient. In this paper, inspired by the multi-bit fully homomorphic encryption scheme by Li et al., two kinds of new public keys are constructed respectively, which contain multiple LWE instances, instead of only one. Then we construct two kinds of multi-bit lattice-based encryption using two new public keys, i.e., Regev and GPV as the building blocks respectively, and proved them CPA secure under LWE assumption.

Key words: lattice-based cryptography, learning with errors, multi-bit encryption, FHE

中图分类号:

TP309

李增鹏, 马春光, 张磊, 张雯雯. 两类基于容错学习的多比特格公钥加密方案[J]. 信息网络安全, 2017, 17(10): 1-7.

Zengpeng LI, Chunguang MA, Lei ZHANG, Wenwen ZHANG. Two Types LWE-based Multi-bit Lattice-based Encryption Schemes[J]. Netinfo Security, 2017, 17(10): 1-7.

图/表 1

参考文献 22

[1]	AJTAI M, DWORK C.A Public-key Cryptosystem with Worst-case/Average-case Equivalence[C]//ACM. 29th Annual ACM Symposium on the Theory of Computing, May 4-6, 1997, Texas, USA. New York: ACM, 1997: 284-293.
[2]	REGEV O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[C]//ACM. 37th Annual ACM Symposium on Theory of Computing, May 22-24, 2005, Baltimore, MD, USA. New York: ACM, 2005: 84-93.
[3]	GENTRY C, PEIKERT C, VAIKUNTANATHAN V.Trapdoors for Hard Lattices and New Cryptographic Constructions[C]//ACM. 40th Annual ACM Symposium on Theory of Computing, May 17-20, 2008, Victoria, British Columbia, Canada. New York: ACM, 2008: 197-206.
[4]	KAWACHI A, TANAKA K, XAGAWA K.Multi-bit Cryptosystems Based on Lattice Problems[C]// Springer. 10th International Conference on Practice and Theory in Public-Key Cryptography, April 16-20, 2007, Beijing, China. Heidelberg: Springer, 2007: 315-329.
[5]	PEIKERT C, VAIKUNTANATHAN V, WATERS B.A Framework for Efficient and Composable Oblivious Transfer[C]//IACR. 28th Annual International Cryptology Conference on Cryptology: Advances in Cryptology, August 17-21, 2008, Santa Barbara, CA, USA. Heidelberg: Springer, 2008: 554-571.
[6]	BRAKERSKI Z, GENTRY C, HALEVI S.Packed Ciphertexts in LWE-based Homomorphic Encryption[C]//IACR. 16th International Conference on Practice and Theory in PublicKey Cryptography, February 26-March 1, 2013, Nara, Japan. Heidelberg: Springer, 2013: 1-13.
[7]	GENTRY C.Fully Homomorphic Encryption Using Ideal Lattices[C]//ACM. 41st Annual ACM Symposium on Theory of Computing, May 31-June 2, 2009, Bethesda, MD, USA. New York: ACM, 2009: 169-178.
[8]	吕海峰,丁勇,代洪艳,等. LWE上的全同态加密方案研究[J]. 信息网络安全,2015(1):32-38.
[9]	LI Zengpeng, MA Chunguang, MORAIS E, et al.Multi-bit Leveled Homomorphic Encryption via Dual.LWE-based[C]// Springer. 2016 International Conference on Information Security and Cryptology, November 4-6, 2016, Beijing, China. Heidelberg: Springer, 2016: 221-242.
[10]	BLUM A, KALAI A, WASSERMAN H.Noise-tolerant Learning, the Parity Problem, and the Statistical Query Model[J]. ACM, 2003, 50(4): 506-519.
[11]	LYUBASHEVSKY V.Lattice Signatures without Trapdoors[C]//IACR. 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, April 15-19, 2012, Cambridge, UK. Heidelberg: Springer, 2012: 738-755.
[12]	HIROMASA R, ABE M, OKAMOTO T.Packing Messages and Optimizing Bootstrapping in GSW-FHE[C]//IACR. 18th IACR International Conference on Practice and Theory in Public Key Cryptography, March 30-April 1, 2015, Gaithersburg, MD, USA. Heidelberg: Springer, 2015: 699-715.
[13]	LI Zengpeng, MA Chunguang, DU Gang, et al.Dual LWE-based Fully Homomorphic Encryption with Errorless Key Switching[C]//IEEE. 22nd IEEE International Conference on Parallel and Distributed Systems, December 13-16, 2016, Wuhan, China. New Jersey: IEEE, 2017: 1169-1174.
[14]	BRAKERSKI Z, VAIKUNTANATHAN V.Efficient Fully Homomorphic Encryption from(Standard) LWE[C]//IEEE. IEEE 52nd Annual Symposium on Foundations of Computer Science, October 22-25, 2011, CA, USA. New Jersey: IEEE, 2011: 97-106.
[15]	BRAKERSKI Z.Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages[C]//IACR. 31st Annual Conference on Advances in Cryptology, August 14-18, 2011, Santa Barbara, CA, USA. Heidelberg: Springer, 2011: 505-524.
[16]	GENTRY C, SAHAI A, WATERS B.Homomorphic Encryption from Learning with Errors: Conceptually-simpler, Asymptotically-faster, Attribute-based[C]//IACR. 33rd Annual Conference on Advances in Cryptology, August 18-22, 2013, Santa Barbara, CA, USA. Heidelberg: Springer, 2013: 75-92.
[17]	BRAKERSKI Z.Fully Homomorphic Encryption without Modulus Switching from Classical Gapsvp[C]//IACR. 32nd Annual Conference on Advances in Cryptology, August 19-23, 2012, Santa Barbara, CA, USA. Heidelberg: Springer, 2012: 868-886.
[18]	BRAKERSKI Z, LANGLOIS A, PEIKERT C, et al.Classical Hardness of Learning with Errors[C]//ACM. 45th Annual ACM Symposium on Theory of Computing, June 1-4, 2013, Palo Alto, CA, USA. New York: ACM, 2013: 575-584.
[19]	MICCIANCIO D, PEIKERT C.Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller[C]//IACR. 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, April 15-19, 2012, Cambridge, UK. Heidelberg: Springer, 2012: 700-718.
[20]	GOLDWASSER S, KALAI Y, PEIKERT C, et al.Robustness of the Learning with Errors Assumption[C]//Tsinghua University. 1st Symposium on Innovations in Computer Science, January 5-7, 2010, Beijing, China. Beijing: WanFang Data, 2010: 230-240.
[21]	BAI S, GALBRAITH S D.Lattice Decoding Attacks on Binary LWE[C]//Springer. 19th Australasian Conference on Information Security and Privacy, July 7-9, 2014, Wollongong, NSW, Australia. Heidelberg: Springer, 2014: 322-337.
[22]	王志刚,马春光,史晓倩. 基于Binary LWE的全同态加密方案研究[J]. 信息网络安全,2015(7):41-50.

两类基于容错学习的多比特格公钥加密方案

Two Types LWE-based Multi-bit Lattice-based Encryption Schemes

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 22

相关文章 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]. 信息网络安全, 2016, 16(3): 1-7.
[5]	王志刚, 马春光, 史晓倩. 基于Binary LWE的全同态加密方案研究[J]. 信息网络安全, 2015, 15(7): 41-50.
[6]	吕海峰, 丁勇, 代洪艳, 李新国. LWE上的全同态加密方案研究[J]. 信息网络安全, 2015, 15(1): 32-38.
[7]	. 可计算密文加密体制研究[J]. , 2014, 14(5): 78-.
[8]	吴旭东. 云计算数据安全研究[J]. , 2011, 11(9): 0-0.