Paper 2026/614

Spectral Method attacks Sparse LWE, Sparse LPN and Beyond

Amitabha Bagchi, Indian Institute of Technology Delhi

Rajendra Kumar, Indian Institute of Technology Delhi

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\leq l\leq n$, we give a spectral method to solve this problem in $\widetilde{O}\left(\binom{n}{l}\lvert{R}\rvert^l\right)$ time except with probability at most $n^{-\Omega(l)}$, provided the number of samples is roughly at least $\left(\frac{\lvert{R}\rvert 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 $\lvert{R}\rvert =\omega(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.

@misc{cryptoeprint:2026/614,
      author = {Shashwat Agrawal and Amitabha Bagchi and Rajendra Kumar},
      title = {Spectral Method attacks Sparse {LWE}, Sparse {LPN} and Beyond},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/614},
      year = {2026},
      url = {https://eprint.iacr.org/2026/614}
}