Feasibility Analysis and Optimization of Non-Gaussian Error Distributions in LWE-based Cryptosystems: A Step Distribution Approach
DOI:
https://doi.org/10.54097/xs866e22Keywords:
Learning with Errors, non-Gaussian Error Distribution, Step Distribution, Lattice-based Cryptography, Post-quantum Security, Decryption CorrectnessAbstract
The Learning with Errors (LWE) problem is a fundamental hardness assumption for post-quantum lattice-based cryptography. Standard LWE schemes rely on discrete Gaussian error distributions, which incur high sampling overhead. This paper explores the feasibility of replacing the Gaussian distribution with a novel non-Gaussian alternative—the Step Distribution—within Regev’s classic LWE public-key encryption scheme. The Step Distribution partitions the error range into equal-width steps, with probabilities proportional to Gaussian weights at step midpoints. The distribution is formally defined, its asymptotic convergence to the discrete Gaussian is proved, and conditions under which the decryption error probability becomes negligible are derived. The Step Distribution offers a tunable parameter—the number of steps—that allows a trade-off between security (closeness to the Gaussian) and computational efficiency. This work provides a flexible error distribution for LWE-based cryptosystems, particularly suitable for resource-constrained environments.
Downloads
References
[1] Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509. https:// doi. org/ 10.1137/S0097539795293172.
[2] Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6), 1–40. https://doi.org/10.1145/1562164.1562166.
[3] Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., & Seiler, G. (2018). CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM. In 2018 IEEE European Symposium on Security and Privacy (EuroS&P) (pp. 353–367). IEEE. https://doi.org/ 10.1109/ EuroSP. 2018.00032.
[4] Lyubashevsky, V., Peikert, C., & Regev, O. (2013). On ideal lattices and learning with errors over rings. Journal of the ACM, 60(6), 1–35. https://doi.org/10.1145/2535929.
[5] Sun, X. C., Li, B., & Lu, X. H. (2014). LWE problem with uniform secret and errors and its application. Journal of Computer Research and Development, 51(7), 1515–1519. (In Chinese.) https://doi.org/10.3724/SP.J.1123.2014.001515.
[6] Applebaum, B., Cash, D., Peikert, C., & Sahai, A. (2009). Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In S. Halevi (Ed.), Advances in Cryptology — CRYPTO 2009 (Vol. 5677, pp. 595–618). Springer. https://doi.org/10.1007/978-3-642-03356-8_35.
[7] Bai, S., & Galbraith, S. D. (2014). An improved compression technique for signatures based on learning with errors. In J. Benaloh (Ed.), Topics in Cryptology — CT-RSA 2014 (Vol. 8366, pp. 28–47). Springer. https://doi.org/10.1007/978-3-319-04801-1_2.
[8] Micciancio, D., & Peikert, C. (2012). Trapdoors for lattices: Simpler, tighter, faster, smaller. In D. Pointcheval & T. Johansson (Eds.), Advances in Cryptology — EUROCRYPT 2012 (Vol. 7237, pp. 700–718). Springer. https://doi.org/ 10. 1007/ 978-3-642-29011-4_41.
[9] Chen, Y., & Nguyen, P. Q. (2011). BKZ 2.0: Better lattice security estimates. In D. H. Lee & X. Wang (Eds.), Advances in Cryptology — ASIACRYPT 2011 (Vol. 7073, pp. 1–20). Springer. https://doi.org/10.1007/978-3-642-25385-0_1.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Frontiers in Computing and Intelligent Systems
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
