{"ID":3083868,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T05:49:02.101151534Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.05834","arxiv_id":"2606.05834","title":"Towards Worst-case Hardness for Low-Noise LPN","abstract":"The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives to public-key encryption and beyond. A central open question is whether the average-case hardness of LPN can be based on worst-case complexity assumptions, as has been achieved for the analogous Learning With Errors (LWE) problem. Existing worst-case-to-average-case reductions for LPN [BLVW19, YZ21] rely on statistical smoothing of linear codes, which inherently limits the resulting average-case hardness to noise rates as large as $1/2 - 1/\\mathrm{poly}(n)$, which is insufficient for public-key applications. We explore a new approach towards obtaining such reductions: rather than requiring that random sparse combinations of the rows of the generator matrix of a code be statistically close to uniform, we only require that they be computationally indistinguishable from uniform. This leads to a clean win-win structure: we show that any efficient LPN solver can be transformed into a pair of efficient algorithms $(S, D)$ such that for every matrix $A$ of appropriate dimensions over $\\mathbb{F}_2$, either $S$ decodes the code generated by $A$ from random noise, or $D$ distinguishes random noisy codewords of the dual of this code from uniform. By instantiating this reduction with appropriate parameters, we obtain the average-case hardness of LPN with inverse-polynomial noise rate $n^{-α}$ for any constant $α\u003c 1$, assuming the worst-case simultaneous hardness of decoding a code from random noise and distinguishing random noisy codewords of its dual from uniform. In particular, setting $α= 1/2$, our reduction yields LPN hardness in the parameter regime required for Alekhnovich's construction of public-key encryption [Ale03], a regime that was previously inaccessible via worst-case reductions.","short_abstract":"The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives to public-key encryption and beyond. A central open question is whether the average-case hardness of LPN can be based on worst-case complexi...","url_abs":"https://arxiv.org/abs/2606.05834","url_pdf":"https://arxiv.org/pdf/2606.05834v1","authors":"[\"Divesh Aggarwal\",\"Rishav Gupta\",\"Hai Hoang Nguyen\",\"Kel Zin Tan\",\"Prashant Nalini Vasudevan\"]","published":"2026-06-04T08:11:23Z","proceeding":"cs.CR","tasks":"[\"cs.CR\"]","methods":"[]","has_code":false}