Paper 2026/2420

Provable Subexponential Algorithms for Module-SIS and Module-LWE

Abstract

Ducas, Engelberts and Loyer (CRYPTO 2025) turned Wagner's generalized birthday algorithm into a provable subexponential-time Gaussian sampler for unstructured short integer solutions. Recent preprints of Han, Gao and Hu, and of Chen, Jiang, Wang and Zhang, obtain low-sample decision learning-with-errors algorithms from this framework. We extend it to module matrices over power-of-two cyclotomic rings, for every residue degree of the prime modulus. For fixed module ranks $k,\ell\ge1$, let $n=kd$, $m=(k+\ell)d$, and suppose $\ln(q/\sqrt n)=(\ln n)^{b+o(1)}$. For every fixed $b,c,\xi>0$, we solve Module-SIS with coefficient infinity-norm bound $q/(\ln n)^c$ in worst-case time and space $2^{(1/(2b)+\xi)n/\ln\ln n}$. For matrix-independent errors satisfying $\|e\|\le\sigma\sqrt m$ with probability $1-o(1)$ and $\ln(2+\sigma)=(\ln n)^{a+o(1)}$, $0\le a<b$, decision and search Module-LWE take $2^{(1/(2(b-a))+\xi)n/\ln\ln n}$. Success is $1-o(1)$ using only the given $k+\ell$ ring samples; error coordinates need not be independent. The structural ingredient is a Chinese-remainder-support uncertainty bound: the loss of randomness of sparse dual labels is compensated by an arithmetic lower bound on their length. Scalar row perturbations give search over the base field, and small integer shears remove a singular-block loss. Projection, the Han--Gao--Hu martingale analysis, and a finite enumeration sampler give a common algorithmic framework. We also prove sample-preserving scalar search-LWE and narrow Module-LWE algorithms. In particular, for polynomial prime $q=n^{\kappa+o(1)}$, $\kappa>1/2$, one ring sample and growing rank suffice for decision and search in time and space $2^{(1/2+\xi)n/\ln\ln n}$ when the sample supplies $(1+o(1))n/\ln\ln n$ scalar responses. Here ``narrow'' restricts both secret and error. Separate heuristic estimates in the model of Ducas, Engelberts and Loyer suggest that Wagner-style attacks do not reach the NIST security targets of ML-KEM and ML-DSA.