arxiv: 2605.10056 · v2 · submitted 2026-05-11 · 💻 cs.CR · cs.CC

Recognition: 1 theorem link

· Lean Theorem

Hardness Amplification for (Sparse) LPN

Divesh Aggarwal , Rishav Gupta , Li Zeyong

Authors on Pith no claims yet

Pith reviewed 2026-05-13 03:29 UTC · model grok-4.3

classification 💻 cs.CR cs.CC

keywords Learning Parity with NoiseLPNhardness amplificationSparse LPNaverage-case hardnessdirect productcryptography

0 comments

The pith

An LPN algorithm succeeding with probability ε on some instances converts to one succeeding with probability 1-δ on almost all instances of a scaled-down LPN problem.

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

The paper establishes a self-amplification result for the average-case hardness of Learning Parity with Noise. Any solver that works on a small fraction of LPN instances with success probability ε can be transformed into a solver that works on nearly all instances of a related problem whose noise rate and dimension are reduced by a factor k proportional to (1/δ) log(1/ε). This holds for standard LPN, LPN over larger fields, and the sparse variant where each sample vector has a fixed number of nonzero entries. A reader would care because it shows that the hardness assumption for LPN is robust: weakness on typical instances can be bootstrapped into strength across most instances without changing the underlying problem family.

Core claim

We prove an instance-fraction amplification theorem: for any ε, δ > 0, any algorithm solving LPN_η,n,m with success probability ε yields an algorithm solving LPN_η/k, n/k, m with success probability 1-δ where k = Θ((1/δ) log(1/ε)). Equivalently, an algorithm that recovers the secret on only a small fraction of instances can be converted into one that recovers the secret on almost all instances of the scaled distribution. The same transformation applies to LPN over F_q and to Sparse-LPN.

What carries the argument

The instance-fraction amplification theorem, which applies a direct-product construction to LPN samples to scale the secret length and noise rate while lifting the success probability from ε to 1-δ.

If this is right

Hardness self-amplification holds for standard LPN, Sparse-LPN, and LPN over F_q across wide parameter ranges.
Solving LPN on a small fraction of instances implies solving it on almost all instances after scaling.
The average-case hardness assumption for LPN variants becomes more robust for cryptographic reductions.
The transformation works for any ε and δ without further conditions on η, n, or m.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Security proofs relying on LPN could potentially reduce to even weaker parameter settings if the amplification is tight.
The scaling relation between noise rate and dimension may indicate that LPN hardness behaves uniformly across certain parameter regimes.
The result suggests designing LPN-based schemes by first assuming hardness on a small fraction of instances and then invoking the amplification.

Load-bearing premise

A direct-product construction can be applied to LPN instances to produce the claimed scaling of η and n together with the success-probability boost, without extra restrictions on the original parameters.

What would settle it

An explicit algorithm that solves LPN_η,n,m with probability ε yet cannot be transformed into an algorithm solving LPN_η/k,n/k,m with probability close to 1, for the stated choice of k.

read the original abstract

We prove new hardness amplification results for Learning Parity with Noise ($\mathsf{LPN}$) and its sparse variants. In $\mathsf{LPN}_{\eta,n,m}$, the goal is to recover a secret $\vec s\in\mathbb{F}_2^n$ from $m$ noisy linear samples $(\vec a,b)$, where $\vec a\leftarrow \mathbb{F}_2^n$ is uniform and $b=\langle \vec a,\vec s\rangle + e$ with $e\leftarrow \mathrm{Ber}(\eta)$. Building on the direct-product framework introduced by Hirahara and Shimizu [HS23], we show an 'instance-fraction amplification' theorem: for any $\varepsilon,\delta>0$, any algorithm that solves $\mathsf{LPN}_{\eta,n,m}$ with success probability $\varepsilon$ can be transformed into an algorithm that succeeds with probability $1-\delta$ on a related $\mathsf{LPN}$ distribution with scaled parameters $\mathsf{LPN}_{\eta/k,\;n/k,\;m}$, where $ k=\Theta\!\left(\frac{1}{\delta}\log\frac{1}{\varepsilon}\right). $ Equivalently, an algorithm that solves $\mathsf{LPN}$ on a 'small fraction of instances' can be converted into an algorithm that solves $\mathsf{LPN}$ on 'almost all instances', yielding a self-amplification for a wide range of parameters. We extend the same amplification approach to $\mathsf{LPN}$ over $\mathbb{F}_q$ and to Sparse-$\mathsf{LPN}$, where each query vector $\vec a$ has exactly $\sigma$ nonzero entries. Together, these results establish hardness self-amplification for a broad family of $\mathsf{LPN}$-type problems, strengthening the foundations for assuming the average-case hardness of $\mathsf{LPN}$ and its sparse variants.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper applies the Hirahara-Shimizu direct-product framework to LPN and its variants to claim self-amplification from weak to strong solvers, but the abstract gives no verification that LPN satisfies the framework's hypotheses.

