Paper 2014/980

A Fast Phase-Based Enumeration Algorithm for SVP Challenge through y-Sparse Representations of Short Lattice Vectors

Dan Ding, Guizhen Zhu, Yang Yu, and Zhongxiang Zheng

Abstract

In this paper, we propose a new phase-based enumeration algorithm based on two interesting and useful observations for y-sparse representations of short lattice vectors in lattices from SVP challenge benchmarks. Experimental results show that the phase-based algorithm greatly outperforms other famous enumeration algorithms in running time and achieves higher dimensions, like the Kannan-Helfrich enumeration algorithm. Therefore, the phase-based algorithm is a practically excellent solver for the shortest vector problem (SVP).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. ICISC 2014
Keywords
Lattice-based Xryptography
Contact author(s)
dingd09 @ mails tsinghuaa edu cn
History
2014-12-07: received
Short URL
https://ia.cr/2014/980
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/980,
      author = {Dan Ding and Guizhen Zhu and Yang Yu and Zhongxiang Zheng},
      title = {A Fast Phase-Based Enumeration Algorithm for SVP Challenge through y-Sparse Representations of Short Lattice Vectors},
      howpublished = {Cryptology ePrint Archive, Paper 2014/980},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/980}},
      url = {https://eprint.iacr.org/2014/980}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.