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

Ideal lattices · heuristic

Cost scale

2^{c n + o(n)}

Norm

Euclidean ℓ₂ under the source embedding

Heuristic assumption

Ideal-lattice / GaussSieve heuristic

Reference

BL16

structure

Cyclotomic ideal lattices

Assumptions and source notes

The source gives the same 0.298 leading time coefficient for arbitrary and ideal lattices. For suitable cyclotomic ideal lattices, rotational symmetry yields linear-factor improvements in both time and space. These polynomial gains are not a smaller exponential coefficient. The selected ring and embedding must be specified for concrete comparisons. 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}
}