Research ArticleOpen AccessGoogle Scholar indexed

Learning with Errors Public Key Cryptosystem with Its Security

¹ Engineering Research Center of Ministry of Education for Financial Computing and Digital Engineering, Renmin University of China, Beijing, China
² Engineering Research Center of Ministry of Education for Financial Computing and Digital Engineering, Renmin University of China, Beijing, China
³ Engineering Research Center of Ministry of Education for Financial Computing and Digital Engineering, Renmin University of China, Beijing, China
⁴ Engineering Research Center of Ministry of Education for Financial Computing and Digital Engineering, Renmin University of China, Beijing, China

Journal of Information Security·Volume 14 (2022)·Pages 25–38·Published 30 November 2022·DOI10.4236/jis.2023.141003

Abstract

The main purpose of this paper is to introduce the LWE public key cryptosystem with its security. In the first section, we introduce the LWE public key cryptosystem by Regev with its applications and some previous research results. Then we prove the security of LWE public key cryptosystem by Regev in detail. For not only independent identical Gaussian disturbances but also any general independent identical disturbances, we give a more accurate estimation probability of decryption error of general LWE cryptosystem. This guarantees high security and widespread applications of the LWE public key cryptosystem.

KeywordsLearning With Errors ProblemCryptosystemDecryption ErrorProbabilitySecurity

Regev, O. (2005) On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, 22-24 May 2005, 84-93. https://doi.org/10.1145/1060590.1060603
Micciancio, D. and Regev, O. (2009) Lattice-Based Cryptography. In: Bernstein, D.J., Buchmann, J. and Dahmen, E., Eds., Post-Quantum Cryptography, Springer, Berlin, 147-191. https://doi.org/10.1007/978-3-540-88702-7_5
Regev, O. (2009) On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Journal of the ACM, 56, Article No. 34. https://doi.org/10.1145/1568318.1568324
Ajtai, M., Kumar, R. and Sivakumar, D. (2001) A Sieve Algorithm for the Shortest Lattice Vector Problem. Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Heraklion, 6-8 July 2001, 601-610. https://doi.org/10.1145/380752.380857
Blum, A., Kalai, A. and Wasserman, H. (2003) Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model. Journal of the ACM, 50, 506-519. https://doi.org/10.1145/792538.792543
Kumar, R. and Sivakumar, D. (2001) On Polynomial Approximation to the Shortest Lattice Vector Length. Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington DC, 7-9 January 2001, 126-127.
Zheng, Z. and Tian, K. (2022) On the LWE Cryptosystem with More General Disturbance. Journal of Information Security, 13, 127-139. https://doi.org/10.4236/jis.2022.133008
Rivest, R., Adleman, L. and Dertouzos, M. (1978) On Data Banks and Privacy Homomorphism. In: DeMillo, R.A., Ed., Foundations of Secure Computation, Academic Press, New York, 169-180.
Gentry, C. (2009) Fully Homomorphic Encryption Using Ideal Lattices. Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Bethesda, 31 May-2 June 2009, 169-178. https://doi.org/10.1145/1536414.1536440
Dijk, M., Gentry, C., Halevi, S. and Vaikuntanathan, V. (2010) Fully Homomorphic Encryption over the Integers. International Conference on Theory and Applications of Cryptographic Techniques, French Riviera, 30 May-3 June 2010, 24-43. https://doi.org/10.1007/978-3-642-13190-5_2
Brakerski, Z. and Vaikuntanathan, V. (2011) Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. Annual Cryptology Conference, Santa Barbara, 14-18 August 2011, 505-524. https://doi.org/10.1007/978-3-642-22792-9_29

Menu

Learning with Errors Public Key Cryptosystem with Its Security

Abstract

References (16)