Research ArticleOpen AccessGoogle Scholar indexed

On the LWE Cryptosystem with More General Disturbance

¹ 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 13 (2022)·Pages 127–139·Published 9 June 2022·DOI10.4236/jis.2022.133008

Abstract

The main purpose of this paper is to give an extension on learning with errors problem (LWE) based cryptosystem about the probability of decryption error with more general disturbance. In the first section, we introduce the LWE cryptosystem with its application and some previous research results. Then we give a more precise estimation probability of decryption error based on independent identical Gaussian disturbances and any general independent identical disturbances. This upper bound probability could be closed to 0 if we choose applicable parameters. It means that the probability of decryption error for the cryptosystem could be sufficiently small. So we verify our core result that the LWE-based cryptosystem could have high security.

KeywordsLearning with Errors ProblemDecryption ErrorProbabilityGeneral Disturbance

Regev, O. (2005) On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Proceedings of the Thirty-Seventh 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
Ajtai, M. (1996) Generating Hard Instances of Lattice Problems. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, 22-24 May 1996, 99-108. https://doi.org/10.1145/237814.237838
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 Thirty-Third Annual ACM Symposium on Theory of Computing, Hersonissos, 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 Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Washington DC, 7-9 January 2001, 126-127.
Peikert, C. (2009) Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, Bethesda, 31 May-2 June 2009, 333-342. https://doi.org/10.1145/1536414.1536461
Ajtai, M. (2005) Representing Hard Lattices with O(n log n) Bits. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, Baltimore, 22-24 May 2005, 94-103. https://doi.org/10.1145/1060590.1060604
Ajtai, M. and Dwork, C. (1997) A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, 4-6 May 1997, 284-293. https://doi.org/10.1145/258533.258604
Alekhnovich, M. (2003) More on Average Case vs Approximation Complexity. 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, 11-14 October 2003, 298-307. https://doi.org/10.1109/SFCS.2003.1238204

Menu

On the LWE Cryptosystem with More General Disturbance

Abstract

References (25)