A Genetic Algorithm for Searching the Shortest Lattice Vector of SVP Challenge

In this paper, we propose a genetic algorithm for solving the shortest vector problem (SVP) based on sparse representation of short lattice vectors, which, we prove, can guarantee finding the shortest lattice vector under a Markov analysis. With some heuristic improvements (local search and heuristic pruning), the SVP genetic algorithm, by experimental results, outperforms other SVP algorithms, like the famous Kannan-Helfrich algorithm under SVP challenge benchmarks. In summary, we, for the first time, adopt the genetic algorithm in solving the shortest vector problem, based on which lattice-based cryptosystem is as a promising candidate for post-quantum cryptography.