Algorithms for Sparse LPN and LSPN Against Low-noise (extended abstract)

摘要

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 without fast matrix multiplication or tensor methods such that its algorithms are easy to implement and run in polynomial space. Let n be the dimension, k denote the sparsity, and η be the noise rate such that each label gets flipped with probability η. As a fundamental problem in computational learning theory, Learning Sparse Parities with Noise (LSPN) assumes the hidden parity is k-sparse instead of a potentially dense vector. While the simple enumeration algorithm takes n k=O(n/k)^k time, previously known results stills need at least n k/2 = Ω(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 that samples random vectors in 𝐅_2^n, it samples random k-sparse vectors. Because the number of k-sparse vectors is n k<n^k, sparse LPN has learning algorithms in polynomial time when m>n^k/2. However, much less is known about learning algorithms for a constant k like 3 and m<n^k/2 samples, except the Gaussian elimination algorithm and sum-of-squares algorithms. Our framework provides a learning algorithm in e^Õ(η· n^δ+1/2) time given δ∈ (0,1) and m=max{1,η· n^δ+1/2/k^2}· n^1+(1-δ)·k-1/2 samples. This improves previous learning algorithms. For example, in the classical setting of k=3 and m=n^1.4, our algorithm would be faster than previous approaches for any η<n^-0.7.