read the letter

The punchline is that this paper takes the direct-product amplification from Hirahara and Shimizu and applies it to LPN, sparse LPN, and LPN over F_q to get a self-amplification result. Any algorithm that works on a small fraction of instances can be turned into one that works on almost all instances, with the noise rate and dimension scaled down by the same factor k roughly (1/delta) log(1/epsilon). This turns an epsilon-success algorithm for LPN_eta,n,m into a (1-delta)-success one for LPN_eta/k, n/k, m. They claim the same for the sparse case with fixed nonzero entries per vector and for the finite-field version. This specific instantiation is new relative to the cited prior work. The abstract states the result cleanly and explains its relevance to strengthening average-case hardness assumptions used in post-quantum crypto. That part is useful for anyone tracking how direct-product techniques carry over to noisy linear problems. The main soft spot is the complete absence of any proof sketch, error analysis, or check that LPN meets the conditions of the HS23 framework. LPN consists of noisy linear equations with fixed m samples, and scaling both n and eta downward at once could easily violate the density or independence requirements that the framework needs. The stress-test note correctly flags the risk of unstated restrictions on the parameters, and nothing in the abstract rules it out. Without seeing how the authors handle the noisy structure or confirm the hypotheses hold for a wide range, the claim rests on an unverified transfer. This work is aimed at cryptographers who rely on LPN or sparse LPN assumptions in scheme design. A reader following hardness amplification results would find the parameter scaling interesting if it holds up. I recommend sending it to peer review. The idea is straightforward enough that a referee can check the reduction details and any hidden conditions during revision. If the math goes through cleanly, it adds a modest but concrete strengthening to the LPN hardness foundation.

Referee Report

2 major / 3 minor

Summary. The manuscript proves hardness amplification results for LPN and its variants by instantiating the Hirahara-Shimizu direct-product framework. The central result is an instance-fraction amplification theorem: for any ε,δ>0, an algorithm solving LPN_η,n,m with success probability ε yields an algorithm solving LPN_η/k,n/k,m with success probability 1-δ, where k=Θ((1/δ)log(1/ε)). The same approach is extended to LPN over F_q and to Sparse-LPN (where each a has exactly σ nonzero entries), establishing self-amplification for a broad family of LPN-type problems.

Significance. If correct, the result strengthens average-case hardness assumptions for LPN and sparse LPN by converting weak success probability into near-certain success on scaled instances. This is useful for cryptography, where LPN underpins many constructions, and the explicit parameter scaling plus extensions to sparse and finite-field variants add concrete value. The work gives credit to the HS23 framework while providing a direct instantiation with verifiable parameter relations.

major comments (2)

[§3] §3 (application of HS23): The manuscript must explicitly verify that LPN_η,n,m satisfies every hypothesis of the Hirahara-Shimizu direct-product theorem (e.g., verifiable search problem, sufficient instance density or independence). The claimed scaling to LPN_η/k,n/k,m with fixed m may violate these when k grows large, since η/k becomes arbitrarily small while the effective dimension n/k shrinks; the abstract's assertion of validity for a 'wide range of parameters' therefore requires a precise statement of the admissible (η,n,m) regime.
[§5] §5 (Sparse-LPN extension): The reduction for Sparse-LPN must confirm that the fixed sparsity σ remains compatible with the direct-product construction after dimension reduction to n/k. If σ is constant while n/k decreases, the relative sparsity changes and could invalidate the density or independence assumptions inherited from HS23; the paper should state the required relation between σ, n, and k.

minor comments (3)

