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
latticeshortest vectorsieveheuristicsphere 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2010/647}},
      url = {https://eprint.iacr.org/2010/647}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.