FlagThis

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 ≤ l ≤ n, we give a spectral method to solve this problem in O(n^l |R|^l) time except with probability at most n^-[(l)] , provided the number of samples is roughly at least |R|n k/2 l . This attack generalizes the Kikuchi method described by Wein et. al. (Journal of the ACM 2019) for Z2 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| = Ω(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 Zq-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.