Paper 2021/994

BKW Meets Fourier: New Algorithms for LPN with Sparse Parities

Dana Dachman-Soled, Huijing Gong, Hunter Kippen, and Aria Shahverdi

Abstract

We consider the Learning Parity with Noise (LPN) problem with sparse secret, where the secret vector $\mathbf{\text{s}}$ of dimension $n$ has Hamming weight at most $k$. We are interested in algorithms with asymptotic improvement in the $\mathit{\text{exponent}}$ beyond the state of the art. Prior work in this setting presented algorithms with runtime $n^{c\cdot k}$ for constant $c<1$, obtaining a constant factor improvement over brute force search, which runs in time $(\genfrac{}{}{0ex}{}{n}{k})$. We obtain the following results: - We first consider the $\mathit{\text{constant}}$ error rate setting, and in this case present a new algorithm that leverages a subroutine from the acclaimed BKW algorithm [Blum, Kalai, Wasserman, J.~ACM '03] as well as techniques from Fourier analysis for $p$-biased distributions. Our algorithm achieves asymptotic improvement in the exponent compared to prior work, when the sparsity $$, where $$ and $$. The runtime and sample complexity of this algorithm are approximately the same. - We next consider the $$ setting, where the error is subconstant. We present a new algorithm in this setting that requires only a $$ number of samples and achieves asymptotic improvement in the exponent compared to prior work, when the sparsity $$ and noise rate of $$ and $$, for $$. To obtain the improvement in sample complexity, we create subsets of samples using the $$ of Nisan and Wigderson [J.~Comput.~Syst.~Sci. '94], so that any two subsets have a small intersection, while the number of subsets is large. Each of these subsets is used to generate a single $$-biased sample for the Fourier analysis step. We then show that this allows us to bound the covariance of pairs of samples, which is sufficient for the Fourier analysis. - Finally, we show that our first algorithm extends to the setting where the noise rate is very high $$, and in this case can be used as a subroutine to obtain new algorithms for learning DNFs and Juntas. Our algorithms achieve asymptotic improvement in the exponent for certain regimes. For DNFs of size $$ with approximation factor $$ this regime is when $$, and $$, for $$. For Juntas of $$ the regime is when $$, and $$, for $$.