We revisit the Blum-Kalai-Wasserman (BKW) algorithm and its subexponential variant proposed by Kirchner and Fouque (CRYPTO 2015) for solving Learning with Errors (LWE). Taking a modular view, we regard BKW as a combination of Wagner's algorithm (CRYPTO 2002), run over the corresponding dual problem, and the Aharonov-Regev distinguisher (JACM 2005). Hence, the subexponential Wagner step alone should be of interest for solving this dual problem -- namely, the Short Integer Solution problem (SIS) -- but this appears to have been undocumented so far. We reinterpret this Wagner step as walking backward through a chain of projected lattices, zigzagging through some auxiliary superlattices. This approach yields an approximate discrete Gaussian sampler for $q$-ary lattices, running in time $\exp(O(n / \log \log n))$. Applied to $\mathrm{SIS}^\infty$ with norm bound $\beta = q / \mathrm{polylog}(n)$, the method provides the first provable subexponential-time algorithm for this setting. We discuss its implications for lattice-based cryptography, including the NIST standard ML-DSA (Dilithium), whose security remains unaffected in practice.
This is a joint work with Léo Ducas and Lynn Engelberts.
Johanna Loyer is a postdoctoral researcher at Inria Saclay in the GRACE team, working on the classical and quantum cryptanalysis of post-quantum schemes, with a particular focus on lattice- and code-based cryptography. Before joining Inria Saclay, she completed her PhD at Inria Paris in 2023 and held a postdoctoral position at CWI in Amsterdam.