Gaussian Difference Dynamics: Breaking the $2^{n/2}$ Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling

What it is

Gaussian Difference Dynamics (GDD) is a framework from Yiming Gao, Xuyuan Han and Honggang Hu, posted as IACR ePrint 2026/2690 (received 30 October 2026, approved 4 November 2026). It is a preprint. The paper gives classical randomized algorithms in a word-RAM model for discrete Gaussian sampling (DGS) and the Shortest Vector Problem (SVP) on arbitrary lattices, and says they break the 2^{n/2} barrier for both.

Stated results

• Shifted DGS: for any fixed α > 1 and width σ ≥ α·η_{1/2}(L), it takes (3/2)^{n/2+o(n)} time and (4/3)^{n/2+o(n)} space. The authors say these match the heuristic sieving exponents of Becker, Ducas, Gama and Laarhoven (BDGL). The DGS bounds are stated as proven, not heuristic.
• Batch sampling: at widths of at least 3η_{1/2}(L)/2, the same total cost yields a batch of ⌊(4/3)^{n/2}⌋ samples that are jointly close to independent target Gaussians.
• SVP: returns a shortest nonzero vector with high probability in 2^{0.4130n+o(n)} time and 2^{0.3138n+o(n)} space.
• Centered DGS: the same exponents hold at every width, which the authors say answers a question of Stephens-Davidowitz (SODA 2016).

How it works

GDD tracks expected counts and pairwise clustering of vectors through repeated differencing. A closed recursion for the first two counting moments bounds these quantities relative to a Gaussian reference, and it does not need independence within intermediate lists.

Accurate moment bounds let the algorithm extract a Gaussian sample by weighted selection. The weaker bounds needed to establish a shortest-vector representation let it keep more differences. Both transitions happen on thin spherical shells, where the Gaussian rejection weights can be renormalized at subexponential cost. Batch sampling combines this with the double rejection technique of Doulgerakis and Laarhoven, which controls the joint distribution of outputs while reusing vectors.

Caveats

• The page is an abstract with no implementation, benchmarks or concrete parameter sets. It does not discuss any specific lattice scheme or its security estimates.
• The result is asymptotic, with o(n) terms left unquantified, so it says nothing directly about practical dimensions.
• It has not been peer reviewed. The page gives no independent verification.
• No action follows from the page. It does not state any change to recommended parameters.