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

doi:10.3969/j.issn.1671-1122.2017.10.001

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 1

References 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.