A Genetic Algorithm with Restart Strategy for Solving Approximate Shortest Vector Problem

The shortest vector problem(SVP) is a famous hard problem in lattice-based cryptography. In this paper, we propose a genetic algorithm for solving approximate shortest vector problem with restart strategy. The genetic algorithm is based on natural number representation proposed by Fukase [1]. We introduce the concept and properties of natural number representation, and encode lattice vector into natural number vector as chromosome. To avoid local stagnation, we propose a restart strategy utilizing good individuals to reduce lattice basis and improve the property of lattice basis, which is enlightened by random sampling reduction algorithms. The genetic algorithm with restart outperforms some SVP challenge records and classic enumeration algorithms on lattices under 100 dimension in practice, and its implementation efficiency is close to the state-of-art enumeration technique of extreme pruning.