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.
References
[1]
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
[2]
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
[3]
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
[4]
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
[5]
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
[6]
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.
[7]
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
[8]
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.
[9]
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
[10]
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
[11]
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
[12]
Brakerski, Z. and Vaikuntanathan, V. (2011) Efficient Fully Homomorphic Encryption from (Standard) LWE. IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, 22-25 October 2011, 831-871. https://doi.org/10.1109/FOCS.2011.12
[13]
Gentry, C., Sahai, A. and Waters, B. (2013) Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. Annual Cryptology Conference, Santa Barbara, 18-22 August 2013, 75-92. https://doi.org/10.1007/978-3-642-40041-4_5
[14]
Islam, M., Islam, M., Islam, N. and Shabnam, B. (2018) A Modified and Secured RSA Public Key Cryptosystem Based on “n” Prime Numbers. Journal of Computer and Communications, 6, 78-90. https://doi.org/10.4236/jcc.2018.63006
[15]
Impagliazzo, R. and Zuckerman, D. (1989) How to Recycle Random Bits. Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Research Triangle Park, 30 October-1 November 1989, 248-253. https://doi.org/10.1109/SFCS.1989.63486
[16]
Riauba, B. (1975) A Central Limit Theorem for Dependent Random Variables. Lithuanian Mathematical Journal, 15, 185-200. https://doi.org/10.1007/BF00975432
