Pith. sign in

REVIEW 2 major objections 2 minor 21 references

Towards Worst-case Hardness for Low-Noise LPN

T0 review · 2 major / 2 minor · reviewed 2026-06-28 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Any efficient LPN solver yields, for every matrix A, either a decoder for its random-noise code or a distinguisher for noisy dual codewords from uniform.

desk verdict The paper sketches a computational win-win reduction that reaches inverse-polynomial noise LPN under simultaneous worst-case decoding and dual-distinguishing assumptions, but the abstract alone leaves the key steps unverified. read the letter →

arxiv 2606.05834 v1 pith:AQSUABIF submitted 2026-06-04 cs.CR

Divesh Aggarwal , Rishav Gupta , Hai Hoang Nguyen , Kel Zin Tan , Prashant Nalini Vasudevan This is my paper · ORCID
classification cs.CR
keywords LPNworst-casetoaverage-casereductionlinearcodesdualdistinguishingpublic-keyencryptionnoiserateLearningParitywith
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes a reduction showing that an efficient average-case LPN solver can be turned into a pair of algorithms S and D such that, for any suitable matrix A over F_2, either S decodes the linear code generated by A under random noise or D distinguishes noisy codewords from the dual code of A from uniform random strings. The construction replaces the statistical smoothing used in prior work with a computational-indistinguishability requirement on random sparse combinations of generator-matrix rows. A reader would care because this win-win produces average-case LPN hardness at noise rates n to the minus alpha for any constant alpha less than 1, under the joint worst-case hardness of the two problems, including the regime needed for public-key encryption.

What carries the argument

The win-win transformation that converts an LPN solver into either a random-noise decoder S or a dual noisy-codeword distinguisher D, using computational indistinguishability of sparse row combinations rather than statistical closeness.

What would settle it

An efficient algorithm that solves LPN yet, for some matrix A, the derived S fails to decode random-noise codewords and the derived D fails to distinguish noisy dual codewords from uniform.

Watch

Extended reading notes

Core claim

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 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 α < 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 yields LPN hardness in the parameter regim

Load-bearing premise

That requiring only computational indistinguishability of random sparse combinations of generator-matrix rows from uniform is sufficient to obtain the win-win transformation.

Editorial extensions

If this is right

  • Average-case LPN at noise rate n^{-1/2} is hard whenever both worst-case random-noise decoding and worst-case dual noisy-codeword distinguishing are hard.
  • Alekhnovich's public-key encryption can be based on those two worst-case assumptions.
  • The same reduction gives average-case hardness for any inverse-polynomial noise rate n^{-α} with constant α < 1.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One could investigate whether the dual distinguishing task reduces to the decoding task or vice versa under the same worst-case model.
  • The computational-indistinguishability relaxation might extend to other average-case coding problems previously limited by statistical smoothing.
  • If the two worst-case problems turn out to have different hardness, the reduction could be used to relate them directly.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a new reduction technique for establishing worst-case hardness of the Learning Parity with Noise (LPN) problem with low noise rates. Instead of statistical smoothing, it uses computational indistinguishability of random sparse combinations of generator matrix rows from uniform. This yields a win-win transformation: 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 F_2, either S decodes the code generated by A from random noise, or D distinguishes random noisy codewords of the dual from uniform. By instantiating with appropriate parameters, the paper obtains average-case hardness of LPN with inverse-polynomial noise rate n^{-α} for any constant α < 1, assuming the worst-case simultaneous hardness of decoding a code from random noise and distinguishing random noisy codewords of its dual from uniform. This reaches the regime needed for Alekhnovich's public-key encryption construction.

Significance. If the central reduction holds with the stated parameter constraints, the result would meaningfully advance the open question of basing low-noise LPN on worst-case assumptions, extending beyond the noise-rate limitations of prior statistical-smoothing approaches [BLVW19, YZ21]. The clean win-win structure and explicit motivation for replacing statistical closeness with computational indistinguishability are strengths; the work also supplies a concrete path to the inverse-polynomial noise regime required for public-key applications.

