Gaussian Difference Dynamics: Breaking the 2^(n/2) Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling
ePrint 2026/2690
- Time bound
- 20.4130 n + o(n)
- Space bound
- 20.3138 n + o(n)
- Source / version date
- 30 Oct 2026
- Comparison variant
- Classical · worst case
- Cost scale
- 2c n + o(n)
- Norm
- Euclidean ℓ₂
- Success guarantee
- High probability
- Computation model
- Word RAM
- reference
- GHH26
Assumptions and source notes
Preprint claim for arbitrary lattices in a word-RAM model, returning a shortest vector with high probability. Also arXiv:2611.04336. Source checked; proof not independently audited.
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
@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}
}