Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem

Xiaoyun Wang; Mingjie Liu; Chengliang Tian; Jingguo Bi

Paper 2010/647 Original: eprint.iacr.org/2010/647 ↗

Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem

Xiaoyun Wang

Mingjie Liu

Chengliang Tian

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: Preprint.
History: 2011-08-28: last updated; 2010-12-21: published
Short URL: https://ia.cr/2010/647
License: https://creativecommons.org/licenses/by/4.0/

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}
}