Sieving for shortest vectors in lattices using angular locality-sensitive hashing

Thijs Laarhoven

Crypto 2015

Time bound

2^{0.3366 n + o(n)}

Space bound

2^{0.2075 n + o(n)}

Source / version date

26 Sept 2014

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

Nguyen–Vidick list-distribution heuristic

reference

Laa15

Assumptions and source notes

CRYPTO 2015; first ePrint 26 September 2014. Charikar angular LSH accelerates the pair search. The source gives heuristic time 0.3366 and space 0.2075 for its Nguyen–Vidick variant. The practical GaussSieve-based HashSieve has a separate conjectured time/space bound 0.3366/0.3366; the smaller-space NV bound should not be attributed to that implementation.

Primary source ↗

@misc{paper-1156d8d47edf,
  author = {Thijs Laarhoven},
  title = {{Sieving for shortest vectors in lattices using angular locality-sensitive hashing}},
  year = {2015},
  url = {https://eprint.iacr.org/2014/744},
  cr_date = {2014-09-26},
  cr_status = {published},
  cr_venue = {CRYPTO 2015},
  cr_author_ids = {thijs-laarhoven},
  howpublished = {Cryptology {ePrint} Archive, Paper 2014/744}
}