[Abstract] The abstract and introduction use 'wide range of parameters' without listing concrete bounds; replace with an explicit statement of the admissible regime for η, n, m, σ.
[Theorem 1] Notation for the scaled parameters (η/k, n/k) should be introduced once in the theorem statement and used consistently thereafter to avoid ambiguity when k depends on ε and δ.
[Introduction] The paper should include a short comparison paragraph with prior LPN hardness amplification results (e.g., those based on direct-product or parallel repetition) to clarify the novelty of the instance-fraction approach.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestions. We address each major comment below and will revise the manuscript accordingly to strengthen the presentation.

read point-by-point responses

Referee: [§3] §3 (application of HS23): The manuscript must explicitly verify that LPN_η,n,m satisfies every hypothesis of the Hirahara-Shimizu direct-product theorem (e.g., verifiable search problem, sufficient instance density or independence). The claimed scaling to LPN_η/k,n/k,m with fixed m may violate these when k grows large, since η/k becomes arbitrarily small while the effective dimension n/k shrinks; the abstract's assertion of validity for a 'wide range of parameters' therefore requires a precise statement of the admissible (η,n,m) regime.

Authors: We agree that an explicit verification of the HS23 hypotheses is required for rigor. In the revision we will add a dedicated paragraph in §3 that checks each condition: LPN is a verifiable search problem (a candidate secret can be validated against the m samples up to the known noise rate), the instance distribution is dense and uniform, and the required independence holds for the direct-product construction. Regarding scaling with fixed m: m denotes samples per instance and remains unchanged because amplification is performed across independent instances; the per-instance sample count is not altered. We will state the admissible regime explicitly: k ≤ min(n/2, 1/(2η)) so that n/k ≥ n/2 (still growing with n) and η/k ≤ 1/2. This covers the asymptotic regime claimed in the abstract while preventing the cited violations. The revision will make these bounds precise. revision: yes
Referee: [§5] §5 (Sparse-LPN extension): The reduction for Sparse-LPN must confirm that the fixed sparsity σ remains compatible with the direct-product construction after dimension reduction to n/k. If σ is constant while n/k decreases, the relative sparsity changes and could invalidate the density or independence assumptions inherited from HS23; the paper should state the required relation between σ, n, and k.

Authors: We will revise §5 to include the requested confirmation. In the Sparse-LPN case the HS23 direct-product construction reduces the secret dimension while preserving the exact support size σ of each sample vector a (via coordinate selection or projection that respects the original sparsity pattern). Compatibility with the inherited density and independence assumptions requires n/k ≥ σ so that σ-sparse vectors remain possible in the reduced space. We will state the explicit relation: k ≤ n/(2σ), which ensures relative sparsity σk/n ≤ 1/2 and keeps the scaled distribution inside the regime where HS23 applies. This condition is compatible with our k = Θ((1/δ)log(1/ε)) whenever the original n is sufficiently larger than σ times that quantity, which is the natural setting for fixed-σ Sparse-LPN. revision: yes

Circularity Check

0 steps flagged

No circularity; central theorem applies external HS23 framework to LPN

full rationale

The paper's derivation chain consists of instantiating the direct-product framework from Hirahara and Shimizu [HS23] (distinct authors) on LPN_η,n,m to obtain the stated instance-fraction amplification: any ε-success algorithm yields a (1-δ)-success algorithm on LPN_η/k,n/k,m with k=Θ((1/δ)log(1/ε)). No step reduces by definition, fitted parameter, or self-citation to the paper's own inputs. The abstract and claim explicitly attribute the result to the external framework, and the extension to F_q and Sparse-LPN follows the same non-circular application. This is a standard reduction whose validity hinges on whether LPN meets the framework hypotheses, but that is an external correctness question, not internal circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the direct-product framework from Hirahara and Shimizu 2023 together with standard properties of linear algebra and Bernoulli noise over finite fields; no new free parameters or invented entities are introduced.

axioms (1)

standard math Standard properties of uniform random vectors in F_2^n and Bernoulli noise
Used to define the LPN distribution and the success probability transformation.

pith-pipeline@v0.9.0 · 5640 in / 1262 out tokens · 119664 ms · 2026-05-13T03:29:09.885679+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

any algorithm that solves LPN_η,n,m with success probability ε can be transformed into an algorithm that succeeds with probability 1-δ on a related LPN distribution with scaled parameters LPN_η/k, n/k, m, where k=Θ(1/δ log 1/ε)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

[1]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =

Hirahara, Shuichi and Shimizu, Nobutaka , title =. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =. 2023 , isbn =. doi:10.1145/3564246.3585189 , abstract =

