Provable Subexponential Algorithms for Module-SIS and Module-LWE

What it is

A preprint by William Youmans (ePrint 2026/2420, received 2026-10-08, not peer-reviewed) that extends the Ducas–Engelberts–Loyer (CRYPTO 2025) Wagner-based provable Gaussian sampler from unstructured SIS to module matrices over power-of-two cyclotomic rings. It builds on recent low-sample decision-LWE preprints by Han–Gao–Hu and by Chen–Jiang–Wang–Zhang.

How it works

• The key new piece is a Chinese-remainder-support uncertainty bound. Sparse dual labels lose randomness, but an arithmetic lower bound on their length compensates for the loss. This holds for every residue degree of the prime modulus.
• Scalar row perturbations give search over the base field.
• Small integer shears remove a loss from singular blocks.
• Projection, the Han–Gao–Hu martingale analysis, and a finite enumeration sampler form a common framework for the SIS, decision and search results.

Preconditions / Affected

The results are asymptotic and need these conditions:

• Module ranks k, ℓ are fixed. Set n = kd and m = (k+ℓ)d, with ln(q/√n) = (ln n)^{b+o(1)}.
• Module-SIS: the coefficient ∞-norm bound is q/(ln n)^c. Worst-case time and space are 2^{(1/(2b)+ξ)n/ln ln n}.
• Module-LWE (decision and search): the error satisfies ‖e‖ ≤ σ√m with probability 1−o(1), and ln(2+σ) = (ln n)^{a+o(1)} with 0 ≤ a < b. Running time is 2^{(1/(2(b−a))+ξ)n/ln ln n}. Errors are matrix-independent but need not have independent coordinates. Success probability is 1−o(1) from only the k+ℓ given ring samples.
• Sample-preserving variants: scalar search-LWE and "narrow" Module-LWE, where both secret and error are restricted. For polynomial prime q = n^{κ+o(1)} with κ > 1/2, one ring sample and growing rank suffice. The sample must supply (1+o(1))n/ln ln n scalar responses. Time and space are then 2^{(1/2+ξ)n/ln ln n}.

What to do

Nothing operational. The page names no patches, parameter changes or detections. For ML-KEM and ML-DSA, the author's separate heuristic estimates in the Ducas–Engelberts–Loyer model suggest Wagner-style attacks do not reach the NIST security targets. So there is no stated reason to change parameters.

Caveats

• The result is provable and subexponential, but the exponent n/ln ln n is still far from practical at standardized parameter sizes. The NIST-target conclusion rests on heuristic estimates, not on the proofs.
• The bounds depend on the modulus and error regimes above (b, a, c, ξ). The page does not say how the standardized parameter sets map onto them.
• Only power-of-two cyclotomic rings are covered.
• The paper is a single-author preprint and has had no independent verification that the page mentions.