Spectral Method attacks Sparse LWE, Sparse LPN and Beyond

Abstract

Given a set of $k$-sparse linear equations over a ring $R$, we give algorithms to determine whether the right-hand sides are random or have a secret assignment planted with noise. For a parameter $k/2\le l\le n$, we give a spectral method to solve this problem in $\tilde{O}\left(\left(\genfrac{}{}{0ex}{}{n}{l}\right)|R{|}^l\right)$ time except with probability at most $n^{-\hat{I}\text{c◯}(l)}$, provided the number of samples is roughly at least ${\left(\frac{|R|n}{l}\right)}^{k/2}$. This attack generalizes the Kikuchi method described by Wein et. al. (Journal of the ACM 2019) for ${\mathbb{Z}}_2$ to (commutative) rings of any finite size. We also give a simpler algorithm with better runtime than the spectral method and better sample complexity when $|R|=\ddot{I}‰(n/l)$. As a consequence, we obtain new sample-time tradeoffs for the decision problem of sparse LWE, sparse LPN over higher modulus $q$, and in general the distinguishing random vs planted ${\mathbb{Z}}_q$-linear equations for a large class of noise distributions. Our results imply a tightness of the hardness claims of Jain, Lin, Saha (Annual International Cryptology Conference, 2024) for sparse LWE.