Cryptology ePrint Archive: Report 2014/489

A Genetic Algorithm for Searching Shortest Lattice Vector of SVP Challenge

Dan Ding and Guizhen Zhu and Xiaoyun Wang

Abstract: In this paper, we propose a genetic algorithm for solving the shortest vector problem (SVP) based on sparse integer representations of short vectors in lattices as chromesomes, which, we prove, can guarantee finding the shortest lattice vector under a Markov chain analysis. Moreover, we also suggest some improvements by introducing heuristic techniques: local search and heuristic pruning. The experimental results show that the genetic algorithm outperforms most enumeration algorithms in running time, and achieves the shortest vectors in larger dimensions under SVP challenge benchmarks.

Category / Keywords: Shortest Vector Problem (SVP), Lattice-Based Cryptography, Genetic Algorithm, Chromesome, and Local Search.

Date: received 19 Jun 2014, last revised 24 Jun 2014

Contact author: dingd09 at mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Note: submitted to JCST

Version: 20140624:111347 (All versions of this report)

Short URL: ia.cr/2014/489

Discussion forum: Show discussion | Start new discussion