Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search

Anja Becker · Nicolas Gama · Antoine Joux

ePrint 2015/522

Time bound

2^{0.3112 n + o(n)}

Space bound

2^{0.2075 n + o(n)}

Source / version date

31 May 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 heuristic; geometric reduction to binary nearest-neighbor search

reference

BGJ15

Assumptions and source notes

A low-memory improvement, rather than a chronological time record after SphereSieve. The source states heuristic time 0.3112 while retaining space 0.2075. The method adapts nearest-neighbor search for binary codes. First ePrint received 31 May 2015; source publication status is preprint.

Primary source ↗

@misc{paper-2f67f6ebf8c0,
  author = {Anja Becker and Nicolas Gama and Antoine Joux},
  title = {{Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search}},
  year = {2015},
  url = {https://eprint.iacr.org/2015/522},
  cr_date = {2015-05-31},
  cr_status = {preprint},
  cr_author_ids = {anja-becker; nicolas-gama; antoine-joux},
  howpublished = {Cryptology {ePrint} Archive, Paper 2015/522}
}