Spectral Method attacks Sparse LWE, Sparse LPN and Beyond

Shashwat Agrawal, Amitabha Bagchi, Rajendra Kumar

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.…