work page doi:10.1145/3564246.3585189 2023
[2]

American Mathematical Monthly , year=

A Remark on Stirling’s Formula , author=. American Mathematical Monthly , year=

work page
[3]

Furst and Michael J

Avrim Blum and Merrick L. Furst and Michael J. Kearns and Richard J. Lipton , title =. CRYPTO '93 , series =. 1993 , publisher =

work page 1993
[4]

Journal of the ACM , volume =

Avrim Blum and Adam Kalai and Hal Wasserman , title =. Journal of the ACM , volume =

work page
[5]

Annual international conference on the theory and applications of cryptographic techniques , pages=

Worst-case hardness for LPN and cryptographic hashing via code smoothing , author=. Annual international conference on the theory and applications of cryptographic techniques , pages=. 2019 , organization=

work page 2019
[6]

IACR International Conference on Public-Key Cryptography , pages=

Worst and average case hardness of decoding via smoothing bounds , author=. IACR International Conference on Public-Key Cryptography , pages=. 2025 , organization=

work page 2025
[7]

Smoothing Out Binary Linear Codes and Worst-Case Sub-exponential Hardness for LPN

Yu, Yu and Zhang, Jiang. Smoothing Out Binary Linear Codes and Worst-Case Sub-exponential Hardness for LPN. Advances in Cryptology -- CRYPTO 2021. 2021

work page 2021
[8]

Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing , pages =

Regev, Oded , title =. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing , pages =. 2005 , isbn =. doi:10.1145/1060590.1060603 , abstract =

work page doi:10.1145/1060590.1060603 2005
[9]

Smoothing Codes and Lattices: Systematic Study and New Bounds , year=

Debris-Alazard, Thomas and Ducas, Léo and Resch, Nicolas and Tillich, Jean-Pierre , journal=. Smoothing Codes and Lattices: Systematic Study and New Bounds , year=

work page
[10]

, journal=

Prange, E. , journal=. The use of information sets in decoding cyclic codes , year=

work page
[11]

Proceedings of the 7th International Workshop on Post-Quantum Cryptography - Volume 9606 , pages =

Canto Torres, Rodolfo and Sendrier, Nicolas , title =. Proceedings of the 7th International Workshop on Post-Quantum Cryptography - Volume 9606 , pages =. 2016 , isbn =. doi:10.1007/978-3-319-29360-8_10 , abstract =

work page doi:10.1007/978-3-319-29360-8_10 2016
[12]

and Blum, Manuel , title =

Hopper, Nicholas J. and Blum, Manuel , title =. Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology , pages =. 2001 , isbn =

work page 2001
[13]

, title =

Juels, Ari and Weis, Stephen A. , title =. Proceedings of the 25th Annual International Conference on Advances in Cryptology , pages =. 2005 , isbn =. doi:10.1007/11535218_18 , abstract =

work page doi:10.1007/11535218_18 2005
[14]

Conference on Current Trends in Theory and Practice of Informatics , year=

Cryptography from Learning Parity with Noise , author=. Conference on Current Trends in Theory and Practice of Informatics , year=

work page
[15]

IND-CCA secure cryptography based on a variant of the LPN problem , year =

D\". IND-CCA secure cryptography based on a variant of the LPN problem , year =. Proceedings of the 18th International Conference on The Theory and Application of Cryptology and Information Security , pages =. doi:10.1007/978-3-642-34961-4_30 , abstract =

work page doi:10.1007/978-3-642-34961-4_30
[16]

Simple Chosen-Ciphertext Security from Low-Noise LPN

Kiltz, Eike and Masny, Daniel and Pietrzak, Krzysztof. Simple Chosen-Ciphertext Security from Low-Noise LPN. Public-Key Cryptography -- PKC 2014. 2014

work page 2014
[17]

, booktitle=

Alekhnovich, M. , booktitle=. More on average case vs approximation complexity , year=

work page
[18]

Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise

Jain, Abhishek and Krenn, Stephan and Pietrzak, Krzysztof and Tentes, Aris. Commitments and Efficient Zero-Knowledge Proofs from Learning Parity with Noise. Advances in Cryptology -- ASIACRYPT 2012. 2012

work page 2012
[19]

International Colloquium on Automata, Languages and Programming , year=

