DGS / Classical · shifted · above smoothing · one sample

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: (3/2)^n/2+o(n)
Space bound: (4/3)^n/2+o(n)

Source / version date: 3 Nov 2026
Comparison variant: Classical · shifted · above smoothing · one sample
Cost scale: 2^{c n + o(n)}
Width requirement: s >= alpha eta_{1/2}(L), any fixed alpha > 1
Output: One sample on any rational shift L+a
Distribution error: TV <= exp(-Omega(n/log^{2+xi}(n+2))), fixed xi > 0
Cost model: Randomized word RAM; time and bit space bounded on every execution

Assumptions and source notes

Exact logarithmic coefficients are used rather than rounded 0.292/0.208. This theorem concerns widths above smoothing.

Source location

Theorem 1.1, printed p. 6
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}
}