DGS / Arbitrary width · worst case

Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling

Divesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz

STOC 2015

PublishedSource checked

Time bound: 2^{1 n + o(n)}
Space bound: 2^{1 n + o(n)}

Source / version date: 26 Dec 2014
Comparison variant: Arbitrary width · worst case
Cost scale: 2^{c n + o(n)}
Width restriction: Any positive Gaussian parameter
Output samples: 2^{n/2} samples
Distribution error: As specified by the source theorem
Computation model: Randomized classical; preprocessing included
reference: ADRS15

Assumptions and source notes

STOC 2015; first arXiv date shown. Total cost for a batch of 2^{n/2} samples (abstract). Retaining one sample gives the displayed upper bound.

Selected earlier references

Selected sources cited by this paper.

A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
Daniele Micciancio · Panagiotis Voulgaris · 2013
Uses the previous exact-CVP/Voronoi bound as the comparison point for 1.97-approximate CVP. Abstract; introduction
On the Closest Vector Problem with a Distance Guarantee
Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz · 2014
Combines the distance-guaranteed decoder with above-smoothing DGS to charge construction of the Gaussian advice and obtain 0.422-BDD in half-exponent total time. §7.2, Theorem 7.3 explicitly attributed to DRS14 Theorem 3.1

Primary source ↗

BibTeXDownload .bib

@misc{paper-86925aff6e6c,
  author = {Divesh Aggarwal and Daniel Dadush and Oded Regev and Noah Stephens-Davidowitz},
  title = {{Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling}},
  year = {2015},
  url = {https://arxiv.org/abs/1412.7994},
  cr_date = {2014-12-26},
  cr_status = {published},
  cr_venue = {STOC 2015},
  cr_author_ids = {divesh-aggarwal; daniel-dadush; oded-regev; noah-stephens-davidowitz},
  howpublished = {STOC 2015; arXiv:1412.7994}
}