Cryptology ePrint Archive: Report 2010/647

Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem

Xiaoyun Wang and Mingjie Liu and Chengliang Tian and Jingguo Bi

Abstract: In this paper, we present an improvement of the Nguyen-Vidick heuristic sieve algorithm for shortest vector problem in general lattices, which time complexity is 2^0.3836n polynomial computations, and space complexity is 2^0.2557n. In the new algorithm, we introduce a new sieve technique with two-level instead of the previous one-level sieve, and complete the complexity estimation by calculating the irregular spherical cap covering.

Category / Keywords: lattice, shortest vector, sieve, heuristic, sphere covering

Publication Info: Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security (ASIACCS 2011)

Date: received 18 Dec 2010, last revised 28 Aug 2011

Contact author: xiaoyunwang at mail tsinghua edu cn,liu-mj07 at mails tsinghua edu cn

Available formats: PDF | BibTeX Citation

Version: 20110828:131448 (All versions of this report)

Discussion forum: Show discussion | Start new discussion