A New Lattice Reduction Algorithm Based on Genetic Strategy

Lattice reduction algorithms play an important role in the field of cryptanalysis. In this paper, based on the strategies of genetic algorithm, a new lattice reduction algorithm is proposed through the transformation of the initial lattice basis. The new algorithm always can obtain a shorter vector and a higher quality basis compared with the original algorithms. By the new algorithm, some lattice bases of the Shortest Vector Problem (SVP) challenge are experienced and the outputs of the new algorithm can always reach or break the records on the internet which illustrates that the new algorithm behaves well.