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

Heuristic · classical

Cost scale

2^{c n + o(n)}

norm

Euclidean ℓ₂

heuristic

Gaussian heuristic in overlattice towers and translated cosets

Source locator

Abstract and Table 1 of ePrint 2013/685

Computation model

Classical; Gaussian heuristic for the intermediate overlattice samples

Preprocessing cost

Initialization and target handling included in the displayed total cost

Assumptions and source notes

Heuristic exact CVP via overlattice towers and translated cosets, under Gaussian-heuristic assumptions for intermediate samples. The displayed total cost includes initialization and target handling as specified in the source. This is distinct from an unrestricted worst-case theorem and from a preprocessing-only online query cost.

Source location

Abstract and Table 1; CVP adaptation in the algorithm analysis
Version: ePrint 2013/685; first public preprint 24 October 2013

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.}
}