Shortest Vector from Lattice Sieving: a Few Dimensions for Free

Léo Ducas

Eurocrypt 2018

Time bound

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

Space bound

—

Source / version date

11 Oct 2017

Comparison variant

Classical · heuristic

Cost scale

2^{c n + o(n)}

Norm

Euclidean ℓ₂

Success guarantee

Under the underlying sieve and reduction heuristics

Computation model

Classical; underlying sieve oracle with subexponential dimension saving

Heuristic assumption

Underlying sieve-distribution heuristic and dimensions-for-free analysis

Assumptions and source notes

Reduces dimension n to a few sieve calls in dimensions below n − d, where d = Θ(n/log n). Applying this to the cited spherical-filter sieve preserves its leading coefficient ½log₂(3/2), while improving the subexponential factor. The row therefore ties the standing exponent; it is not a new exponent record. The paper also implements a simpler (4/3)^n sieve. No separate total-space coefficient is inferred from the checked abstract.

Source location

Abstract, paragraphs 1–3; ePrint history; institutional EUROCRYPT 2018 publication record
Version: First ePrint received 11 October 2017; minor revision 26 October 2017

Primary source ↗

@inproceedings{ducas-2017-dimensions-free,
  author = {Léo Ducas},
  title = {{Shortest Vector from Lattice Sieving: a Few Dimensions for Free}},
  booktitle = {EUROCRYPT 2018},
  year = {2018},
  doi = {10.1007/978-3-319-78381-9_5},
  url = {https://eprint.iacr.org/2017/999},
  keywords = {SVP, lattice sieving, dimensions for free, subexponential improvement},
  cr_date = {2017-10-11},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {EUROCRYPT 2018},
  cr_author_ids = {leo-ducas}
}