Gaussian Difference Dynamics: Breaking the 2^(n/2) Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling
ePrint 2026/2690
- Time bound
- 2b n+o(n) per target
- Space bound
- 2(log2(4/3)/2)n+o(n) bits
- Source / version date
- 3 Nov 2026
- Comparison variant
- Classical · preprocessing/radius tradeoffs
- Cost scale
- Parameterized query time
- Decoding radius
- 0 < r < sqrt(e b log(2))/(alpha A_KL), A_KL=2^{0.401}
- Preprocessing time
- 2^{alpha_G n+o(n)}, alpha_G=(1/2)log_2(3/2)
- Advice / space
- 2^{beta_G n+o(n)} bits, beta_G=(1/2)log_2(4/3)
- Parameter domain
- Feasible (alpha,b) in source Eq. (125), or full-batch (alpha,b)=(3/2,beta_G)
- Success guarantee
- With probability 1-o(1), one advice string correctly decodes every rational target within r lambda_1(L)
Assumptions and source notes
The full-batch choice gives any fixed radius r < 0.3157071 with query exponent beta_G and preprocessing exponent alpha_G. The entire tradeoff is stored without a fabricated fixed score.
Source location
Theorem 12.1, printed p. 59; Table 1, p. 7
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
@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}
}