Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.19215 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908388277878784 |
|---|---|
| author | Chen, Xue Shu, Wenxuan Zhou, Zhaienhe |
| author_facet | Chen, Xue Shu, Wenxuan Zhou, Zhaienhe |
| contents | 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(η\cdot n/k)^k$ for any noise rate $η$, which improves the state-of-the-art of LSPN whenever $η\in ( k/n,\sqrt{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}<n^k$, sparse LPN has learning algorithms in polynomial time when $m>n^{k/2}$. However, much less is known about learning algorithms for constant $k$ like 3 and $m<n^{k/2}$ samples, except the Gaussian elimination algorithm of time $e^{ηn}$. Our framework provides a learning algorithm in $e^{O(η\cdot n^{\frac{δ+1}{2}})}$ time given $δ\in (0,1)$ and $m \approx n^{1+(1-δ)\cdot \frac{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 than previous approaches for any $η<n^{-0.7}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_19215 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Algorithms for Sparse LPN and LSPN Against Low-noise Chen, Xue Shu, Wenxuan Zhou, Zhaienhe Cryptography and Security 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(η\cdot n/k)^k$ for any noise rate $η$, which improves the state-of-the-art of LSPN whenever $η\in ( k/n,\sqrt{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}<n^k$, sparse LPN has learning algorithms in polynomial time when $m>n^{k/2}$. However, much less is known about learning algorithms for constant $k$ like 3 and $m<n^{k/2}$ samples, except the Gaussian elimination algorithm of time $e^{ηn}$. Our framework provides a learning algorithm in $e^{O(η\cdot n^{\frac{δ+1}{2}})}$ time given $δ\in (0,1)$ and $m \approx n^{1+(1-δ)\cdot \frac{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 than previous approaches for any $η<n^{-0.7}$. |
| title | Algorithms for Sparse LPN and LSPN Against Low-noise |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2407.19215 |