Hardness Amplification for (Sparse) LPN
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914556618473472 |
|---|---|
| author | Aggarwal, Divesh Gupta, Rishav Zeyong, Li |
| author_facet | Aggarwal, Divesh Gupta, Rishav Zeyong, Li |
| contents | We prove new hardness amplification results for Learning Parity with Noise ($\mathsf{LPN}$) and its sparse variants. In $\mathsf{LPN}_{η,n,m}$, the goal is to recover a secret $\vec s\in\mathbb{F}_2^n$ from $m$ noisy linear samples $(\vec a,b)$, where $\vec a\leftarrow \mathbb{F}_2^n$ is uniform and $b=\langle \vec a,\vec s\rangle + e$ with $e\leftarrow \mathrm{Ber}(η)$.
Building on the direct-product framework introduced by Hirahara and Shimizu [HS23], we show an 'instance-fraction amplification' theorem: for any $\varepsilon,δ>0$, any algorithm that solves $\mathsf{LPN}_{η,n,m}$ with success probability $\varepsilon$ can be transformed into an algorithm that succeeds with probability $1-δ$ on a related $\mathsf{LPN}$ distribution with scaled parameters $\mathsf{LPN}_{η/k,\;n/k,\;m}$, where $ k=Θ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right). $ Equivalently, an algorithm that solves $\mathsf{LPN}$ on a 'small fraction of instances' can be converted into an algorithm that solves $\mathsf{LPN}$ on 'almost all instances', yielding a self-amplification for a wide range of parameters.
We extend the same amplification approach to $\mathsf{LPN}$ over $\mathbb{F}_q$ and to Sparse-$\mathsf{LPN}$, where each query vector $\vec a$ has exactly $σ$ nonzero entries. Together, these results establish hardness self-amplification for a broad family of $\mathsf{LPN}$-type problems, strengthening the foundations for assuming the average-case hardness of $\mathsf{LPN}$ and its sparse variants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10056 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hardness Amplification for (Sparse) LPN Aggarwal, Divesh Gupta, Rishav Zeyong, Li Cryptography and Security Computational Complexity We prove new hardness amplification results for Learning Parity with Noise ($\mathsf{LPN}$) and its sparse variants. In $\mathsf{LPN}_{η,n,m}$, the goal is to recover a secret $\vec s\in\mathbb{F}_2^n$ from $m$ noisy linear samples $(\vec a,b)$, where $\vec a\leftarrow \mathbb{F}_2^n$ is uniform and $b=\langle \vec a,\vec s\rangle + e$ with $e\leftarrow \mathrm{Ber}(η)$. Building on the direct-product framework introduced by Hirahara and Shimizu [HS23], we show an 'instance-fraction amplification' theorem: for any $\varepsilon,δ>0$, any algorithm that solves $\mathsf{LPN}_{η,n,m}$ with success probability $\varepsilon$ can be transformed into an algorithm that succeeds with probability $1-δ$ on a related $\mathsf{LPN}$ distribution with scaled parameters $\mathsf{LPN}_{η/k,\;n/k,\;m}$, where $ k=Θ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right). $ Equivalently, an algorithm that solves $\mathsf{LPN}$ on a 'small fraction of instances' can be converted into an algorithm that solves $\mathsf{LPN}$ on 'almost all instances', yielding a self-amplification for a wide range of parameters. We extend the same amplification approach to $\mathsf{LPN}$ over $\mathbb{F}_q$ and to Sparse-$\mathsf{LPN}$, where each query vector $\vec a$ has exactly $σ$ nonzero entries. Together, these results establish hardness self-amplification for a broad family of $\mathsf{LPN}$-type problems, strengthening the foundations for assuming the average-case hardness of $\mathsf{LPN}$ and its sparse variants. |
| title | Hardness Amplification for (Sparse) LPN |
| topic | Cryptography and Security Computational Complexity |
| url | https://arxiv.org/abs/2605.10056 |