Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem

Xiaoyun Wang; Mingjie Liu; Chengliang Tian; Jingguo Bi

Paper 2010/647

Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem

Xiaoyun Wang, Mingjie Liu, 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.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security (ASIACCS 2011)
Keywords: lattice shortest vector sieve heuristic sphere covering
Contact author(s): xiaoyunwang @ mail tsinghua edu cn
liu-mj07 @ mails tsinghua edu cn
History: 2011-08-28: last of 3 revisions; 2010-12-21: received; See all versions
Short URL: https://ia.cr/2010/647
License: CC BY

BibTeX

@misc{cryptoeprint:2010/647,
      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},
      url = {https://eprint.iacr.org/2010/647}
}