THE QUANTUM INTELLIGENCER

Wagner’s Algorithm Achieves Subexponential Runtime for SIS∞: Implications for Post-Quantum Cryptography In Plain English: This research tackles a math problem that’s used to protect digital information in a future where quantum computers could break today’s security systems. The problem involves finding a short solution to a large set of number equations, which is hard to do quickly. The researchers studied an existing method called Wagner’s algorithm and showed it can solve this problem faster than previously thought—though still not fast enough to break real-world systems like the one used in the U.S. government’s new quantum-safe security standard. Their improved understanding helps ensure that the security methods we rely on are truly safe, by testing how strong they really are against clever mathematical attacks. Summary: This paper analyzes a variant of Wagner’s algorithm—originally designed for generalized birthday problems—and demonstrates that it can solve the Short Integer Solution problem in the infinity norm (SIS∞) in provably subexponential time, specifically exp(O(n / log log n)), under certain conditions. The authors reinterpret Wagner’s method as a backward walk through a chain of projected lattices, incorporating auxiliary superlattices and introducing Gaussian randomized rounding during the bucketing phase. This innovation eliminates the need for sample amplification and transforms the algorithm into an approximate discrete Gaussian sampler over q-ary lattices. For an SIS instance with n equations modulo q, the algorithm achieves a Gaussian width parameter s = q / polylog(n) using only m = n + ω(n / log log n) samples. This result provides the first provable subexponential algorithm for SIS∞ with β = q / polylog(n), a problem central to the security of lattice-based cryptographic schemes such as Dilithium, a NIST post-quantum cryptography standard. However, the authors emphasize that while the theoretical complexity is improved, the algorithm does not pose a practical threat to Dilithium’s concrete security parameters. Key Points: - Wagner’s algorithm, when enhanced with Gaussian randomized rounding, can solve SIS∞ in subexponential time exp(O(n / log log n)). - The method avoids sample amplification by using randomized rounding to produce discrete Gaussian-like samples. - The algorithm operates by walking backward through a sequence of projected lattices and auxiliary superlattices. - It requires only m = n + ω(n / log log n) samples, slightly more than the number of equations. - The solution achieves a Gaussian width s = q / polylog(n), enabling attacks on SIS∞ with β = q / polylog(n). - SIS∞ is the hardness assumption underlying the security of Dilithium, a NIST-standardized post-quantum signature scheme. - Despite theoretical improvements, the algorithm does not compromise the practical security of Dilithium. Notable Quotes: - “Wagner's algorithm provably runs in subexponential time for SIS$^\infty$.” - “This directly provides a provable algorithm for solving the Short Integer Solution problem in the infinity norm (SIS$^\infty$).” - “Despite its subexponential complexity, Wagner's algorithm does not appear to threaten Dilithium's concrete security.” Data Points: - Runtime complexity: exp(O(n / log log n)) - Number of SIS variables required: m = n + ω(n / log log n) - Achievable Gaussian width parameter: s = q / polylog(n) - Applicable to SIS∞ with norm bound β = q / polylog(n) - Modulus q: polynomial in n (q = poly(n)) - Error distribution: narrow (implied by context) - Year of reference work (BKW): 2003 - Conference where Kirchner and Fouque presented related claim: CRYPTO 2015 Controversial Claims: - The claim that Wagner’s algorithm—originally a heuristic method for collision search—can be rigorously adapted to solve a central lattice problem (SIS∞) in provable subexponential time may challenge conventional wisdom about the hardness of SIS. - The assertion that only slightly more than n samples (m = n + ω(n / log log n)) are sufficient to solve SIS∞ could be seen as surprising, given typical requirements for lattice reduction techniques. - The re-interpretation of Wagner’s algorithm as a backward walk through projected lattices with Gaussian rounding introduces a novel geometric perspective that may invite scrutiny regarding its practical implementability or optimality. Technical Terms: - Wagner’s algorithm - Short Integer Solution problem (SIS) - SIS in the infinity norm (SIS∞) - Learning with Errors (LWE) - Blum-Kalai-Wasserman (BKW) algorithm - Discrete Gaussian sampling - q-ary lattices - Gaussian randomized rounding - Sample amplification - Dual problem (in lattice cryptography) - Subexponential time - Norm bound (β) - Modulus (q) - Projected lattices - Superlattices - Bucketing step - Gaussian width parameter (s) - Post-quantum cryptography - Dilithium (cryptographic algorithm) —Ada H. Pemberley Dispatch from The Prepared E0