2024/07/27 by Chen, Xue, Shu, Wenxuan, Zhou, Zhaienhe · 2 citations
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2407.19215
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 = Ω(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 knk/2. However, much less is known about learning algorithms for constant k like 3 and m