Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli

The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning problems widely used in cryptography, including Learning with Errors (LWE), Learning with Rounding (LWR), and Learning Parity with Noise (LPN). We present a new sample-preserving search-to-decision reduction for Noisy Linear Equations that has complexity poly(n,m, q, q/σ), where n is the dimension of the secret, m is the number of samples, q is the modulus, and σ is the magnitude of the noise (defined suitably for the kind of noise involved). In particular, this implies search-to-decision reductions for LWE and LWR that run in time poly(n) even if the modulus q is exponentially large, as long as the noise-to-modulus ratio σ/q is non-negligible. Our reduction works for prime moduli q. If q is composite, it instead produces a list that contains a small multiple of the solution. Prior to this work, known search-to-decision reductions for LWE and LWR either did not preserve the parameters of the problem (i.e., m, n, σ, and q), or had complexity that scaled polynomially with either σ or the largest prime factor of q.