A Genetic Algorithm for Searching Shortest Lattice Vector of SVP Challenge

Dan Ding; Guizhen Zhu; Xiaoyun Wang

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2014/489

A Genetic Algorithm for Searching Shortest Lattice Vector of SVP Challenge

Dan Ding, 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.

Note: submitted to JCST

Metadata

Available format(s): PDF
Publication info: Preprint. MAJOR revision.
Keywords: Shortest Vector Problem (SVP)Lattice-Based Cryptography Genetic Algorithm Chromesome and Local Search.
Contact author(s): dingd09 @ mails tsinghua edu cn
History: 2014-06-24: revised; 2014-06-23: received; See all versions
Short URL: https://ia.cr/2014/489
License: CC BY

BibTeX

@misc{cryptoeprint:2014/489,
      author = {Dan Ding and Guizhen Zhu and Xiaoyun Wang},
      title = {A Genetic Algorithm for Searching Shortest Lattice Vector of SVP Challenge},
      howpublished = {Cryptology ePrint Archive, Paper 2014/489},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/489}},
      url = {https://eprint.iacr.org/2014/489}
}