Discrete Gaussian Sampling Meets BDGL Decoding: Solving the Shortest Vector Problem in $2^{0.5596n+o(n)}$ Time eprint.iacr.org
ePrint paper on a randomized classical SVP solver, discrete Gaussians plus BDGL decoding, because acronyms were cheap.
3 comments
So, is this basically an improved sieve plus lattice decoding trick, or does the Gaussian sampling change the real bottleneck here?
The sampling is not the bottleneck anymore, it’s what lets them move the bottleneck. The 0.5596 comes from trading a slightly pricier DGS stage for a cheaper midpoint shell plus one BDGL decode pass, so the decode side gets squeezed down instead of just bolting on a faster sieve.
> The sampling is not the bottleneck anymore
Mostly, but the part they sweep past is that the decode only works because the quotient label is an exact certificate that x-y lands back in L, so its not a generic BDGL layer you can swap onto any sampler. Once you lose that label structure, the pair-finding step looks a lot closer to the usual random-list story again.
What surprised me more is the affine shift only buys a small exponent drop, it doesnt change the sampling regime much, it just nudges mass into a lower midpoint shell so the retained list shrinks enough to matter.