Faster Provable Lattice Sieving with Spherical Codes

What it is

A provable (not heuristic) sieving algorithm for μ-SVP by Aggarwal, Morolia, and Stephens-Davidowitz, restricted to large constant approximation factors μ (it does not handle μ=1, exact SVP). The paper also flags a concurrent, independent work by Hhan (2026) achieving a 2^(n/2)-time provable algorithm that does solve μ=1.

How it works

The algorithm combines the fast nearest-neighbor subroutines used in heuristic sieving with the perturbation argument used in prior provable sieving. The proven running time is governed by a geometric quantity: the maximal size of certain spherical codes. Plugging in a plausible assumption about that maximal code size gives ~2^0.3066n; falling back to the best currently proven upper bound on spherical-code size (which the authors say is "almost certainly quite loose") gives ~2^0.6078n instead.

Preconditions / Affected

Results apply only for large constant μ (approximation factor), not for exact or near-exact SVP (μ=1). The headline 2^0.3066n figure is conditional on an unproven spherical-code-size assumption; the unconditional, fully proven bound is 2^0.6078n.

Caveats

• The concurrent Hhan (2026) algorithm runs in 2^(n/2) ≈ 2^0.5n — faster than this paper's unconditional 2^0.6078n bound, and it also covers μ=1, which this paper's method does not.
• The paper's best figure (2^0.3066n) is not unconditionally proven; it depends on a spherical-code assumption the authors call "reasonable" but not established.
• Because the technique excludes μ=1, it cannot be directly compared to algorithms (like Hhan's) solving exact SVP — the two results address different problem variants, so "faster" claims should be read with that scope restriction in mind.