Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs
For cryptographers analyzing sparse LWE/LPN-based schemes, this work provides improved attacks with better sample-time tradeoffs, though it is an incremental extension of prior work for q=2.
This paper extends the Kikuchi method to attack decisional k-sparse LWE and LPN problems for higher moduli q, achieving new tradeoffs between sample complexity and time complexity.
This paper extends the Kikuchi method to give algorithms for decisional $k$-sparse Learning With Errors (LWE) and $k$-sparse Learning Parity with Noise (LPN) problems for higher moduli $q$. We create a Kikuchi graph for a sparse LWE/LPN instance and use it to give two attacks for these problems. The first attack decides by computing the spectral norm of the adjacency matrix of the Kikuchi graph, which is a generalization of the attack for $q=2$ given by Wein et. al. (Journal of the ACM 2019). The second approach computes non-trivial closed walks of the graph, and then decides by computing a certain polynomial of edge labels in the walks. This is a generalization of the attack for $q=2$ given by Gupta et. al. (SODA 2026). Both the attacks yield new tradeoffs between sample complexity and time complexity of sparse LWE/LPN.