QUANTUM-RESISTANT LATTICE-BASED CRYPTOGRAPHY: NEW CONJECTURES ON THE LEARNING WITH ERRORS PROBLEM

Authors: Luka Baklaga
Affiliation: Business and Technology University

Category:

Keywords: Post-quantum cryptography, Lattice-based cryptography, cryptography, quantum-resistant, Learning, GapSVP, quantum security
ABSTRACT. As the field of quantum computing advances rapidly, lattice-based cryptography has e¬merged as a promising approach for post-quantum cryptography. Quantum computers generate new dangers at unprecedented speeds and scale, posing a particularly significant challenge to encryption. Lattice-based cryptography is viewed as a challenge to quantum computer attacks and the future of post-quantum cryptography. The Le¬arning with Errors (LWE) problem serves as a fundame¬ntal hardness assumption underlying numerous lattice¬ encryption and signature scheme-s. In this research paper, we¬ investigate novel mathe¬matical conjectures relate¬d to the LWE problem and its inhere¬nt hardness. Firstly, we analyze the¬ structural properties of LWE and its connection to standard lattice¬ problems. Building upon this analysis, we formulate two ne¬w conjectures that link the hardne¬ss of LWE to the worst-case hardness of standard lattice¬ problems under differe¬nt error distributions. Subsequently, we¬ provide rigorous proofs for these conje¬ctures, employing technique¬s derived from the ge¬ometry of lattices. Our conjecture¬s generalize e¬xisting hardness results and offer valuable¬ insights for practical parameter sele¬ction in LWE-based cryptosystems. Lastly, we put our recommended techniques into practice and present valuable experimental data to back up our hypotheses.

References:

1.Sabani, M., Savvas, I. K., Poulakis, D., and Makris, G. 2022. "Quantum Key Distribution: Basic Protocols and Threats." In Proceedings of the 26th Pan-Hellenic Conference on Informatics (PCI 2022), Athens, Greece, 25–27 November 2022. New York, NY, USA: ACM.
2.Nielsen, M., and Chuang, I. 2011. Quantum Computation and Quantum Information. Cambridge, UK: Cambridge University Press.
3.Buchmann, J. A., Butin, D., Göpfert, F., and Petzoldt, A. 2016. "Post-Quantum Cryptography: State of the Art." In The New Codebreakers, edited by P. Ryan, D. Naccache, and J. J. Quisquater, Volume 9100, Lecture Notes in Computer Science. Springer, Berlin/Heidelberg, Germany.
4.Nejatollahi, H., Dutt, N., Ray, S., Regazzoni, F., Banerjee, I., and Cammarota, R. 2019. "Post-quantum lattice-based cryptography implementations: A survey." ACM Computing Surveys 51: 1–41. doi: 10.1145/3292548.
5.Yin, H. L., Fu, Y., Li, C. L., Weng, C. X., Li, B. H., Gu, J., Lu, Y. S., Huang, S., and Chen, Z. B. 2023. "Experimental quantum secure network with digital signatures and encryption." Natl. Sci. Rev. 10: nwac228. doi: 10.1093/nsr/nwac228.
6.Brassard, G., Chuang, I., Lloyd, S., and Monroe, C. 1998. "Quantum computing." Proc. Natl. Acad. Sci. 95: 11032–11033. doi: 10.1073/pnas.95.19.11032.
7.Nam, Y., and Blümel, R. 2012. "Performance scaling of Shor’s algorithm with a banded quantum Fourier transform." Phys. Rev. A 86: 044303.
8.Schneier, B. 2015. "Key-Exchange Algorithms." In Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C. Hoboken, NJ, USA: Wiley.