Paper 2014/980 Original: eprint.iacr.org/2014/980 ↗
A Fast Phase-Based Enumeration Algorithm for SVP Challenge through y-Sparse Representations of Short Lattice Vectors
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
- Preprint.
- History
- 2014-12-07: last updated
- 2014-12-07: published
- Short URL
- https://ia.cr/2014/980
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2014/980}
}