Hardness Amplification for (Sparse) LPN Divesh Aggarwal, Rishav Gupta, and Li Zeyong
arXiv:2605.10056v1 [cs.CR] 11 May 2026
1
National University of Singapore, [email protected] 2 National University of Singapore, [email protected] 3 National University of Singapore, [email protected]
Abstract. We prove new hardness amplification results for Learning Parity with Noise (LPN) and its sparse variants. In LPNη,n,m , the goal is to recover a secret s ∈ Fn 2 from m noisy linear samples (a, b) , where a ← Fn 2 is uniform and b = ⟨a, s⟩ + e with e ← Ber(η) . Building on the direct-product framework introduced by Hirahara and Shimizu [HS23], we show an instance-fraction amplification theorem: for any ε, δ > 0 , 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ε . Equivalently, an algorithm that solves LPN on a small fraction of instances can be converted into an algorithm that solves LPN on almost all instances, yielding a self-amplification for a wide range of parameters. We extend the same amplification approach to LPN over Fq and to Sparse- LPN , where each query vector a has exactly σ nonzero entries. Together, these results establish hardness self-amplification for a broad family of LPN-type problems, strengthening the foundations for assuming the average-case hardness of LPN and its sparse variants.
1 Introduction Learning Parity with Noise (LPN) . Learning Parity with Noise (LPN) is a noisy linear problem over F2 and can be viewed as a randomized form of syndrome decoding. In the standard search version, one is given n a matrix A ∈ Fm×n and a vector b = As + e ∈ Fm 2 , where the secret s ← F2 is uniform and the noise 2 m vector e ← Ber(η) has independent Bernoulli coordinates. The goal is to recover s from (A, b) . Since the early 1990s, LPN and its variants have been used as average-case hardness assumptions in cryptography and learning theory [BFKL93,BKW03]. Many constructions rely on LPN in different parameter regimes. In the constant-noise regime (typically m = poly(n) and constant η ), it gives light weight shared secret authentication protocols such as [HB01,JW05]. In lower-noise regimes (often m = O(n) and η = O(n−1/2 ) ), it implies public-key encryption, including dual-Regev-style schemes [Ale03] and CCA-secure variants [DMQN12,KMP14]. LPN has also been used for pseudorandom generators and one-way functions [Pie12], symmetric-key encryption with adaptive IND-CPA security [GRS08], and commitments and zero-knowledge proofs [JKPT12] (see also [YZW + 19] for hashing in lower-noise regimes). A practical feature of LPN is efficiency: operations over F2 correspond to XOR/AND computations, and Ring- LPN variants have been studied for efficient authentication and encryption [HKL + 12,YGJ + 18]. Sparse Learning Parity with Noise. Sparse- LPN is a variant of LPN where the challenge matrix A ∈ Fm×n 2 is row-sparse: each row has Hamming weight at most (often exactly) σ = O(1) . The samples have the form u = As + e for a uniform secret s ∈ Fn2 and noise e ← Ber(η)m (typically with inverse-polynomial η ). Sparse- LPN has been used for linear-stretch pseudorandom generators in NC0 [AIK08], public-key encryption from related sparse-XOR regimes [ABW10], and a number of cryptographic primitives based on noisy local linear constraints, [IKOS08,BCGI18,BCG + 20,BCG + 22,CRR21,RRT23,DIJL23,BCCD23]. Sparse LPN (and the more general Local Functions with Noise model) assumption plays a key role in recent work on indistinguishability obfuscation [JLS21,JLS22].
Worst-case to average-case reductions. For the closely related Learning with Errors (LWE) problem, worstcase-to-average-case reductions from lattice problems are known and form a main part of its foundations [Reg05,Pei09,BLP + 13]. For LPN , the known worst-case-to-average-case results are weaker. The first such reductions for variants of LPN use code smoothing. Brakerski, Lyubashevsky, Vaikuntanathan and Wichs [BLVW19] gave Fourier-analytic smoothing lemmas for binary linear codes, reducing worst-case instances of a balanced nearest codeword problem at very low error rate (about logn n ) to average-case LPN at very high noise (about 12 − n1c ). Yu and Zhang [YZ21] extended this approach and obtained implications for constant-noise LPN under stronger nearest-codeword assumptions. Debris-Alazard and Resch [DR25] developed a more general Fourier-analytic framework and clarified limitations of smoothing bounds. A common feature of these results is that they start from worst-case regimes with extremely low relative error, for example corruption rate t/m = O(log n/n) . In this regime, one can solve the worst-case instance in quasipolynomial time by sampling r = Θ(n) equations, enumerating the O(log n) corrupted ones (which holds with high probability), and then applying Gaussian elimination. Thus, these reductions start from worst-case sources that are far from the parameters used in cryptography, and they do not rule out quasipolynomial-time algorithms for average-case LPN in cryptographic regimes (e.g., constant noise or η = 1/nc ). These works leave open the following natural question. Question 1 (Next best to worst-case-to-average-case for LPN ). Can one prove an “almost” worst-case-toaverage-case statement for Search-LPN in cryptographic regimes: namely, that hardness on a small δ fraction of random instances can be amplified to hardness on almost all random instances (and hence average-case hardness), under a standard parameter transformation? Sparse- LPN and worst-case to average-case. For Sparse- LPN , the situation is even less developed. Unlike LWE, and unlike the partial progress for LPN via code smoothing, there are currently no known worst-caseto-average-case reductions for Sparse- LPN in cryptographic regimes. Moreover, existing approaches based on smoothing and extractor-style “random hashing” do not seem to apply in any useful way: smoothing arguments rely on properties of dense random codes, while sparse instances correspond to highly structured, low-density constraints; and applying sparse hashing tends to destroy sparsity or forces parameters into regimes that are algorithmically easy. This leaves open the following analogue of the question above. Question 2 (Next best to worst-case-to-average-case for Sparse- LPN ). Can one prove an “almost” worstcase-to-average-case statement for Search Sparse- LPN in cryptographic regimes: namely, that hardness on a small δ fraction of random Sparse- LPN instances can be amplified to hardness on almost all instances (and hence average-case hardness), under a standard parameter transformation that preserves sparsity? Our perspective: self-amplification. We take a different route and work directly with the standard averagecase LPN distribution. Our results are a form of instance-fraction amplification for Search-LPN : assuming that LPN is hard on even a small fraction of random instances implies hardness on almost all instances (and hence average-case hardness) at related parameters. Roughly, given an algorithm that recovers the secret on random instances with success probability ε , we build an algorithm that recovers the secret with success probability 1 − δ on a 1 − δ fraction of instances, for small δ (with an explicit parameter change). A full worst-case-to-average-case reduction would correspond to the special case δ = 0 . Our proof uses the self-amplification framework introduced by Hirahara and Shimizu [HS23]. We instantiate their framework for LPN by showing how to combine k independent LPN instances into a single larger instance with an explicitly transformed noise rate, and then applying the HS23 analysis together with a verification test that succeeds on all but a negligible fraction of instances. 2
Hirahara and Shimizu’s approach. Hirahara and Shimizu [HS23] consider a distributional problem (f, µ) and its k -fold product (f ×k , µ×k ) . The standard direct-product reduction places an input x ← µ into a random coordinate of a k -tuple and fills the other coordinates with fresh samples from µ , then queries a solver for the product problem. The question is whether this procedure samples from the solver’s easy inputs often enough to give high success on most base inputs. HS23 show that for suitable k (typically k = Θ(1/δ · log(1/ε)) ), this amplifies success on the product problem into much higher success on the base problem for a 1 − δ fraction of inputs. 1.1
Our contributions and techniques
From HS23 to LPN . We use the hardness self-amplification framework of Hirahara and Shimizu [HS23]. In our setting, the underlying search problem is Search- LPN : the function f maps an LPN instance (A, b) to its secret s (and is undefined on the negligible set of non-decodable instances; we handle this using a verification/decodability test). To apply [HS23], we need to relate the k -fold product distribution (f ×k , µ×k ) to a single LPN distribution. We do this by an explicit product-to-single embedding. Given k independent LPN instances (Ai , bi = Ai si + ei ) m×(n/k)
with Ai ∈ F2
for i ∈ [k] ,
, we form A := [A1 | A2 | · · · | Ak ] ∈ Fm×n , 2
b :=
k M
bi = As ⊕ e ,
i=1
where s := (s1 , . . . , sk ) ∈ Fn2 and e := distribution transforms exactly as e ∼ Ber(η ′ )m
Lk
i=1 ei . The matrix
η′ =
with
A is uniform over Fm×n , and the noise 2
1 − (1 − 2η)k . 2
Thus, any solver for a single LPN instance at parameters (n, η ′ ) yields a solver for k independent LPN instances at parameters (n/k, η) with the same success probability. Combining this embedding with the sampler analysis of [HS23] gives our amplification theorems for LPN (and similarly over Fq ). Sparse- LPN . For Sparse- LPN , the same embedding suggests that sparsity should scale by a factor of k when we concatenate blocks. The difficulty is that the usual Sparse- LPN distribution fixes the row weight to be exactly σ , and this distribution is not closed under concatenation into blocks. We handle this by introducing an approximate-sparse variant in which each entry of A is independently 1 with probability σ/n (so each row has expected weight σ ). This distribution is closed under block concatenation: concatenating k independent matrices of dimension n/k with per-entry probability (σ/k)/(n/k) = σ/n again gives an n -column matrix with per-entry probability σ/n . We prove selfamplification for this approximate-sparse variant using the same product-to-single embedding and [HS23]. To return to the standard Sparse- LPN model (exact row weight σ ), we use a simple filtering reduction: from an approximate-sparse sample, keep only those rows of weight exactly σ . Conditioned on a row having weight σ , its distribution is uniform over weight- σ vectors, so the retained rows form a valid Sparse- LPN instance. This incurs only a controlled blowup in the number of samples. q -ary extension. All steps above extend to Fq for prime q . The embedding is identical, except that the noise sum is over Fq and the noise parameter becomes η ′ = 1 − (1 − η)k . Informal summary of results. Below, arrows should be read as: “a solver for the bottom problem implies a solver for the top problem,” with an explicit polynomial-time reduction. 3
– Self-amplification for Search-LPN . For suitable k and all relevant parameter ranges, a solver for LPNη′ , n, m ×k
′
k = 1−(1−2η) 2
′
k
implies a solver for (LPNη, n/k, m ) with success ε, where η (binary) or η = 1 − (1 − η) ( q -ary). Using [HS23] plus verification, this yields amplification: from success ε on the product distribution we obtain success at least 1 − δ on a 1 − δ fraction of base instances (for appropriate k ). – Sparse case via approximate-sparse. We prove the same amplification statement for the approximatesparse distribution (per-entry probability σ/n ), and then reduce approximate-sparse to exact-sparse by filtering rows of Hamming weight exactly σ , with a mild increase in the number of samples. The sparsity rate is preserved (dimension and sparsity scale together). We expect the same approach to apply to other noisy linear problems whose instance distributions are compatible with direct-product embeddings and admit efficient verification on almost all inputs. 1.2
Discussion and Comparison to Prior Work
Why leftover-hash style “smoothing” does not help for LPN . A standard way to obtain worst-case-to-averagecase implications for lattice problems is to apply an extractor-style transformation (see, e.g., [GMPW20] in the LWE setting). The basic idea is to left-multiply by a random hash matrix M ∈ Fm×m whose rows are 2 σ -sparse, with the goal that for most A the pair (M A, A) is statistically close to (U, A) , where U is uniform over Fm×n . For such a leftover-hash argument to give small statistical distance, the hash family must have 2 sufficiently large entropy; for σ -sparse rows this requires roughly σ log
n σ
≳ n
⇒
n log n . 1−(1−2η)σ ≈ 2
σ ≳
Under this transformation, M (As + e) = (M A)s + M e, so the noise rate changes to η ′ = ση (for small η ). Therefore, if σ ≳ n/ log n and we want η ′ bounded away from 1/2 , we must have η ≲ (log n)/n . This is a regime where LPN is algorithmically easy when m = poly(n) , since the number of corrupted equations is at most O(log n) and one can enumerate the error locations and solve by Gaussian elimination. In short, leftover-hash style smoothing pushes the parameters into a regime that is not relevant for cryptography. For sparse- LPN , the situation is worse: left-multiplication by a dense hash destroys sparsity, while restricting to sparse hashes runs into the same entropy/noise barrier above. We are not aware of a way to obtain useful cryptographic-parameter implications for sparse- LPN from such smoothing arguments. Our approach and why it avoids these bottlenecks. Our results follow the hardness self-amplification framework of Hirahara and Shimizu [HS23]. The starting point is that solving k independent instances with probability ε can, under suitable conditions, be amplified to success close to 1 on almost all instances. In the HS23 framework, this amplification is obtained by analyzing the standard direct-product reduction as a sampler on the input distribution. We instantiate this framework for LPN using a product-to-single embedding: we combine k independent LPN instances in dimension n/k into one LPN instance in dimension n by concatenating the challenge matrices and summing the responses. Under this embedding, the noise parameter transforms exactly as k ′ = 1−(1−2η) and ηq′ = 1 − (1 − η)k , while the dimension scales by n′ = n/k . Together with the ηbin 2 sampler analysis of [HS23], this gives quantitative instance-fraction amplification: for appropriate k (e.g., k = poly(n) ), a solver with success ε on the product distribution can be converted into a solver that succeeds with probability at least 1 − δ on a 1 − δ fraction of instances, with δ controlled by k (see Section 3 for the precise statement and parameters). Importantly, this amplification holds in the standard cryptographic noise regimes for LPN (constant noise down to η = 1/nα ), without forcing η into the easy (log n)/n range. For sparse- LPN , we avoid the sparsity blow-up that arises in hashing-based approaches by going through an approximate-sparse variant, where each entry of A is 1 independently with probability σ/n . This distribution is compatible with the product-to-single embedding. We prove self-amplification for the approximatesparse variant, and then reduce back to the standard exact-sparse model by filtering rows of weight exactly σ . This step increases the number of samples by only a controlled factor and loses only negligible success probability, while keeping sparsity at essentially σ . 4
with success ε
Relation to [HS23]. Hirahara and Shimizu [HS23] illustrate their framework on linear-algebraic tasks such as matrix multiplication, where amplification can be combined with a cancellation identity (e.g., expanding (A+R)(B+S) ). For LPN , such cancellation identities are not available because the unknown secret s prevents us from generating the analogue of “random masks” of the form Rs with the correct noise. Our contribution is to show how to apply the HS23 framework to LPN anyway, by giving a direct-product embedding that stays within the LPN distribution (including sparse variants) and by using a verification/decodability procedure to support instance-fraction amplification in cryptographic parameter regimes. We leave open the question of obtaining a true worst-case-to-average-case reduction for LPN with parameters comparable to those achieved in our work. 1.3
Organization of the Paper
In Section 2, we recollect some notations and tools useful for our presentation. We also show that for each of the LPN variants considered, a random instance is (essentially) uniquely decodable with all but negligible probability. In Section 3, we present a detailed exposition of the self hardness amplification framework introduced in [HS23]. In Section 4, we prove self-hardness amplification for the standard LPNq,η,n,m problem and its binary analogue LPNη,n,m , leveraging the direct-product framework of [HS23]. To extend these results to sparse=σ LPN , we introduce a new variant LPN≈σ η,n,m . Recall that in the sparse version LPNη,n,m , each query vector a ∈ Fn2 has Hamming weight exactly σ , whereas in the approximate-sparse variant LPN≈σ η,n,m , each coordinate of a is sampled so that the expected Hamming weight is σ . In Section 5, we establish hardness self-amplification for this approximate-sparse variant, and then give a =σ reduction from LPN≈σ η,n,M to the exact-sparse version LPNη,n,m by discarding non- σ -sparse samples. While this incurs a mild blowup in sample complexity, the loss in success probability is only negligible. Combining =kσ these steps, we obtain a reduction from LPN≈σ η,n,M with success 1 − δ to LPNkη,kn,m with success ε , for both the binary and q -ary variants, thereby strengthening the hardness foundations of LPN as well as Sparse- LPN .
2 Preliminaries We use the following notations. For a set S , we write x ∼ S to mean that x is chosen uniformly at random from S . For a distribution D ,we write x ∼ D to mean that x is drawn according to D . We also use the notation [n] to denote the set of all binary vectors in Fn2 of Hamming weight exactly s . We use the notation s ∥x∥0 in order to denote the hamming weight of x . 2.1
Information Theory and Probability
We begin by defining the q -ary entropy function, Hq . Definition 1 ( q -ary entropy function). For ρ ∈ [0, 1] , the q -ary entropy function is defined as follows, Hq (ρ) := ρ logq (q − 1) − ρ logq ρ − (1 − ρ) logq (1 − ρ). We can use the q -ary entropy function in order to estimate the volume of a Hamming ball. Lemma 1 (Entropy Bound [GRS12]). For integers n ≥ 1 and 0 ≤ k ≤ n , let Bq (k, n) denote the number of vectors in Fnq of Hamming weight at most k then, q nHq (ρ)−o(n) ≤ Bq (ρn, n) ≤ q nHq (ρ) , 5
for ρ ∈ [0, 1 − 1/q].
The following lemma is the standard Chernoff’s Bound. Pm Lemma 2 (Chernoff ’s Bounds). Let X = i=1 Xi , where Xi are independent Bernoulli random variables, and let µ = E[X] . Then for any 0 < δ < 1 , 2 δ Pr[X ≤ (1 − δ)µ] ≤ exp − µ , 2 and for any δ > 0 , δ2 µ . Pr[X ≥ (1 + δ)µ] ≤ exp − 2+δ
We now define the Bernoulli distribution. Definition 2 (Bernoulli Distribution). A boolean random variable X is said to follow a Bernoulli distribution with parameter η ∈ [0, 1] , denoted X ∼ Ber(η) , if Pr[X = 1] = η
Pr[X = 0] = 1 − η.
and
The following lemma describes the distribution generated by sum of k identical and independent Bernoulli random variables over F2 . Lemma 3. Let X1 , . . . , Xk be independent random variables where Xi ∼ Ber(η) , then the following random variable, S = X1 ⊕ X2 ⊕ · · · ⊕ Xk , k
follows the distribution Ber(θk (η)) , where θk (η) = 1−(1−2η) . 2 Proof. Let Yi := (−1)Xi ∈ {±1} . Then E[Yi ] = (1 − η) · 1 + η · (−1) = 1 − 2η . Notice that (−1)S := Y1 · Y2 · · · Yk . Since Y1 , . . . , Yk are independently distributed, we have that k k hY i Y (−1)Xi = E[(−1)Xi ] = (1 − 2η)k . E (−1)S = E i=1
i=1
But E[(−1)S ] = Pr[S = 0] − Pr[S = 1] = 1 − 2 Pr[S = 1] . Hence Pr[S = 1] =
1 − (1 − 2η)k =: θk (η) . 2
Therefore S ∼ Ber(θk (η)) .
⊔ ⊓
We now extend the notion of the Bernoulli distribution to finite fields Fq . Definition 3 (General Bernoulli Distribution). A random variable X ∈ Fq is said to follow the distribution Berq (η) , if it samples a uniform element from Fq with probability η , otherwise returns 0 . More formally, η if x = 0, (1 − η) + q X ∼ Berq (η) if Pr[X = x] = η if x ∈ Fq \ {0}. q 6
Observe that Ber(η) distribution is same as Ber2 (2η) distribution. The only reason we don’t unify both definitions is to keep both definitions consistent with those in the literature. In the following lemma we describe the distribution generated by sum of k identical and independent general Bernoulli random variables. Lemma 4. Let X1 , . . . , Xk be independent random variables where, Xi ∼ Berq (η) then the following random variable, S = X1 + X2 + · · · + Xk
mod q,
over Fq is distributed as Berq (ϕk (η)) , where ϕk (η) = 1 − (1 − η)k . Proof. Use the equivalent sampling rule for Berq (η) : with probability 1 − η output 0 , and with probability η output a uniform element of Fq . Write Xi = Bi Ui , where Bi ∼ Ber(η) and Ui ∼ Unif(Fq ) are independent (and all pairs (Bi , Ui ) are independent across i ). Then S =
k X
Bi Ui .
i=1
If all Bi = 0 (which happens with probability (1 − η)k ), then S = 0 . Otherwise, conditioned onPthe event that, there exists at least one i such that Bi = 1 , the random variable S is Ui + Y , where Y = j̸=i Bj Uj is independent of Ui , and hence S is uniform in Fp . This implies that 1 = Pr[S = 0] = (1 − η)k · 1 + 1 − (1 − η)k · q
ϕk (η) 1 − ϕk (η) + , q
and for each a ̸= 0 , 1 ϕk (η) 1 − (1 − η)k · = . q q This shows that S id distributed as Berq ϕk (η) . Pr[S = a] =
⊔ ⊓
Note, both θk (η) and ϕk (η) are smaller than kη . The following is the standard notion of statistical distance. Definition 4 (Statistical Distance). Let D1 and D2 be two probability distributions over the same finite domain X . Let PrD [x] denote the probability that the random variable sampled from the distribution D takes the value x . The statistical distance (or total variation distance) between them is defined as ∆(D1 , D2 ) =
1X Pr[x] − Pr[x] . D1 D2 2 x∈X
The following is the standard data processing inequality. Lemma 5 (Data Processing Inequality). Let P, Q be discrete random variables on a finite set. For any (possibly randomized) function f , ∆ f (P ), f (Q) ≤ ∆(P, Q). 7
2.2
Stirling’s Approximation
Lemma 6 (Stirling-Robbins Bound [Rob55]). For every integer n ≥ 1 , n n 1 √ √ 1 2πn ne e 12n+1 < n! < 2πn ne e 12n . Corollary 1 (Stirling approximation for binomial coefficients). For integers n ≥ s ≥ 1 , the binomial coefficient satisfies, n 1 nn nn 1 p p ≤ ≤ . · · s 8s(1 − ns ) ss (n − s) n−s 2πs(1 − ns ) ss (n − s) n−s We include a standard proof in Section A for completeness. 2.3
Variants of LPN
LPN is a distributional problem, equipped with distributions S, Da , De . For a secret vector s sampled from distribution S , we are given oracle access to samples of (a, b) , where a ∼ Da and b = ⟨a, s⟩ + e with e ∼ De . We can collectively view these samples as (A, b = A · s + e) . The goal of the Search- LPN problem is to recover the secret s given (A, b) . Now by changing the distributions associated with the LPN problem we define the following variants, 1. This is the classical variant defined over the binary field, Definition 5 ( LPNη,n,m ). For a uniformly random secret s ∼ Fn2 , we are given oracle access to m samples of the form (a, b) , where a is uniform in Fn2 and b = ⟨a, s⟩+e with e ∼ Ber(η) . The goal of the problem is to recover the secret s using these m samples. 2. The following is the large field variant which generalizes this problem to Fq , Definition 6 ( LPNq,η,n,m ). n For a prime q , and a secret s ∼ Fnq , we are given access to m samples (a, b) , where a ∼ (Fq ) uniformly and b = ⟨a, s⟩ + e with e ∼ Berq (η) . The goal of the problem is to recover the secret s using these m samples. 3. The following is the sparse version of the classical variant as the vectors a ’s have Hamming weight exactly σ . This is the variant that is most often used in the literature, in cryptographic constructions. n Definition 7 ( LPN=σ η,n,m ). For a secret s ∼ F2 , we are given oracle access to m samples (a, b) , where a ∼ [n] uniformly and b = ⟨a, s⟩ ⊕ e with e ∼ Ber(η) . The goal of the problem is to recover the secret σ s using these m samples.
4. The following is very similar, but is much more convenient to work with for our reductions. In this variant, the vector a is a boolean vector where each co-ordinate is chosen independently such that the expected hamming weight is σ , n Definition 8 ( LPN≈σ η,n,m ). For a secret s ∼ F2 , we are given oracle access to m samples (a, b), where a ∼ (Ber(σ/n))n and b = ⟨a, s⟩ ⊕ e with e ∼ Ber(η) . The goal of the problem is to recover the secret s using these m samples.
5. All our results will extend for general prime field Fq , and so we define these variants below. We could have completed avoided talking about LPN for F2 and introduced all definitions and proofs for Fp . The only reason we do this separately is that most work in the cryptographic literature considers LPN modulo 2 and a more general statement might be less appealing. 8
n Definition 9 ( LPN=σ q,η,n,m ). Let Xq,n,σ denote the set of all vectors in Fq , which have hamming weight n exactly σ . For a secret s ∼ Fq , we are given oracle access to m samples (a, b) , where a ∼ Xq,n,σ uniformly and b = ⟨a, s⟩ + e with e ∼ Berq (η) . The goal of the problem is to recover the secret s using these m samples. n Definition 10 ( LPN≈σ q,η,n,m ). For a secret s ∼ Fq , we are given oracle access to m samples (a, b) , where n q·σ and b = ⟨a, s⟩ + e with e ∼ Berq (η) . The goal of the problem is to recover the a ∼ Berq (q−1)·n secret s using these m samples.
Again, here, the distribution of each co-ordinate of a is chosen to get the expected hamming weight of a to be σ . An algorithm A solves Search- LPN with success probability α if, Pr [A (A, A · s + e) = s] ≥ α.
s,A,e
2.4
Decodability of LPN
In this section we prove that as long as η is small enough, for a sample (A, b = As + e) ∼ LPNq,η,n,m , the only vector v that satisfies ∥b − Av∥0 ≤ 2ηm is the true secret v = s . Our approach is to first establish that a random code A ∼ Fm×n has large distance, and then show that the noise vector e has small Hamming q weight with high probability. Combining these facts via a union bound yields the desired conclusion. The following lemma establishes the large-distance property of a random code. , and let dist(A) denote the minimum Hamming weight Lemma 7 (GV-Bound). [GRS12] Let A ∼ Fm×n q 1 of a nonzero codeword in the linear code generated by A . If η < (1 − 1/q) and m > 1−H2q (4η) · n , then 4 dist(A) ≤ 4η · m with probability at most q −n . Proof. Since the code generated by A is simply Img(A) , i.e., the image of A when treated as a linear map from Fnq to Fm q . We bound the probability that the image of A contains a non-zero vector of Hamming weight at most 4ηm . Let Bq (r, m) denote the Hamming ball of radius r in Fm q . Then, X
Pr[dist(A) ≤ 4η · m] ≤ A
Pr[u ∈ Img(A)] ,
A
u∈Bq 4ηm,m \{0}
Bq 4ηm, m , ≤ q m−n ≤ q − (1−Hq (4η))·m−n , ≤ q −n . ⊔ ⊓ The following lemma is a straightforward application of Chernoff bounds, showing that the noise vector e has small Hamming weight with overwhelming probability. m Lemma 8. For e ∼ Ber(η) , the event ∥e∥0 > 2ηm occurs with probability at most e−ηm/3 . Also, for m e ∼ Berq (η) , the event ∥e∥0 > 2ηm occurs with probability at most e−ηm/3 . 9
m Proof. It suffices to prove this statement only for e ∼ Ber(η) . The second statement follows from the fact that P r[Berq (η) = 0] ≥ P r[Ber(η) = 0] . Pm Let Xi be the indicator random variable for the event ei ̸= 0 , and set X = i=1 Xi = ∥e∥0 . Then E[X] = ηm , and the Xi ’s are independent. Applying the Chernoff bound with δ = 1 , we obtain δ2 · ηm = exp − 13 ηm . Pr[X ≥ 2ηm] = Pr[X ≥ (1 + δ)ηm] ≤ exp − 2+δ ⊔ ⊓ Combining the two statements, we get the following conclusion. 1 (1 − 1/q) and m > 1−H2q (4η) · n , the LPNq,η,n,m sample (A, b = A · s + e) is such 4 that, only the secret vector v = s satisfies ∥b − Av∥0 ≤ 2η · m , with probability 1 − q −n − e−ηm/3 .
Corollary 2. For η <
Proof. Using Lemma 7 we say can say that the distance of the code generated by the matrix A is at least 4ηm with probability at least (1 − q −n ) and using Lemma 8, ∥b − A · s∥0 < 2η · m with probability at least (1−e−ηm/3 ) . Hence by applying union bound we can conclude that with probability at least 1−q −n −e−ηm/3 , the distance of the code generated by the matrix A is at least 4ηm , and ∥b − A · s∥0 < 2η · m . Thus, with probability 1 − q −n − e−ηm/3 , for any v ̸= s , the Hamming distance of Av from As + e is more than 4ηm − 2ηm = 2ηm . The result follows. ⊔ ⊓
2.5
Decodability of Sparse- LPN
In this section we prove that for a sample (A, b = As + e) ∼ LPN≈σ q,η,n,m , the only candidate vector v whose encoding Av lies close to b is the true secret v = s . Our proof follows the same high-level strategy as in the standard LPN setting: first, we establish that a random code A has large distance; next, we argue that the noise vector e has small Hamming weight with overwhelming probability; finally, we combine these ingredients via a union bound to obtain the desired uniqueness guarantee. Since we are no longer in the uniform sampling regime, a key technical step is to lower bound the probability Pra [⟨a, u⟩ ̸= 0] for nonzero u , both in the binary and in the q -ary setting. The following lemmas establish these lower bounds, which in turn will help us conclude that the code generated by A has large distance, with high probability.We note that similar proofs appear in the literature; see, for example, [CSZ25]. Lemma 9. For a ∼ (Ber (σ/n))
n
and a non-zero vector u ∈ Fn2 such that ∥u∥0 = ℓ , we have ℓ
Pr [⟨a, u⟩ ̸= 0] = a
1 − (1 − 2σ/n) σ ≥ . 2 n
Proof. If ⟨u, a⟩ = 0 , this implies that u and a are simultaneously 1 only at even many coordinates. Hence given ∥u∥0 = ℓ , X ℓ σ i σ ℓ−i Pr [⟨u, a⟩ ̸= 0] = 1− , a i n n i is odd
ℓ
=
1 − (1 − 2σ/n) . 2 ⊔ ⊓ 10
n qσ Lemma 10. For a ∼ Berq (q−1)n and a non-zero vector u ∈ Fnq such that ∥u∥0 = ℓ , we have ℓ ! 1 qσ σ Pr [⟨a, u⟩ ̸= 0] = 1 − 1− 1− ≥ . a q (q − 1)n n Proof. Let pℓ be the probability that Pra [⟨a, u⟩ = 0] , when ∥u∥0 = ℓ . Notice that pℓ satisfies the following qσ recurrence relation where α = (q−1)n , α α pℓ = 1 − α + · pℓ−1 + · (1 − pℓ−1 ). q q Solving this recurrence with p0 = 1 gives, pℓ = (1 − α)ℓ +
1 · 1 − (1 − α)ℓ . q ⊔ ⊓
Hence we get the required claim.
Observe that as ℓ increases, Pr[⟨u, a⟩ ̸= 0] , increases as well. Hence Pr[⟨u, a⟩ ̸= 0] ≥ (σ/n) , for all non-zero vectors u , in both cases. Lemma 11. Let m ≥ 48 · n3 /σ 2 , with η < 81 , and c = (0.25 − η) . Then, with probability at least 1 , for an instance (A, b = As + e) of LPN≈σ 1 − 2(2n−1) η,n,m , the secret vector v = s is the unique vector such that, σ ∥b − Av∥0 < (η + c · ) · m. n Proof. If we sample A ∼ (Ber(σ/n))m×n and e ∼ (Ber(η))m , then for a given s ∈ Fn2 and v ∈ Fn2 such that ∥s + v∥0 = ℓ > 0 , we have E[∥(As + e) − (As)∥0 ] = E[∥e∥0 ] = ηm, Similarly, if we compute the expected distance between b = (As + e) and Av we get, E[∥(As + e) − (Av)∥0 ] m X = Pr [bi ̸= ⟨ai , v⟩] , i=1
= m · (Pr[⟨ai , s + v⟩ ̸= ei ]) , = m · (η · Pr[⟨ai , s + v⟩ = 0] + (1 − η) · Pr[⟨ai , s + v⟩ ̸= 0]) , = m · (η + (1 − 2η) · Pr[⟨ai , s + v⟩ ̸= 0]) . Since, c < (0.5 − 2η) and for p := Pr[⟨ai , s + v⟩ ̸= 0] . If ∥s + v∥0 > 0 then p ≥ σ/n using Lemma 9, which implies (1 − 2η) · p − c · nσ ≥ p/2 . Hence we bound the following probability using Chernoff, σ Pr [∥(As + e) − (Av)∥0 < (η + c · ) · m] e,A n ! 2 σ η+c· n (η + (1 − 2η) · p) · m ≤ exp − 1 − · , (η + (1 − 2η) · p) 2 ! 2 (1 − 2η) · p − c · nσ m ≤ exp − · , η + (1 − 2η) · p 2 p2 m ≤ exp − · , η + (1 − 2η) · p 8 m ≤ exp −p2 · . 8 11
If ∥s + v∥0 > 0 , then p ≥ σ/n this implies, i h σ2 m σ Pr ∥(As + e) − (Av)∥0 < (η + c · ) · m ≤ exp − 2 . e,A n 8n Now if m ≥ 48 · n3 /σ 2 , then by union bound, h i σ Pr ∃ v ̸= s | ∥(As + e) − (Av)∥0 < (η + c · ) · m n 2 σ m ≤ 2n · exp − 2 ≤ 4−n . 8n We will again use Chernoff’s bound and the fact that η < 1/8, c > 1/8 in order to get the following bound, Pr[∥e∥0 > (η + c ·
σ c2 σ 2 · m) ≤ 4−n . ) · m] < exp(− n 3ηn2
Hence, by union bound only the secret vector v = s, satisfies ∥b + Av∥0 < (η + c · nσ ) · m with probability 1 1 − 2(2n−1) . ⊔ ⊓ Following exactly the same proof as Lemma 11 along with Lemma 10 we can obtain a similar conclusion for LPN≈σ q,η,n,m . Lemma 12. Let m ≥ 48 · n3 /σ 2 · log q , with η < 81 and c = (0.25 − η) . Then, with probability at least 1 , for an instance (A, b = As + e) of LPN≈σ 1 − 2(2n−1) q,η,n,m , the secret vector v = s is the unique vector such that, 1 σ ∥b − Av∥0 < 1− ·η +c· · m. q n m×n qσ Proof. If we sample A ∼ Berq (q−1)n and e ∼ (Berq (η))m , then for a given s ∈ Fn2 and v ∈ Fnq such that ∥v − s∥0 = ℓ > 0 , we have E[∥(As + e) − (As)∥0 ] = E[∥e∥0 ] =
1−
1 q
· ηm,
Let u = (v − s) ̸= 0 , now if we compute the expected distance between b = (As + e) and Av we get, E[∥(As + e) − (Av)∥0 ], m X = Pr [bi ̸= ⟨ai , v⟩] , i=1
= m · (Pr[⟨ai , u⟩ ̸= ei ]) , 1 η =m· 1− η · Pr[⟨ai , u⟩ = 0] + 1 − · Pr[⟨ai , u⟩ ̸= 0] , q q 1 1 ≥m· 1− ·η+ 1−2 1− η · Pr[⟨ai , u⟩ ̸= 0] . q q Using Lemma 10 we get, E[∥(As + e) − (Av)∥0 ] ≥ m ·
1−
1 q
1 s ·η+ 1−2 1− η · . q n
From this point, the proof proceeds analogously to Lemma 11. The only difference is that, when applying the union bound over all vectors, we now sum over q n possibilities instead of 2n , introducing an additional factor of log q in the lower bound for m . ⊔ ⊓ 12
3 Hardness self-amplification from [HS23] One important conclusion from [HS23] is that, the simple direct product reduction is a powerful tool for hardness amplification. In this section, we provide a combinatorial exposition of some of their results. We emphasise that we do not claim any originality in the results. 3.1
Direct Product Reduction
Let (f, µ) be a distributional problem where f : X → {0, 1}∗ is a function defined on domain X = supp(µ) , µ is the input distribution. The k -wise direct product of (f, µ) is the distributional problem (f ×k , µ×k ) defined as follows, for any x1 , . . . , xk ∈ X : f ×k (x1 , . . . , xk ) = (f (x1 ), . . . , f (xk )) , µ×k (x1 , . . . , xk ) =
k Y
µ(xi ) .
i=1
In other words, µ×k is simply the product distribution of k independent copies of µ , and input space of (f ×k , µ×k ) is Y := X k . Suppose we are given oracle access to a solver O for (f ×k , µ×k ) . We define the direct product reduction O R , which is a randomized reduction that uses O to solve (f, µ) as follows: Reduction RO On input x ∈ X and internal randomness r : 1. For all j ∈ [k], sample xj ∼ µ independently. 2. Sample i ∈ [k] uniformly at random. 3. Replace the sample xi , with our input x and form the tuple, y = (x1 , . . . , xi−1 , x, xi+1 , . . . , xk ) ∈ Y. 4. Query the oracle O on input y . 5. Let (z1 , z2 , · · · , zi , · · · zk ) be the output of the O , return zi as the solution for x .
3.2
Hardness Amplification from Direct Product Reduction
Lemma 13. Let (f, µ) be a distributional problem. For ε, δ, c ∈ [0, 1] and positive integer k satisfying that 2 exp(−kc2 δ/8) ≤ cε . Let O be an oracle that solves its k -wise direct product (f ×k , µ×k ) with probability ε over its input distribution internal randomness. We have h i Pr Pr RO (x, r) = f (x) ≥ (1 − c)ε ≥ 1 − δ .
x∼µ
r
Proof. Set c′ := c/2, ε′ := cε/2 . We use G(x, r) to denote the instance y ∈ Y generated in the reduction RO (x, r) . Define HX := {x : Prr RO (x, r) = f (x) ≤ (1 − c)ε} to be the set of hard instances from X . Set δ1 := Pr [x ∈ HX ] . x∼µ
Note that it suffices to prove that δ1 < δ and let us assume towards contradiction that δ1 ≥ δ . We start with following claim, with the intuition that knowing y does not reveal too much information about whether x ∈ HX , since the reduction is “mixing” especially when k is large: 13
Claim.
Pr
′
Pr [x ∈ HX |G(x, r) = y] ≤ (1 − c )δ1 ≤ ε′ .
x∼µ,r
y∼µ×k
Proof. For any fixed y = (x1 , . . . , xk ) , notice that Pr [x ∈ HX |G(x, r) = y] =
x∼µ,r
k X j=1
Pr [i = j] · 1xj ∈HX
i∼[k] k
=
1X 1x ∈H . k j=1 j X
The claim follows from applying Chernoff-Hoeffding’s inequality by treating 1xj ∈HX as a random variable about y with expectation δ1 . ⋄ ⊔ ⊓ Next, set w(y) := PrO [O(y) = f (y)] . By our assumption on O , we have X Pr [O(y) = f (y)] = µ×k (y)w(y) ≥ ε . y∼µ×k ,O
y∈Y
Set SY := {y ∈ Y : Prx∼µ,r [x ∈ HX |G(x, r) = y] ≤ (1 − c′ )δ1 } be the set of instances from Y that has relatively small contributions towards solving instances in HX . Now consider two ways of evaluating the probability Pr [x ∈ HX , RO (x, r) = f (x)]
x∼µ,r
. Pr [x ∈ HX , RO (x, r) = f (x)] X = µ×k (y) Pr [x ∈ HX |G(x, r) = y] Pr[O(y) = f (y)] x∼µ,r
x∼µ,r
y∈Y
≥
X
O
µ×k (y) · Pr [x ∈ HX |G(x, r) = y] · w(y) x∼µ,r
y∈Y \SY
≥(1 − c′ )δ1
X
µ×k (y) · w(y)
y∈Y \SY
≥(1 − c′ )δ1
X
µ×k (y)w(y) −
y∈Y ′
X
µ×k (y)w(y)
y∈SY ′
′
≥(1 − c )δ1 (ε − ε ) = (1 − c )(1 − ε′ /ε)εδ1 . On the other hand, we have
Pr [x ∈ HX , RO (x, r) = f (x)]
x∼µ,r
≤(1 − c)ε Pr[x ∈ HX ] ≤(1 − c)εδ1 . Combining the two inequalities we have (1 − c′ )(1 − ε′ /ε) ≤ (1 − c) which is a contradiction by our choices of c′ and ε′ . ⊔ ⊓ 14
Theorem 1. For every δ, ε , γ > 0 and k ≥ 32 δ log
4 ε
if there exists,
– An algorithm A that takes input y = (x1 , x2 , · · · , xk ) , runs in time T (|y|) and solves the distributional problem (f ×k , µk ) with success probability ε . – An algorithm B , which takes (x, z) as input, runs in time t(|x|) and verifies if z = f (x) , for all but ϑ fraction of x . , for solving the distributional Then there exists an algorithm A′ , running in time O log γ1 · T (kn)+t(n) ε problem (f, µ) , with success probability (1 − δ − γ − ϑ) . Proof. We will use the following algorithm A′ in order to solve (f, µ) , An Algorithm A′ for (f, µ) Given an input x, we perform the following steps, for ℓ =
l
2 log(γ −1 ) ε
m
iterations:
1. Run the reduction RO on x , where the oracle O is instantiated by the algorithm A . 2. Use B to verify whether RA (x) = f (x) , if it is same as f (x) , then we output it and break out of the loop. 4 Using Lemma 13 with c = 0.5 we get, if k ≥ 32 δ log ε then in one single iteration, for (1 − δ) fraction of x ∼ µ , we can obtain f (x) with probability ≥ 0.5ε . Moreover, for a (1 − ϑ) fraction of x ∼ µ, the verifier succeeds in checking a proposed solution. Hence using union bound, for (1 − δ − ϑ) fraction of x , with −1 probability 1−(1−0.5ε)2 log(γ )/ε ≥ 1−γ , we can obtain the solution for x from the ℓ iterations. Using union bound, the overall success probability of the above algorithm is at least (1−δ −γ −ϑ) . Since in every iteration we make only one call to A , the running time is clearly O(ℓ·(T (kn)+t(n))) = O(log(γ −1 )ε−1 (T (kn)+t(n))) . ⊔ ⊓
4 Hardness Self Amplification for Search-LPN In this section, we prove that direct-product self-reductions amplify average-case hardness for the standard LPN . Concretely, for any ε, δ > 0 and k ∈ Ω 1δ log 1ε , an algorithm that solves LPNq in n′ dimensions with noise rate η ′ and success probability ε can be turned into an algorithm that solves LPNq in n = n′ /k dimensions with base noise rate η > η ′ /k , achieving success probability at least 1 − 2−Ω(n) on a 1 − δ fraction of instances. Theorem 2. Let m, n, k be positive integers with m > (1−H2q (4η)) · n . Let ε > 0 , δ > q −Ω(n) , η ∈ (0, 1/8) , 8 ϵ n ηm/3 and let 192 . There is a poly(n, k, 1/δ, 1/ε) -time reduction that, given an δ · log ε < k < 8 · min q , e oracle that succeeds with probability ε for LPNq,(1−(1−η)k ),kn,m , solves LPNq,η,n,m with probability 1 − δ . Let ϕk (η) = 1 − (1 − η)k . We first show that a k -fold product of small LPNq instances can be combined into a single larger LPNq instance by concatenating the challenge matrices and summing the noisy responses, thereby matching the transformed noise rate ϕk (η) . After establishing this reduction, we will apply the algorithm in Theorem 1 in order to conclude the proof of Theorem 2. Lemma 14. The product distributional problem (Search-LPNq,η,n,m)k consists of k independent samples from LPNq,η,n,m , (A1 , b1 = A1 · s1 + e1 ), . . . , (Ak , bk = Ak · sk + ek ) , and the goal is to recover (s1 , · · · , sk ) . Suppose there exists a T (kn) -time algorithm A that solves Search- LPNq,ϕk (η),kn,m with success probability ε . Then there exists an algorithm à , running in time T (kn) , which solves (Search-LPNq,η,n,m )k with success probability ε . 15
Proof. Given an instance y = (A1 , b1 = A1 · s1 + e1 ), . . . , (Ak , bk = Ak · sk + ek ) of (Search-LPNq,η,n,m )k , we define (A∗ , b∗ ) as follows, ∗
A = A1 A2 . . . A k ,
∗
b =
k X
bi .
i=1
Denote s∗ = (s1 , s2 , . . . , sk ) and d = nk . Notice that A∗ is uniformly distributed over Fm×d and s∗ q P ∗ ∗ ∗ ∗ is uniformly distributed over Fdq . Moreover, let e∗ = i∈[k] ei , then we have b = A s + e . Since ∗ m e is the sum of k independent random (Berq (η)) , by Lemma 4 it is exmvariables with distribution m actly distributed as Berq 1 − (1 − η)k = (Berq (ϕk (η))) . So we get A∗ ∼ Fm×d , s∗ ∼ Fdq , e∗ ∼ q m ∗ ∗ ∗ ∗ ∗ ∗ (Berq (ϕk (η))) , b = A ·s +e . Thus, we have constructed an instance (A , b ) of Search-LPNq,ϕk (η),kn,m . Running A on this instance yields s∗ with success probability ε . Finally, note that s∗ = (s1 , . . . , sk ) is precisely the solution to the original instance y as well. Therefore, we obtain an algorithm Ae that solves (Search-LPNq,η,n,m )k with success probability ε in time T (kn) . ⊔ ⊓ Proof (Proof of Theorem 2). By Lemma 14, the assumed T (kn) -time solver A for LPNq,ϕk (η),kn,m can be transformed into a T (kn) -time algorithm à that solves the product problem (Search-LPNq,η,n,m )k with success probability ε . Let µ be the input distribution of LPNq,η,n,m ( . In order to apply Theorem 1, we define the function f : s there exists a unique s such that ∥b − As∥0 ≤ 2η · m n Fm×n × Fm . q q → Fq ∪ {⊥} as follows: f (A, b) = ⊥ otherwise Notice that à also solves (f ×k , µ×k ) with success probability at least ε − k q −n + e−ηm/3 ≥ ε/2 . In particular, the extra error comes from the (non-decodable) event stipulated by Corollary 2, which happens with probability at most q −n + e−ηm/3 for each small instance. In particular, here is a simple verification algorithm (required for Theorem 1) for (f, µ) : accept if and only if ∥b − As∥0 ≤ 2η · m . Now applying Theorem 1 with the following parameters (δ ′ = δ/3, γ ′ = δ/3, ϑ′ = q −n + e−ηm/3 ) , any T (kn) -time solver for (f ×k , µ×k ) with success probability ε/2 can be converted into an algorithm A′ for (f, µ) with success probability 1 − 2δ/3 − (q −n + e−ηm/3 ) . Lastly, A′ also solves LPNq,η,n,m with the same success probability, except for a (q −n + e−ηm/3 ) fraction of (not uniquely decodable) instances. The resulting algorithm runs in time O((1/ε) log(1/δ) · T (kn)) and succeeds with probability at least 1 − 2δ/3 − 2 q −n + e−ηm/3 > 1 − δ over the input distribution and its internal randomness as desired. ⊔ ⊓ Using the above theorem with q = 2 , we obtain the following result for the binary case LPNη,n,m . Corollary 3. Let m, n, k be positive integers with m > (1−H22 (4η)) · n . Let ε > 0 , δ > 2−Ω(n) , η ∈ (0, 1/8) , 8 ϵ n ηm/3 . There is a poly(n, k, 1/δ, 1/ε) -time reduction that, given an and let 192 δ · log ε < k < 8 · min 2 , e oracle that solves LPN 1−(1−2η)k with success probability ε , solves LPNη,n,m with probability 1 − δ . 2
,nk,m
Proof. Since LPN2,η′ ,n,m is identical to LPNη′ /2,n,m , substituting η ′ = 2η in the base instance and η ′ = 1 − (1 − 2η)k in the scaled instance gives the claimed binary statement.
5 Hardness of Sparse Search-LPN 5.1
Hardness Self Amplification of Search- LPN≈σ η,n,m
We will again follow the same template as Section 4 in this section in order to prove hardness self amplification result about LPN≈σ q,η,n,m . 16
Theorem 3. Let m, n, k, σ bepositive integers with m ≥ 48 · (n3 log q/σ 2 ) . Let ε > 0, δ > 6(2−(2n−1) ), η ∈ 8 (0, 1/8) , and let 192 < k < 2(2n−2) · ε . There is a poly(n, k, 1/δ, 1/ϵ) -time reduction that, given an δ · log ϵ ≈σ oracle which succeeds with probability ε for LPN≈kσ q,(1−(1−η)k ),kn,m , solves LPNq,η,n,m with success probability 1 − δ. ≈kσ k Let ϕk (η) = 1 − (1 − η)k . We will now reduce (Search-LPN≈σ q,η,n,m ) to Search-LPNq,ϕk (η),kn,m . After establishing this reduction we will use the algorithm in Theorem 1 in order to get Theorem 3, k Lemma 15. The product distributional problem (Search-LPN≈σ q,η,n,m ) consists of k independent samples from ≈σ LPNq,η,n,m , (A1 , b1 = A1 · s1 + e1 ), . . . , (Ak , bk = Ak · sk + ek ) ,
and the goal is to recover (s1 , · · · , sk ) . Suppose there exists a T (kn) -time algorithm A that solves SearchLPN≈kσ q,ϕk (η),kn,m with success probability ε . k Then there exists an algorithm à , running in time T (kn) which solves (Search-LPN≈σ q,η,n,m ) with success probability ε .
Proof. Given an instance, y = (A1 , b1 = A1 · s1 + e1 ), . . . , (Ak , bk = Ak · sk + ek ) , ∗ ∗ k of (Search-LPN≈σ q,η,n,m ) , we define (A , b ) as follows,
A∗ = A1 A2 . . . A k ,
b∗ =
k X
bi .
i=1 m×d Denote s∗ = (s1 , s2 , . . . , sk ) and d = nk . Notice that A∗ is exactly distributed as (Berq (qσ/(q = P −1)n)) (Berq (kqσ/(q − 1)d))m×d and s∗ is uniformly distributed over Fdq . Moreover, let e∗ = i∈[k] ei , then we have b∗ = A∗ s∗ + e∗ . Since e∗ is the sum of k independent random variables with distribution (Berq (η))m , m k m by Lemma 4 it is exactly distributed as Berq 1 − (1 − η) = (Berq (ϕk (η))) . So we get,
A∗ ∼ Berq
kqσ (q − 1)d
m×d
m
, s∗ ∼ Fd2 , e∗ ∼ (Berq (ϕk (η))) , b∗ = A∗ · s∗ + e∗ .
Thus, we have constructed an instance (A∗ , b∗ ) of Search-LPN≈kσ q,ϕk (η),kn,m . Running A on this instance yields s∗ with success probability ε . Finally, note that s∗ = (s1 , . . . , sk ) is precisely the solution to the k original instance y as well. Therefore, we obtain an algorithm Ae that solves (Search-LPN≈σ q,η,n,m ) with success probability ε in time T (kn) . ⊔ ⊓ Proof (Proof of Theorem 3). By Lemma 15, the assumed T (kn) -time solver A for LPN≈kσ q,ϕk (η),kn,m can be k transformed into a T (kn) -time algorithm à that solves the product problem (Search-LPN≈σ q,η,n,m ) with success probability ε . Let µ be the input distribution of LPN≈σ q,η,n,m . In order to apply Theorem 1, we define the function m n f : Fm×n × F → F ∪ {⊥} as follows: q q q ( s ∃ unique s with ∥b − As∥0 ≤ (η(1 − 1/q) + (0.25 − η) nσ ) · m f (A, b) = . ⊥ otherwise Notice that à also solves (f ×k , µ×k ) with success probability at least ε − k(2−(2n−1) ) . In particular, the extra error comes from the (non-decodable) event stipulated by Lemma 12, which happens with probability at most 2−(2n−1) for each small instance. 17
In particular, there is a very simple verification algorithm (as required for Theorem 1) for (f, µ) : accept if and only if ∥b − As∥0 ≤ (η(1 − 1/q) + (0.25 − η) nσ ) · m . Now applying Theorem 1 with the following parameters (δ ′ = δ/3, γ ′ = δ/3, ϑ′ = 2−(2n−1) ) , any T (kn) -time solver for (f ×k , µ×k )) with success probability ε − k(2−(2n−1) ) > ε/2 can be converted into an algorithm A′ for (f, µ) with success probability 1 − 2δ/3 − (2−(2n−1) ) . Lastly, A′ also solves LPN≈σ q,η,n,m with the same success probability, except for a (2−(2n−1) ) fraction of (not uniquely decodable) instances. The resulting algorithm runs in time O((1/ε) log(1/δ) · T (kn)) and succeeds with probability at least 1 − 2δ/3 − 2(2−(2n−1) ) > 1 − δ over the input distribution and its internal randomness as desired. ⊔ ⊓ Using the above theorem with q = 2 we get the following corollary. Corollary 4. Let m, n, k, σ be positive integers with m ≥ 48·(n3 /σ 2 ) . Let ε > 0, δ > 6(2−(2n−1) ), η ∈ (0, 1/8) , 8 192 and let δ · log ϵ < k < 2(2n−2) · ε . There is a poly(n, k, 1/δ, 1/ϵ) -time reduction that, given an oracle , solves LPN≈σ which succeeds with probability ε for LPN≈kσ 1−(1−2η)k η,n,m with success probability 1 − δ . ,kn,m
2
≈σ ′ ′ Proof. Since LPN≈σ 2,η ′ ,n,m is identical to LPNη ′ /2,n,m , substituting η = 2η in the base instance and η = k 1 − (1 − 2η) in the scaled instance gives the claimed binary statement. ⊔ ⊓
5.2
√ to Search- LPN=σ Reduction from Search-LPN≈σ q,η,n,m q,η,n,3 σ·m
√ =σ √ In this section we will give a reduction from LPN≈σ q,η,n,3 σ·m to LPNq,η,n,m . We set M := 3 σ · m . m×(n+1) ∪ In particular, given an instance (A, b = A · s + e) of LPN≈σ q,η,n,M , we will output R (A, b) ∈ F =σ {⊥} , such that distribution of R (A, b) is statistically close to the input distribution of LPNq,η,n,m .
If R (A, b) ̸= ⊥ , then let R (A, b) be (A′ , b′ ) ′ ′ ′ Moreover, the secret s for the original LPN≈σ q,η,n,M instance will be the same as the secret s of (A , b ) .
Now, if an algorithm A can solve LPN=σ q,η,n,m with success probability α then given the above reduction it can solve LPN≈σ with success probability α − κ , where κ is the distance between the distribution q,η,n,M induced by the reduction, and the input distribution of LPN=σ q,η,n,m . The Reduction Given an instance of LPN≈σ q,η,n,M as,
a1 b1 a2 b2 A = .. , b = .. , . . aM
bM
If the number of rows a with hamming weight exactly σ is strictly less than m then we output ⊥ . Otherwise, let [ai1 , ai2 · · · aim ] be the first m rows of A with hamming weight exactly σ . The reduction outputs ai1 bi 1 ai2 bi2 ′ A = .. , b′ = .. . . . aim
bim
To establish that the distribution of (A′ , b′ ) is statistically close to that of the instances of LPN=σ q,η,n,m , we first analyze the distribution of A′ . We claim that the distribution of A′ is statistically close to the uniform 18
m . Conditioned on the event that there are at least m rows with Hamming weight distribution over [n] σ exactly σ (i.e., that the reduction doesn’t output ⊥ ), the distribution of A′ , b′ is distributed as LPN=σ q,η,n,m with the same secret vector s . Let β be the probability that A has strictly less than m rows with Hamming weight σ , i.e., that R (A, b) = ⊥ . Thus, if the LPN=σ q,η,n,m oracle succeeds in finding the secret vector s with probability ε , then the reduction is successful with probability Pr[R (A, b) ̸= ⊥] · Pr[ Reduction outputs s|R (A, b) ̸= ⊥] = Pr[R (A, b) ̸= ⊥] · Pr[LPN=σ q,η,n,m oracle outputs s] = (1 − β) · ε ≥ε−β . Thus, to prove correctness of our reduction, we give an upper bound on β . √ Lemma 16. Let q be a prime power, and let σ, n, m ∈ N with M = ⌈3 σ m⌉ and m ≥ 1200n . Let a1 , . . . , aM be sampled independently as n qσ . ai ∼ Berq (q − 1)n Then, with probability at least 1 − 21n , there exist at least m rows among the ai ’s whose Hamming weight is exactly σ . Proof. Let Xi be the indicator random variable for the event that ai has Hamming weight exactly σ . Put α :=
qσ . (q − 1)n
For a single coordinate Y ∼ Berq (α) , we have Pr[Y = 0] = (1 − α) +
α , q
Pr[Y = v] =
Hence Pr[Y ̸= 0] =
α q
for every v ∈ Fq \ {0}.
q−1 σ α= . q n
Therefore the Hamming weight of ai is distributed as Bin(n, σ/n) , and so n−σ σ σ n−σ n Pr[Xi = 1] = . σ n n Using Corollary 1, we get n−σ n σ σ n−σ Pr[Xi = 1] = σ n n σ σ 1 nn ≥p · · n 8σ(1 − nσ ) σ σ (n − σ)n−σ 1 1 =p ≥√ . 8σ(1 − nσ ) 8σ Now let, X :=
PM
i=1 Xi which implies that E[X] ≥
M M m≤ √ = √ = 3 σ 9σ
r
n−σ n
n−σ
√ √M . Since M = ⌈3 σ m⌉ , we have 8σ
8 M ·√ ≤ 9 8σ
19
r
8 · E[X]. 9
Thus, setting δ := 1 −
q
8 9 , we get m ≤ (1 − δ) · E[X]. By Chernoff’s bound,
Pr[X < m] ≤ Pr[X < (1 − δ)E[X]] 2 δ E[X] ≤ exp − 2 2 δ M ≤ exp − √ 2 8σ 3δ 2 m . ≤ exp − √ 4 2 Since m ≥ 1200n , the final expression is at most e−n , and hence at most 2−n . Therefore, with probability at least 1 − 2−n , there are at least m rows among the ai ’s whose Hamming weight is exactly σ . This gives us the following theorem, √ Theorem 4. Let σ, n, m ∈ N, M = ⌈3 σ m⌉ , and m ≥ 1200n . If there exists an algorithm A running in time ≈σ T (n) , that solves LPN=σ q,η,n,m with success probability ε , then it can solve LPNq,η,n,M with success probability 1 ε − 2n in time T (n) . Following exactly the same proof as above we obtain the following corollary for the binary field, √ Corollary 5. Let σ, n, m ∈ N, M = ⌈3 σ m⌉ , and m ≥ 1200n . If there exists an algorithm A running in time ≈σ T (n) , that solves LPN=σ η,n,m with success probability ε , then it can solve LPNη,n,M with success probability 1 ε − 2n in time T (n) . 5.3
Putting Everything Together
By combining the reductions from Corollary 5 and Corollary 4, we have the following theorem: √ Theorem 5. Let m, n, k, σ be positive integers with m ≥ max(48 · (n3 /σ 2 ), 1200n) and set M = ⌈3 σ m⌉ . 16 Let ε > 0, δ > 6(2−(2n−1) ), η ∈ (0, 1/8) , and k satisfies 192 < k < 2(2n−2) · ε . There is a δ · log ϵ =kσ poly(n, k, 1/δ, 1/ϵ) -time reduction that, given an oracle for LPN 1−(1−2η)k that succeeds with probability 2
,kn,m
ε , solves LPN≈σ η,n,M with success probability 1 − δ . Similarly by combining the reductions from Theorem 4 and Theorem 3 we can get the same theorem and conclusions for LPN=σ q,η,n,m . 3 √ Theorem 6. Let m, n, k, σ be positive integers with m ≥ max( 48nσ2log q , 1200n) and set M = ⌈3 σ m⌉ . 16 Let ε > 0, δ > 6(2−(2n−1) ), η ∈ (0, 1/8) , and k satisfies 192 < k < 2(2n−2) · ε . There is a δ · log ϵ =kσ poly(n, k, 1/δ, 1/ϵ) -time reduction that, given an oracle for LPNq,(1−(1−η)k ),kn,m that succeeds with probability ε , solves LPN≈σ q,η,n,M with success probability 1 − δ .
References ABW10.
Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC ’10, page 171–180, New York, NY, USA, 2010. Association for Computing Machinery. 1
20
AIK08.
Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. On pseudorandom generators with linear stretch in nc0. Comput. Complex., 17(1):38–69, April 2008. 1 Ale03. M. Alekhnovich. More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 298–307, 2003. 1 BCCD23. Maxime Bombar, Geoffroy Couteau, Alain Couvreur, and Clément Ducros. Correlated pseudorandomness from the hardness of quasi-abelian decoding. In Annual International Cryptology Conference, pages 567– 601. Springer, 2023. 1 BCG + 20. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Correlated pseudorandom functions from variable-density lpn. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1069–1080. IEEE, 2020. 1 BCG + 22. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, and Peter Scholl. Correlated pseudorandomness from expand-accumulate codes. In Annual International Cryptology Conference, pages 603–633. Springer, 2022. 1 BCGI18. Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. Compressing vector ole. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS ’18, page 896–912, New York, NY, USA, 2018. Association for Computing Machinery. 1 BFKL93. Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. Cryptographic primitives based on hard learning problems. In CRYPTO ’93, volume 773 of LNCS, pages 278–291. Springer, 1993. 1 BKW03. Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM, 50(4):506–519, 2003. 1 BLP + 13. Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardness of learning with errors. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 575–584, 2013. 2 BLVW19. Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, and Daniel Wichs. Worst-case hardness for lpn and cryptographic hashing via code smoothing. In Annual international conference on the theory and applications of cryptographic techniques, pages 619–635. Springer, 2019. 2 CRR21. Geoffroy Couteau, Peter Rindal, and Srinivasan Raghuraman. Silver: silent vole and oblivious transfer from hardness of decoding structured ldpc codes. In Annual International Cryptology Conference, pages 502–534. Springer, 2021. 1 CSZ25. Xue Chen, Wenxuan Shu, and Zhaienhe Zhou. Algorithms for sparse lpn and lspn against low-noise (extended abstract). In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 1091–1093. PMLR, 30 Jun–04 Jul 2025. 10 DIJL23. Quang Dao, Yuval Ishai, Aayush Jain, and Huijia Lin. Multi-party homomorphic secret sharing and sublinear mpc from sparse lpn. In Annual International Cryptology Conference, pages 315–348. Springer, 2023. 1 DMQN12. Nico Döttling, Jörn Müller-Quade, and Anderson C. A. Nascimento. Ind-cca secure cryptography based on a variant of the lpn problem. In Proceedings of the 18th International Conference on The Theory and Application of Cryptology and Information Security, ASIACRYPT’12, page 485–503, Berlin, Heidelberg, 2012. Springer-Verlag. 1 DR25. Thomas Debris-Alazard and Nicolas Resch. Worst and average case hardness of decoding via smoothing bounds. In IACR International Conference on Public-Key Cryptography, pages 363–392. Springer, 2025. 2 GMPW20. Nicholas Genise, Daniele Micciancio, Chris Peikert, and Michael Walter. Improved discrete gaussian and subgaussian analysis for lattice cryptography. In IACR International Conference on Public-Key Cryptography, pages 623–651. Springer, 2020. 4 GRS08. Henri Gilbert, Matthew J. B. Robshaw, and Yannick Seurin. How to encrypt with the lpn problem. In International Colloquium on Automata, Languages and Programming, 2008. 1 GRS12. Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory. 2012. 5, 9 HB01. Nicholas J. Hopper and Manuel Blum. Secure human identification protocols. In Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, ASIACRYPT ’01, page 52–66, Berlin, Heidelberg, 2001. Springer-Verlag. 1 HKL + 12. Stefan Heyse, Eike Kiltz, Vadim Lyubashevsky, Christof Paar, and Krzysztof Pietrzak. Lapin: An efficient authentication protocol based on ring-lpn. In FSE, volume 7549, pages 346–365. Springer, 2012. 1 HS23. Shuichi Hirahara and Nobutaka Shimizu. Hardness self-amplification: Simplified, optimized, and unified. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 70–83, New York, NY, USA, 2023. Association for Computing Machinery. 1, 2, 3, 4, 5, 13
21
IKOS08.
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography with constant computational overhead. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, page 433–442, New York, NY, USA, 2008. Association for Computing Machinery. 1 JKPT12. Abhishek Jain, Stephan Krenn, Krzysztof Pietrzak, and Aris Tentes. Commitments and efficient zeroknowledge proofs from learning parity with noise. In Xiaoyun Wang and Kazue Sako, editors, Advances in Cryptology – ASIACRYPT 2012, pages 663–680, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. 1 JLS21. Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, pages 60–73, 2021. 1 JLS22. Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from lpn over f p, dlin, and prgs in nc 0. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 670–699. Springer, 2022. 1 JW05. Ari Juels and Stephen A. Weis. Authenticating pervasive devices with human protocols. In Proceedings of the 25th Annual International Conference on Advances in Cryptology, CRYPTO’05, page 293–308, Berlin, Heidelberg, 2005. Springer-Verlag. 1 KMP14. Eike Kiltz, Daniel Masny, and Krzysztof Pietrzak. Simple chosen-ciphertext security from low-noise lpn. In Hugo Krawczyk, editor, Public-Key Cryptography – PKC 2014, pages 1–18, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. 1 Pei09. Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 333–342, 2009. 2 Pie12. Krzysztof Pietrzak. Cryptography from learning parity with noise. In Conference on Current Trends in Theory and Practice of Informatics, 2012. 1 Reg05. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, page 84–93, New York, NY, USA, 2005. Association for Computing Machinery. 2 Rob55. Herbert E. Robbins. A remark on stirling’s formula. American Mathematical Monthly, 62:402–405, 1955. 8 RRT23. Srinivasan Raghuraman, Peter Rindal, and Titouan Tanguy. Expand-convolute codes for pseudorandom correlation generators from lpn. In Annual International Cryptology Conference, pages 602–632. Springer, 2023. 1 YGJ + 18. Zhimin Yu, Chong-Zhi Gao, Zhengjun Jing, Brij Bhooshan Gupta, and Qiuru Cai. A practical public key encryption scheme based on learning parity with noise. IEEE Access, 6:31918–31923, 2018. 1 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, pages 473–501, Cham, 2021. Springer International Publishing. 2 YZW + 19. Yu Yu, Jiang Zhang, Jian Weng, Chun Guo, and Xiangxue Li. Collision resistant hashing from subexponential learning parity with noise. In 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, page 3–24, Berlin, Heidelberg, 2019. Springer-Verlag. 1
A Proof of Corollary 1 Proof (Proof of Corollary 1). Since n n! = . s s!(n − s)! For the lower bound, we use the lower bound for n! and the upper bounds for s! and (n − s)! from Lemma 6 to obtain, √ 1 1 n 2π n n+ 2 e−n+ 12n+1 . ≥ √ √ 1 1 1 1 s 2π s s+ 2 e−s+ 12s 2π (n − s) n−s+ 2 e−(n−s)+ 12(n−s) 22
Canceling the common e−n with e−k e−(n−k) and collecting powers we get, n 1 nn 1 1 1 ≥ p · · exp , − − s 12n + 1 12s 12(n − s) 2πs(1 − ns ) ss (n − s) n−s 1 1 nn nn −1/6 p · e ≥ ; ≥ p · · 2πs(1 − ns ) ss (n − s) n−s 8s(1 − ns ) ss (n − s) n−s which yields the stated lower bound. For the upper bound, we use the upper bound for n! and the lower bounds for s! and (n − s)! from Lemma 6 to obtain, √ 1 1 n 2π n n+ 2 e−n+ 12n , ≤ √ √ 1 1 1 1 s 2π s s+ 2 e−s+ 12s+1 2π (n − s) n−s+ 2 e−(n−s)+ 12(n−s)+1 and again after cancellations and using the fact
1 1 1 12n − 12s+1 − 12(n−s)+1
< 0 we get,
1 n 1 nn 1 1 · s · exp − − , ≤ p s n−s 12n 12s + 1 12(n − s) + 1 s 2πs(1 − n ) s (n − s) ≤ p
1 nn · · 2πs(1 − ns ) ss (n − s) n−s
23