DGS / Classical · centered · arbitrary width · inverse-polynomial error

Gaussian Difference Dynamics: Breaking the 2^(n/2) Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling

Yiming Gao · Xuyuan Han · Honggang Hu

ePrint 2026/2690

PreprintSource checked

Time bound: 2^0.4130n+o(n) per sample
Space bound: 2^0.3138n+o(n)

Source / version date: 3 Nov 2026
Comparison variant: Classical · centered · arbitrary width · inverse-polynomial error
Cost scale: 2^{c n + o(n)}
Width requirement: Every positive rational width on any rational full-rank lattice
Output: One centered sample
Accuracy convention: (1+1/f(n),2^{-f(n)}) accuracy for efficiently computable 1 <= f(n) <= poly(n); implies TV O(1/f(n))+2^{-f(n)}
Cost model: Randomized classical with polynomial reduction overhead

Assumptions and source notes

Uses a corrected centered-DGS-to-SVP reduction; Appendix D identifies and repairs the radius-grid issue in the earlier reduction. Accuracy is weaker than negligible TV.

Source location

Corollary 1.4, printed p. 7; §12.4 and Appendix D
Version: arXiv:2611.04336v1, 3 November 2026; first ePrint release 30 October not inspected separately

Selected earlier references

Selected sources cited by this paper.

One Discrete Gaussian Sample in 2^{n/2+o(n)} Time
Jiseung Kim · 2026
Identifies the preceding half-exponent algorithm for one centered sample at arbitrary width. §1.1 literature discussion
Discrete Gaussian Sampling Reduces to CVP and SVP
Noah Stephens-Davidowitz · 2016
Uses the centered-to-SVP reduction framework, reports a radius-grid problem in its proof, and supplies a corrected argument. Corollary 1.4; §12.4; Appendix D
On the Closest Vector Problem with a Distance Guarantee
Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz · 2014
Uses dual Gaussian batches as reusable advice for the periodic-Gaussian decoder while accounting for preprocessing and query costs. §12.2; Theorem 12.1 proof; Appendix F.1

Primary source ↗

BibTeXDownload .bib

@misc{paper-fd038bb9c63f,
  author = {Yiming Gao and Xuyuan Han and Honggang Hu},
  title = {{Gaussian Difference Dynamics: Breaking the 2^(n/2) Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling}},
  year = {2026},
  url = {https://eprint.iacr.org/2026/2690},
  cr_date = {2026-10-30},
  cr_status = {preprint},
  cr_author_ids = {yiming-gao; xuyuan-han; honggang-hu},
  howpublished = {Cryptology ePrint Archive, Paper 2026/2690}
}