New directions in nearest neighbor searching with applications to lattice sieving

Anja Becker · Léo Ducas · Nicolas Gama · Thijs Laarhoven

SODA 2016

Time bound

(3/2)^{n/2 + o(n)}

Space bound

2^{0.20751874963942188 n + o(n)}

Source / version date

23 Nov 2015

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

Sieve-list distribution / geometric heuristic

reference

BDGL16

Assumptions and source notes

SODA 2016; first ePrint 23 November 2015. Spherical filters from structured random product codes yield heuristic time coefficient ½log₂(3/2) ≈ 0.2925 and space coefficient ½log₂(4/3) ≈ 0.2075. The list-distribution assumption remains heuristic; this is distinct from a Haar-random-lattice theorem.

Primary source ↗

@misc{paper-1bcb4e64b5f3,
  author = {Anja Becker and Léo Ducas and Nicolas Gama and Thijs Laarhoven},
  title = {{New directions in nearest neighbor searching with applications to lattice sieving}},
  year = {2016},
  url = {https://eprint.iacr.org/2015/1128},
  cr_date = {2015-11-23},
  cr_status = {published},
  cr_venue = {SODA 2016},
  cr_author_ids = {anja-becker; leo-ducas; nicolas-gama; thijs-laarhoven},
  howpublished = {Cryptology {ePrint} Archive, Paper 2015/1128}
}