Algorithms for Sparse LPN and LSPN Against Low-noise

We consider sparse variants of the classical Learning Parities with random Noise (LPN) problem. Our main contribution is a new algorithmic framework that provides learning algorithms against low-noise for both Learning Sparse Parities (LSPN) problem and sparse LPN problem. Different from previous approaches for LSPN and sparse LPN, this framework has a simple structure and runs in polynomial space. Let n be the dimension, k denote the sparsity, and η be the noise rate. As a fundamental problem in computational learning theory, Learning Sparse Parities with Noise (LSPN) assumes the hidden parity is k-sparse. While a simple enumeration algorithm takes n choose k=O(n/k)k time, previously known results stills need n choose k/2 = Omega(n/k)k/2 time for any noise rate η. Our framework provides a LSPN algorithm runs in time O(η · n/k)k for any noise rate η, which improves the state-of-the-art of LSPN whenever η ∈ ( k/n,√k/n). The sparse LPN problem is closely related to the classical problem of refuting random k-CSP and has been widely used in cryptography as the hardness assumption. Different from the standard LPN, it samples random k-sparse vectors. Because the number of k-sparse vectors is n choose k<nk, sparse LPN has learning algorithms in polynomial time when m>nk/2. However, much less is known about learning algorithms for constant k like 3 and m<nk/2 samples, except the Gaussian elimination algorithm of time eη n. Our framework provides a learning algorithm in e^O(η · n^fracδ+12) time given δ ∈ (0,1) and m ≈ n^1+(1-δ)· frack-12 samples. This improves previous learning algorithms. For example, in the classical setting of k=3 and m=n1.4, our algorithm would be faster than than previous approaches for any η<n-0.7.