Paper 2010/647

Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem

Xiaoyun Wang, Mingjie Liu, Chengliang Tian, and Jingguo Bi


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.

Available format(s)
Publication info
Published elsewhere. Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security (ASIACCS 2011)
latticeshortest vectorsieveheuristicsphere covering
Contact author(s)
xiaoyunwang @ mail tsinghua edu cn
liu-mj07 @ mails tsinghua edu cn
2011-08-28: last of 3 revisions
2010-12-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiaoyun Wang and Mingjie Liu and Chengliang Tian and Jingguo Bi},
      title = {Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2010/647},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.