Cryptology ePrint Archive: Report 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, 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).

Category / Keywords: public-key cryptography / Lattice-based Xryptography

Original Publication (with minor differences): ICISC 2014

Date: received 3 Dec 2014

Contact author: dingd09 at mails tsinghuaa edu cn

Available format(s): PDF | BibTeX Citation

Version: 20141207:153158 (All versions of this report)

Short URL: ia.cr/2014/980

Discussion forum: Show discussion | Start new discussion