Solving shortest and closest vector problems: The decomposition approach

Anja Becker · Nicolas Gama · Antoine Joux

ANTS 2014

Time bound

2^{0.3774 n + o(n)}

Space bound

2^{0.2925 n + o(n)}

Source / version date

24 Oct 2013

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

Gaussian heuristic for intermediate overlattices and cosets

reference

BGJ14

Assumptions and source notes

ANTS 2014, published under “A sieve algorithm based on overlattices”; first ePrint 24 October 2013. A tower of overlattices and translated cosets replaces a single-lattice sieve. The stated decimal coefficients are rounded: time 0.3774 and memory 0.2925. Analysis depends on the Gaussian heuristic, rather than an arbitrary-lattice correctness theorem.

Primary source ↗

@misc{paper-9617f5d3fa09,
  author = {Anja Becker and Nicolas Gama and Antoine Joux},
  title = {{Solving shortest and closest vector problems: The decomposition approach}},
  year = {2014},
  url = {https://eprint.iacr.org/2013/685},
  cr_date = {2013-10-24},
  cr_status = {published},
  cr_venue = {ANTS 2014},
  cr_author_ids = {anja-becker; nicolas-gama; antoine-joux},
  howpublished = {Cryptology {ePrint} Archive, Paper 2013/685},
  note = {The main part appeared at ANTS 2014 under the title A Sieve Algorithm Based on Overlattices; this linked full version retains its original title and an additional section.}
}