Wagner’s algorithm provably runs in subexponential time for SIS∞

At CRYPTO 2015, Kirchner and Fouque claimed that a carefully tuned variant of the Blum-Kalai-Wasserman (BKW) algorithm (JACM 2003) should solve the Learning with Errors problem (LWE) in slightly subexponential time for modulus q = poly(n) and narrow er- ror distribution, when given enough LWE samples. Taking a modular view, one may 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 be undocumented so far. We re-interpret this Wagner step as walking backward through a chain of projected lattices, zigzagging through some auxiliary superlattices. We further randomize the bucketing step using Gaussian randomized round- ing to exploit the powerful discrete Gaussian machinery. This approach avoids sample amplification and turns Wagner’s algorithm into an ap- proximate discrete Gaussian sampler for q-ary lattices. For an SIS lattice with n equations modulo q, this algorithm runs in subexponential time exp(O(n/ log log n)) to reach a Gaussian width pa- rameter s = q/polylog(n) only requiring m = n + ω(n/ log log n) many SIS variables. This directly provides a provable algorithm for solving the Short Integer Solution problem in the infinity norm (SIS∞) for norm bounds β = q/polylog(n). This variant of SIS underlies the security of the NIST post-quantum cryptography standard Dilithium. Despite its subexponential complexity, Wagner’s algorithm does not appear to threaten Dilithium’s concrete security.