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

CREATORDivesh Aggarwal, Rishav Gupta, Li Zeyong
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.10056

Browse the full library · About the Tower of Babel