Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem

Xiaoyun Wang · Mingjie Liu · Chengliang Tian · Jingguo Bi

AsiaCCS 2011

Time bound

2^{0.3836 n + o(n)}

Space bound

2^{0.2557 n + o(n)}

Source / version date

21 Dec 2010

Comparison variant

Classical · heuristic

Cost scale

2^{c n + o(n)}

Norm

Euclidean ℓ₂

Success guarantee

Under the stated sieve heuristic

Computation model

Classical randomized; polynomial factors suppressed

Heuristic assumption

Uniform sieve lists; two-level spherical covering

reference

WLTB11

Assumptions and source notes

ASIACCS 2011; first ePrint received 21 December 2010. The source states time coefficient 0.3836 and space 0.2557. Two-level sphere covering trades additional memory for a better time exponent. Uses the Nguyen–Vidick sieve heuristic.

Primary source ↗

@misc{paper-0d12f3e7f365,
  author = {Xiaoyun Wang and Mingjie Liu and Chengliang Tian and Jingguo Bi},
  title = {{Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem}},
  booktitle = {Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security},
  year = {2011},
  doi = {10.1145/1966913.1966915},
  url = {https://eprint.iacr.org/2010/647},
  cr_date = {2010-12-21},
  cr_status = {published},
  cr_venue = {AsiaCCS 2011},
  cr_author_ids = {xiaoyun-wang; mingjie-liu; chengliang-tian; jingguo-bi},
  howpublished = {Cryptology {ePrint} Archive, Paper 2010/647}
}