Subexponential Algorithms for LWE via Rejection Sampling on Superlattices

What it is

A preprint (Cryptology ePrint 2026/2640, received 26 October 2026) by Ligeng Fan, Changpeng Shao, Hongbo Li and Dingkang Wang. It gives two provable classical LWE algorithms built on the Ducas, Engelberts and Loyer superlattice framework. Both use rejection sampling to fix the distribution of lattice samples. The page is the abstract only, so the details below come from it.

How it works

The Ducas, Engelberts and Loyer framework already gave a subexponential algorithm for infinity-norm SIS. The authors name an obstacle to extending it to LWE. Kirchner and Fouque hit a similar problem, and their claimed subexponential time with linearly many samples was never rigorously established.

The paper has two refinements:

• Shift normalization. Sampling from a shifted, scaled integer lattice carries a shift-dependent normalization factor. This factor is a product of one-dimensional Gaussian masses, so it can be computed efficiently. Rejection sampling cancels it.
• Random auxiliary superlattices. Rejection sampling is applied to the difference of two Gaussian lattice samples. The accepted output follows the target discrete Gaussian up to a small statistical error.

Preconditions / Affected

The two results cover different parameter ranges.

• Search-LWE, prime q. This needs q in [n^2, 2n^2] and constant Gaussian error width. It uses m=4n independent samples and runs in time and space exp(O(n/ln ln n)).
• General variant. This needs q=n^(κ+o(1)), m=n+h=O(n), and R=h ln q/[m ln(2+σ)] tending to infinity, where σ is the error width. Time and space are 2^((1/2+o(1))n/ln R).
• Subexponential case. For σ=n^(o(1)) and any fixed m/n>1, the second algorithm is provably subexponential.

Caveats

The abstract states a comparison but gives no concrete-parameter analysis. It says the primal and dual baselines have exponential-time bounds. It also says earlier provable subexponential BKW analyses need Ω(n ln n) samples. The page gives no cryptographic parameter sets, concrete security estimates or implementation. It makes no claim about any deployed scheme. The paper is an unreviewed preprint.