Hardness Amplification for (Sparse) LPN
Divesh Aggarwal, Rishav Gupta, Li Zeyong · 2026
Read Hardness Amplification for (Sparse) LPN by Divesh Aggarwal, Rishav Gupta, Li Zeyong (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-10056.txt.
Description
Aggarwal, Gupta and Zeyong prove new hardness-amplification results for LPN (Learning Parity with Noise), a problem at the heart of code-based cryptography. In LPN, the goal is to recover a secret vector from noisy linear samples. Each sample pairing a random vector with a bit equal to its inner product with the secret plus a random error. Building on Hirahara and Shimizu's direct-product framework, they show an instance-fraction amplification theorem.
Any algorithm solving LPN with small success probability can be converted into one succeeding almost always on a related LPN distribution with rescaled parameters. There, noise and dimension shrink by a factor tied to the target probabilities. In plain terms, solving a few instances implies solving almost all of them, a self-amplification result. The same approach extends to LPN over larger finite fields and to sparse LPN, where each query vector has few nonzero entries.
Catalog record
| CREATOR | Divesh Aggarwal, Rishav Gupta, Li Zeyong |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.10056