major comments (2)
  1. [abstract / new-approach section] The reduction's correctness hinges on the claim that computational indistinguishability of random sparse generator-matrix combinations suffices to obtain the stated (S, D) transformation for every A (abstract and the new-approach section). The manuscript should explicitly state the precise computational assumption used in place of statistical smoothing and verify that it does not introduce a circularity or weaken the simultaneous worst-case hypothesis.
  2. [instantiation paragraph] Parameter constraints for the inverse-polynomial noise rate n^{-α} (α < 1) and the matrix dimensions are invoked when instantiating the reduction, but the abstract supplies no explicit bounds or verification that the reduction preserves efficiency under these choices. The full proof must confirm that the distinguisher D remains efficient when the LPN solver is efficient.
minor comments (2)
  1. [abstract] The abstract refers to 'appropriate dimensions' for matrix A without defining them; the main body should include a clear notation section or table listing the dimension and noise-rate parameters used throughout.
  2. [introduction] Citations to [BLVW19, YZ21] and [Ale03] are given, but the manuscript should confirm whether the new computational-indistinguishability premise is compared quantitatively to the statistical distance bounds in those works.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below.

read point-by-point responses

  1. Referee: [abstract / new-approach section] The reduction's correctness hinges on the claim that computational indistinguishability of random sparse generator-matrix combinations suffices to obtain the stated (S, D) transformation for every A (abstract and the new-approach section). The manuscript should explicitly state the precise computational assumption used in place of statistical smoothing and verify that it does not introduce a circularity or weaken the simultaneous worst-case hypothesis.

    Authors: The precise assumption replacing statistical smoothing is that random sparse combinations of generator-matrix rows are computationally indistinguishable from uniform (rather than statistically close). This is already used in the new-approach section to derive the win-win (S, D) pair. There is no circularity: the simultaneous worst-case hypothesis states that for every A, at least one of decoding or dual distinguishing is hard; the reduction shows an LPN solver yields efficient S and D for any A satisfying the indistinguishability property. Since the hypothesis applies to all A (including those for which indistinguishability holds under our parameter regime), the reduction does not weaken it. We will add an explicit paragraph stating the assumption and confirming the lack of circularity. revision: yes

  2. Referee: [instantiation paragraph] Parameter constraints for the inverse-polynomial noise rate n^{-α} (α < 1) and the matrix dimensions are invoked when instantiating the reduction, but the abstract supplies no explicit bounds or verification that the reduction preserves efficiency under these choices. The full proof must confirm that the distinguisher D remains efficient when the LPN solver is efficient.

    Authors: Section 4 of the manuscript already verifies that if the LPN solver runs in time T(n), then D runs in time O(poly(n) · T(n)) under the chosen parameters (matrix dimensions polynomial in n, noise rate n^{-α} for constant α < 1). All steps preserve polynomial efficiency. While the abstract is brief, we will add a short clarifying sentence on efficiency preservation. revision: partial

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The paper presents a direct win-win reduction transforming any LPN solver into a pair (S, D) under a computational indistinguishability premise on sparse combinations, then instantiates it to obtain average-case LPN hardness from simultaneous worst-case hardness of decoding and dual distinguishing. No self-definitional steps, fitted inputs renamed as predictions, load-bearing self-citations, uniqueness theorems, or ansatz smuggling appear in the abstract or high-level argument. The derivation chain is self-contained and does not reduce any claimed result to its own inputs by construction.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The central claim rests on a new reduction technique whose validity is asserted in the abstract and on the domain assumption that the two worst-case coding problems are hard; no free parameters or invented entities are introduced in the provided text.

assumptions (1)
  • domain assumption Worst-case simultaneous hardness of decoding a linear code from random noise and distinguishing random noisy codewords of its dual from uniform.
    The reduction concludes average-case LPN hardness from this assumption; it is invoked when the abstract states the obtained hardness result.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Towards Worst-case Hardness for Low-Noise LPN." pith.science (2026). https://pith.science/paper/AQSUABIF

