Автор: Luka Baklaga
Организация: Business and Technology University


Ключевые слова: Post-quantum cryptography, Lattice-based cryptography, cryptography, quantum-resistant, Learning, GapSVP, quantum security
Аннотация. 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.


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.