How to Encrypt with the LPN Problem , author=. International Colloquium on Automata, Languages and Programming , year=

work page
[20]

Yu, Yu and Zhang, Jiang and Weng, Jian and Guo, Chun and Li, Xiangxue , title =. Advances in Cryptology – ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8–12, 2019, Proceedings, Part II , pages =. 2019 , isbn =. doi:10.1007/978-3-030-34621-8_1 , abstract =

work page doi:10.1007/978-3-030-34621-8_1 2019
[21]

doi:10.1007/978-3-642-34047-5_20 , author=

Lapin: An Efficient Authentication Protocol Based on Ring-LPN , booktitle=. doi:10.1007/978-3-642-34047-5_20 , author=

work page doi:10.1007/978-3-642-34047-5_20
[22]

A Practical Public Key Encryption Scheme Based on Learning Parity With Noise , year=

Yu, Zhimin and Gao, Chong-Zhi and Jing, Zhengjun and Gupta, Brij Bhooshan and Cai, Qiuru , journal=. A Practical Public Key Encryption Scheme Based on Learning Parity With Noise , year=

work page
[23]

Applebaum, Benny and Ishai, Yuval and Kushilevitz, Eyal , title =. Comput. Complex. , month = apr, pages =. 2008 , issue_date =. doi:10.1007/s00037-007-0237-6 , abstract =

work page doi:10.1007/s00037-007-0237-6 2008
[24]

BQP and the polynomial hierarchy,

Applebaum, Benny and Barak, Boaz and Wigderson, Avi , title =. Proceedings of the Forty-Second ACM Symposium on Theory of Computing , pages =. 2010 , isbn =. doi:10.1145/1806689.1806715 , abstract =

work page doi:10.1145/1806689.1806715 2010
[25]

Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , pages =

Ishai, Yuval and Kushilevitz, Eyal and Ostrovsky, Rafail and Sahai, Amit , title =. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , pages =. 2008 , isbn =. doi:10.1145/1374376.1374438 , abstract =

work page doi:10.1145/1374376.1374438 2008
[26]

Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security , pages =

Boyle, Elette and Couteau, Geoffroy and Gilboa, Niv and Ishai, Yuval , title =. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security , pages =. 2018 , isbn =. doi:10.1145/3243734.3243868 , abstract =

work page doi:10.1145/3243734.3243868 2018
[27]

Annual International Cryptology Conference , pages=

Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN , author=. Annual International Cryptology Conference , pages=. 2023 , organization=

work page 2023
[28]

2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=

Correlated pseudorandom functions from variable-density LPN , author=. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2020 , organization=

work page 2020
[29]

Annual International Cryptology Conference , pages=

Correlated pseudorandomness from expand-accumulate codes , author=. Annual International Cryptology Conference , pages=. 2022 , organization=

work page 2022
[30]

Annual International Cryptology Conference , pages=

Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes , author=. Annual International Cryptology Conference , pages=. 2021 , organization=

work page 2021
[31]

Annual International Cryptology Conference , pages=

Correlated pseudorandomness from the hardness of quasi-abelian decoding , author=. Annual International Cryptology Conference , pages=. 2023 , organization=

work page 2023
[32]

Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing , pages=

Indistinguishability obfuscation from well-founded assumptions , author=. Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing , pages=

work page
[33]

Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=

Indistinguishability obfuscation from LPN over F p, DLIN, and PRGs in NC 0 , author=. Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=. 2022 , organization=

work page 2022
[34]

Annual International Cryptology Conference , pages=

Expand-convolute codes for pseudorandom correlation generators from LPN , author=. Annual International Cryptology Conference , pages=. 2023 , organization=

work page 2023
[35]

IACR International Conference on Public-Key Cryptography , pages=

Improved discrete gaussian and subgaussian analysis for lattice cryptography , author=. IACR International Conference on Public-Key Cryptography , pages=. 2020 , organization=

work page 2020
[36]

Essential coding theory , author=

work page
[37]

Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

Public-key cryptosystems from the worst-case shortest vector problem , author=. Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

work page
[38]

Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

Classical hardness of learning with errors , author=. Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

work page
[39]

Proceedings of Thirty Eighth Conference on Learning Theory , pages =

Algorithms for Sparse LPN and LSPN Against Low-noise (extended abstract) , author =. Proceedings of Thirty Eighth Conference on Learning Theory , pages =. 2025 , editor =

work page 2025