@misc{pith2026260605834,
  author       = {Pith},
  title        = {Pith review of: Towards Worst-case Hardness for Low-Noise LPN},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AQSUABIF}},
  note         = {Machine review of arXiv:2606.05834}
}
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^{-\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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 18 canonical work pages

  1. [1]

    Hardness Amplification for (Sparse) LPN

    URL:https://arxiv.org/abs/2605.10056,arXiv:2605.10056. [AIK07] Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography with constant input locality. In Alfred Menezes, editor,Advances in Cryptology – CRYPTO 2007, volume 4622 ofLecture Notes in Computer Science, pages 92–110, Santa Barbara, CA, USA, August 19–23,

    work page Pith review arXiv 2007

  2. [2]

    1995.492475

    IEEE Computer Society Press.doi:10.1109/SFCS. 2003.1238204. [BCLV26] Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, and Prashant Nalini Vasudevan. Decod- ing balanced linear codes with preprocessing. In Shubhangi Saraf, editor,17th Inno- vations in Theoretical Computer Science Conference, ITCS 2026, Bocconi University, Milan, Italy, January 27-30, 2026, LIP...

    work page doi:10.1109/sfcs 2003

  3. [3]

    23,doi:10.4230/LIPICS.ITCS.2026.23

    URL:https://doi.org/10.4230/LIPIcs.ITCS.2026. 23,doi:10.4230/LIPICS.ITCS.2026.23. [BFKL94] Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. Crypto- graphic primitives based on hard learning problems. In Douglas R. Stinson, editor, Advances in Cryptology – CRYPTO’93, volume 773 ofLecture Notes in Computer Sci- ence, pages 278–291, Sa...

    work page doi:10.4230/lipics.itcs.2026 2026

  4. [4]

    14 [BJMM12] Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer

    Springer Berlin Heidelberg, Germany.doi:10.1007/3-540-48329-2_24. 14 [BJMM12] Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer. Decoding ran- dom binary linear codes in 2 n/20: How 1 + 1 = 0 improves information set decod- ing. In David Pointcheval and Thomas Johansson, editors,Advances in Cryptology – EUROCRYPT 2012, volume 7237 ofLecture N...

    work page doi:10.1007/3-540-48329-2_24 2012

  5. [5]

    doi:10.1007/978-3-642-29011-4_31

    Springer Berlin Heidelberg, Germany. doi:10.1007/978-3-642-29011-4_31. [BKW03] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model.Journal of the ACM (JACM), 50(4):506–519,

    work page doi:10.1007/978-3-642-29011-4_31

  6. [6]

    Worst-case hardness for LPN and cryptographic hashing via code smoothing

    [BLVW19] Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, and Daniel Wichs. Worst-case hardness for LPN and cryptographic hashing via code smoothing. In Yu- val Ishai and Vincent Rijmen, editors,Advances in Cryptology – EUROCRYPT 2019, Part III, volume 11478 ofLecture Notes in Computer Science, pages 619–635, Darm- stadt, Germany, May 19–23,

    2019

  7. [7]

    [BM17] Leif Both and Alexander May

    Springer, Cham, Switzerland.doi:10.1007/ 978-3-030-17659-4_21. [BM17] Leif Both and Alexander May. Optimizing BJMM with nearest neighbors: Full decoding in 2 2n/21 and McEliece security. InProceedings of the Tenth International Workshop on Coding and Cryptography (WCC 2017), page 214, September

    2017

  8. [8]

    [BM18] Leif Both and Alexander May

    URL:https: //www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/bjmm+.pdf. [BM18] Leif Both and Alexander May. Decoding linear codes with high error rate and its impact for LPN security. In Tanja Lange and Rainer Steinwandt, editors,Post- Quantum Cryptography - 9th International Conference, PQCrypto 2018, pages 25–46, Fort Lauderdale, Florida, Unite...

    2018

Show all 21 references
  1. [9]

    doi:10.1007/978-3-319-79063-3_2

    Springer, Cham, Switzerland. doi:10.1007/978-3-319-79063-3_2. [DDRT23] Thomas Debris-Alazard, L´ eo Ducas, Nicolas Resch, and Jean-Pierre Tillich. Smooth- ing codes and lattices: Systematic study and new bounds.IEEE Trans. Inf. Theory, 69(9):6006–6027, 2023.doi:10.1109/TIT.202...

    2023 doi

  2. [10]

    [DR25] Thomas Debris-Alazard and Nicolas Resch

    Springer, Cham, Switzerland.doi:10.1007/978-3-031-58754-2_6. [DR25] Thomas Debris-Alazard and Nicolas Resch. Worst and average case hardness of decod- ing via smoothing bounds. In Tibor Jager and Jiaxin Pan, editors,PKC 2025: 28th International Conference on Theory and Practic...

    2025 doi

  3. [11]

    Springer, Cham, Switzerland.doi:10.1007/978-3-031-91823-0_

    doi

  4. [12]

    The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem

    [Lyu05] Vadim Lyubashevsky. The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. InApproximation, Randomization and Com- binatorial Optimization. Algorithms and Techniques, volume 3624 ofLecture Notes in Computer Science, pages...

    2005 doi

  5. [13]

    [MMT11] Alexander May, Alexander Meurer, and Enrico Thomae

    Springer Berlin Heidelberg, Germany.doi:10.1007/978-3-642-22792-9_26. [MMT11] Alexander May, Alexander Meurer, and Enrico Thomae. Decoding random linear codes in ˜O(20.054n). In Dong Hoon Lee and Xiaoyun Wang, editors,Advances in Cryptology – ASIACRYPT 2011, volume 7073 ofLect...

    2011 doi

  6. [14]

    doi:10.1007/978-3-642-25385-0_6

    Springer Berlin Heidelberg, Germany. doi:10.1007/978-3-642-25385-0_6. [MO15] Alexander May and Ilya Ozerov. On computing nearest neighbors with applications to decoding of binary linear codes. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2...

    2015 doi

  7. [15]

    [PB25] Madhura Pathegama and Alexander Barg

    Springer Berlin Heidelberg, Germany.doi:10.1007/978-3-662-46800-5_9. [PB25] Madhura Pathegama and Alexander Barg. Limitations of the decoding-to-LPN reduc- tion via code smoothing.Designs, Codes and Cryptography, 93(7):2761–2778,

    doi

  8. [16]

    [Pei09] Chris Peikert

    doi:10.1007/s10623-025-01617-9. [Pei09] Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In Michael Mitzenmacher, editor,41st Annual ACM Symposium on Theory of Computing, pages 333–342, Bethesda, MD, USA, May 31 – June 2,

    doi

  9. [17]

    [Pie12] Krzysztof Pietrzak

    ACM Press.doi:10.1145/1536414.1536461. [Pie12] Krzysztof Pietrzak. Cryptography from learning parity with noise. InConference on Current Trends in Theory and Practice of Informatics,

    doi

  10. [18]

    semanticscholar.org/CorpusID:8357564

    URL:https://api. semanticscholar.org/CorpusID:8357564. [Pra62] E. Prange. The use of information sets in decoding cyclic codes.IRE Transactions on Information Theory, 8(5):5–9, 1962.doi:10.1109/TIT.1962.1057777. [Reg09] Oded Regev. On lattices, learning with errors, random lin...

    1962 doi

  11. [19]

    A method for finding codewords of small weight

    [Ste89] Jacques Stern. A method for finding codewords of small weight. In G´ erard D. Cohen and Jacques Wolfmann, editors,Coding Theory and Applications, volume 388 ofLecture Notes in Computer Science, pages 106–113. Springer, 1989.doi:10.1007/BFb0019850. 16 [YZ16] Yu Yu and J...

    1989 doi

  12. [20]

    [YZ21] Yu Yu and Jiang Zhang

    Springer Berlin Heidelberg, Germany.doi:10.1007/978-3-662-53018-4_9. [YZ21] Yu Yu and Jiang Zhang. Smoothing out binary linear codes and worst-case sub- exponential hardness for LPN. In Tal Malkin and Chris Peikert, editors,Advances in Cryptology – CRYPTO 2021, Part III, volum...

    2021 doi

  13. [21]

    A Deferred Proof Fact 2.1.(Piling Up Lemma).LetX 1, X2,

    Springer, Cham, Switzer- land.doi:10.1007/978-3-030-84252-9_16. A Deferred Proof Fact 2.1.(Piling Up Lemma).LetX 1, X2, . . . , Xk be independent random variables whereX i ← Ber(η), then the random variableS=X 1 +X 2 +· · ·+X k, where addition is overF 2, follows the distribut...

    doi

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.