{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreif7ae3eyryjzqexwfroffwprixzivvgm53f5f6hppqgiwkge5xgoq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mnpqj72etm22"
  },
  "path": "/report/2026/095",
  "publishedAt": "2026-06-07T12:13:43.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "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^{-\\alpha}$ for any constant $\\alpha < 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 $\\alpha = 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.",
  "title": "TR26-095 |  Towards Worst-case Hardness for Low-Noise LPN | \n\n\tDivesh Aggarwal, \n\n\tRishav Gupta, \n\n\tHai Hoang Nguyen, \n\n\tKel Zin Tan, \n\n\tPrashant Nalini Vasudevan"
}