Tailoring a Genetic Algorithm for searching Shortest Lattice Vector in NTRU Lattices

• Raul Caram de Assis Cepesc http://orcid.org/0009-0003-8572-7072
• Thiago do Rêgo Sousa Cepesc http://orcid.org/0000-0002-0776-034X

DOI: https://doi.org/10.5753/sbseg.2025.10635

Abstract

The NTRU cryptosystem relies on the hardness of the Shortest Vector Problem (SVP), a central challenge in lattice-based cryptography. While genetic algorithms (GAs) have shown promise in solving SVP on generic lattices, little attention has been given to applying it to cryptographic structures like NTRU. In this work, we investigate the suitability of a GA specifically tailored to NTRU lattices. Our approach involves searching outside the lattice and analyzing a cost function whose behavior appears smoother when using BKZ-reduced bases. We present initial observations and outline directions for future research.

References

Ajitha, S. K., Biswas, S., and Kurur, P. P. (2011). Metropolis algorithm for solving shortest lattice vector problem (svp). In 2011 11th International Conference on Hybrid Intelligent Systems (HIS), pages 442–447. IEEE.

Darmstadt lattice challenge. Svp challenge hall of fame. [link]. Accessed: 2025-04-22.

Ding, D. and Zhu, G. (2014). A random sampling algorithm for svp challenge based on y-sparse representations of short lattice vectors. In 2014 Tenth International Conference on Computational Intelligence and Security, pages 425–429. IEEE.

Ding, D., Zhu, G., and Wang, X. (2015). A genetic algorithm for searching the shortest lattice vector of svp challenge. In Proceedings of the 2015 annual conference on genetic and evolutionary computation, pages 823–830.

Fukase, M. and Kaminaga, M. (2022). Improving genetic algorithms for solving the svp: focusing on low memory consumption and high reproducibility. Iran Journal of Computer Science, 5(4):359–372.

Fukase, M. and Kashiwabara, K. (2015). An accelerated algorithm for solving svp based on statistical analysis. Journal of Information Processing, 23(1):67–80.

Hoffstein, J. (2008). An introduction to cryptography. In An Introduction to Mathematical Cryptography, pages 1–58. Springer.

Hoffstein, J., Pipher, J., and Silverman, J. H. (1998). Ntru: A ring-based public key cryptosystem. In International algorithmic number theory symposium, pages 267–288. Springer.

Luan, L., Gu, C., and Zheng, Y. (2020). A genetic algorithm with restart strategy for solving approximate shortest vector problem. In 2020 12th International Conference on Advanced Computational Intelligence (ICACI), pages 243–250. IEEE.

Moghissi, G. R. and Payandeh, A. (2019). A parallel evolutionary search for shortest vector problem. International Journal of Information Technology and Computer Science.

Reddy, V. D. and Rao, G. (2021). Meta-heuristic approaches to solve shortest lattice vector problem. Journal of Discrete Mathematical Sciences and Cryptography, 24(1):81–91.

Silverman, J. H., Pipher, J., and Hoffstein, J. (2008). An introduction to mathematical cryptography, volume 1. Springer.