Efficient (ideal) lattice sieving using cross-polytope LSH

Anja Becker · Thijs Laarhoven

Africacrypt 2016

Time bound

2^{0.2972 n + o(n)}

Space bound

—

Source / version date

24 Aug 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

GaussSieve heuristic; cross-polytope LSH

reference

BL16

Assumptions and source notes

AFRICACRYPT 2016; first ePrint 24 August 2015. Independently reaches the 0.298 time level through efficiently computable cross-polytope hashes, improving practicality over SphereSieve. The abstract applies to arbitrary and ideal lattices. A numeric space coefficient is not inferred from the abstract; consult the chosen variant. Theorem 1 gives 0.2972, often rounded to 0.298 in the abstract; this is a precision normalization, not a new algorithmic improvement.

Source location

Theorem 1; identical asymptotic collision analysis to spherical LSH
Version: AFRICACRYPT 2016 paper, originally ePrint 2015/823

Primary source ↗

@misc{paper-777c2d2d89d5,
  author = {Anja Becker and Thijs Laarhoven},
  title = {{Efficient (ideal) lattice sieving using cross-polytope LSH}},
  year = {2016},
  doi = {10.1007/978-3-319-31517-1_1},
  url = {https://eprint.iacr.org/2015/823},
  cr_date = {2015-08-24},
  cr_status = {published},
  cr_venue = {AFRICACRYPT 2016},
  cr_author_ids = {anja-becker; thijs-laarhoven},
  howpublished = {Cryptology {ePrint} Archive, Paper 2015/823}
}