The kLIN problem concerns solving noisy systems of random sparse linear equations mod 2. It gives rise to natural candidate hard CSP distributions and is a cornerstone of local cryptography. Recently, it was used in cryptographic constructions, under the name “sparse LPN”. For constant sparsity k and inverse polynomial noise rate, both search and decision versions of kLIN are statistically possible and conjectured to be computationally hard for \(n\ll m\ll n^{k/2}\) , where m is the number of k-sparse linear equations, and n is the number of variables. We show an algorithm that given access to a distinguisher for \((k-1)\) LIN with m samples, solves search kLIN with roughly O(nm) samples. Previously, it was only known how to reduce from search kLIN with \(O(m^3)\) samples, yielding guarantees for decision kLIN only when \(m \ll n^{k/6}\) . The reduction succeeds even if the distinguisher has sub-constant advantage at a small additive cost in sample complexity. Our technique applies with some restrictions to Goldreich’s function and kLIN with random coefficients over other finite fields.