Towards Worst-case Hardness for Low-Noise LPN Divesh Aggarwal∗
Rishav Gupta†
Hai Hoang Nguyen‡
Kel Zin Tan§
Prashant Nalini Vasudevan¶ National University of Singapore
arXiv:2606.05834v1 [cs.CR] 4 Jun 2026
June 5, 2026
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/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 F2 , 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, our reduction yields LPN hardness in the parameter regime required for Alekhnovich’s construction of publickey encryption [Ale03], a regime that was previously inaccessible via worst-case reductions.
∗ † ‡ § ¶
Email: [email protected] Email: [email protected] Email: [email protected] Email: [email protected] Email: [email protected]
i
Contents 1 Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Paper Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 2 4 4
2 Preliminaries
5
3 Average-Case Reduction 6 3.1 Large Advantage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Small Advantage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4 Corollaries
12
5 Acknowledgements
14
A Deferred Proof
17
ii
1
Introduction
Learning Parity with Noise (LPN) [BFKL94] is essentially the problem of decoding random noisy codewords of a random linear code. An instance consists of a uniformly random matrix A ← Fm×n 2 n is a uniformly random vector and e ← Ber(η)m is a vector and a vector A·s+e ∈ Fm , where s ← F 2 2 of Bernoulli variables, where η ∈ (0, 1/2) is called the noise rate. In the Search LPN problem, the task is to recover s given (A, As + e). In the Decision LPN problem, the task is to distinguish this distribution from (A, b), where b is an independent uniformly random vector in Fm 2 . These variants are known to be equivalent [AIK07, MM11]. The LPN problem has been of significant consequence to cryptography since its first consideration by Blum et al. [BFKL94]. It is one of the few known sources of secure Public-Key Encryption (PKE) [Ale03, YZ16], and has been used to construct various advanced cryptographic primitives (see, for instance, the survey by Pietrzak [Pie12]). It may be interpreted as the problem of solving a system of noisy linear equations, and for large enough η, worst-case versions of this problem are known to be NP-hard [AK11]. The best algorithms we have for LPN run in time 2O(η·n) for any non-trivial m [Pra62, Ste89, Dum91, MMT11, BJMM12, MO15, BM17, BM18, DEEK24], or in time 2O(n/ log n) if m > 2Ω(n/ log n) [BKW03], or 2O(n/ log log n) if m > n1+Ω(1) [Lyu05]. In many ways, LPN is similar to its analogue in the Euclidean metric, the Learning With Errors (LWE) problem [Reg09]. One notable difference, however, is that the (average-case) hardness of the LWE problem is supported by the worst-case hardness of lattice problems [Reg09, Pei09], leading to a construction of PKE and other primitives from the worst-case hardness of these problems. With LPN, the worst-case to average-case reductions we have are much more limited. Known Reductions for LPN. The only known method for reducing from the plausible worstcase hardness of any problem to LPN is that of Brakerski et al. [BLVW19]. Their reduction is from a worst-case version of the LPN problem itself, called the Nearest Codeword Problem (NCP). Here, and vector As + e ∈ Fm given a matrix A ∈ Fm×n 2 for some e guaranteed to have Hamming weight 2 at most η · m, the problem is to recover s. They show that the worst-case hardness of NCP (with some minor restrictions) with noise rate η = O(log2 n/n) implies the average-case hardness of LPN with noise rate (1/2 − 1/poly(n)). With additional careful analysis, Yu and Zhang [YZ21] extend this reduction to sub-exponential1/2 time algorithms. For example, they show that if NCP with noise rate η = O(n−1/2 ) and m = 2Ω(n ) 1/2 is worst-case hard for algorithms running in time 2O(n ) , then LPN with constant noise-rate and similar values of m is also hard for such algorithms. They also point out that the hardness of LWE with certain noise parameters implies hardness of an analogue of LPN over large fields with noise rate close to 1. Apart from worst-case-to-average-case reductions, hardness amplification results are also known for LPN [AGZ26]. Roughly speaking, these results show that an algorithm solving LPN with secret length kn and noise rate kη with success probability ε can be used to solve LPN with secret length n and noise rate η with success probability at least 1 − δ, where k = Θ 1δ log 1ε . Limits of Known Reductions. The aforementioned results are already quite remarkable as they imply the possibility of symmetric-key cryptography based on worst-case hardness assumptions. Unfortunately, they fall well short of providing the hardness of LPN required for public-key applications, which is hardness at noise rate O(n−1/2 ) [Ale03] against polynomial-time algorithms,
1
1/2
or at constant noise rate against 2ω(n ) -time algorithms [YZ16]. Further, the worst-case hardness assumptions in their hypotheses are quite strong. Recall that [BLVW19] requires hardness of NCP with a noise rate of O(log2 n/n). This is only slightly larger than O(log n/n), at which rate NCP can be solved in polynomial time [Pra62]. Further, if arbitrary pre-processing of the matrix A is allowed, even NCP with noise rate O(log2 n/n) can be solved in polynomial time [BCLV26]. The source of these limitations is as follows. The core of their reduction is, given an arbitrary matrix A, to consider the vector rT A, where r ∈ Fm 2 is a random vector with Hamming weight w. Clearly, if w > n and A is sufficiently non-degenerate, then rT A will be close to being uniformly random. They show that this is true even if w = O(n/ log n) and m is a large enough polynomial in n. Then, given an NCP instance (A, As + e), they generate the rows of their LPN instance as (rT A, rT (As + e)). The first part rT A is uniform as required, and the second part is (rT A)s + rT e, with rT e playing the part of the noise. This phenomenon of the distribution of rT A being close to uniform for an appropriate distribution of r is referred to as smoothing,1 and has been studied in detail for this and other distributions of r, and in various metrics [BLVW19, YZ21, DDRT23, DR25, PB25]. This method of generating the instance causes the noise rate to increase. If e had noise rate η, then rT e will have noise rate α ≈ 1/2 − e−2ηt . This α has to be non-negligibly removed from 1/2 for the problem to be meaningful. So if w is set to Ω(n/ log n), then only noise rates η between ω(log n/n) and O(log2 n/n) are useful, and the resulting α will never be smaller than 1/2 − o(1). One way to try to deal with this issue is to set w to be something smaller. However, it is easy to check that if w = o(n/ log n), then for any m that is polynomial in n, a random vector of Hamming weight w does not have enough entropy for the distribution of rT A ∈ Fn2 to be close to uniform. This remains true for other natural distributions such as Bernoulli vectors with expected Hamming weight w. Another possibility is that instead of using the same distribution for every matrix A, one could try to use a distribution of r specifically tailored to the given A such that rT A will be uniform. However, without bounds on the Hamming weight of r, it is unclear that rT e will remain unbiased for all possible noise vectors e. In fact, it was recently shown by Pathegama and Barg [PB25] that, for which there at least if m = O(n) and the noise rate is a constant, there are matrices A ∈ Fm×n 2 is no such distribution of r that will satisfy both conditions: rT A is sufficiently close to uniform, and rT e has noise rate 1/2 − 1/poly(n). Though not explicitly stated, their result also applies when e is a random Bernoulli vector. This still leaves open the possibility of this approach working if m is much larger, or if we start with hardness of NCP with a smaller noise rate, but pursuing it will require significantly new techniques.
1.1
Our Results
Our proposal to improve on existing reductions is somewhat different, and is to weaken the notion of smoothing used – instead of asking that rT A be statistically close to uniform, we only ask that it be computationally indistinguishable from uniform. Interestingly, this again relates to decoding a linear code – if we view AT as the parity-check matrix of its dual code, then AT r may be regarded as the syndrome of r. If B generates the dual code of A, then multiplying a noisy dual codeword Bs+r by 1
Strictly speaking, “smoothing” actually refers to a dual phenomenon that this is known to be equivalent to [PB25].
2
AT results in the codeword part being cancelled out, giving us: AT (Bs+r) = (AT B)s+AT r = AT r. So recovering r given rT A is equivalent to decoding the dual code of A with r as the noise vector, and distinguishing rT A from uniform corresponds to solving a decision version of the decoding problem for the dual code of A. This now leads to a win-win situation. If rT A is computationally indistinguishable from uniform, then the existing smoothing-based reduction approach can be used to generate pseudorandom LPN samples of the form (rT A, rT (As + e)), which can then be given to an LPN solver. Since this distribution is pseudorandom, the LPN solver will continue to work and find the secret s. On the other hand, if rT A is not pseudorandom, then the distinguisher that breaks pseudorandomness is essentially solving a decision version of the decoding problem for the dual code of A. Following this observation, we show that the hardness of LPN can be derived from the worstcase simultaneous hardness of decoding both a code and its dual from random noise. An informal version of this reduction is described below. We refer to each row of (A, As + e) as a sample of LPN, and each bit of the secret s as a variable. Theorem 1.1 (Informal, see Theorem 3.1 and Corollary 4.1). Suppose there is an efficient algorithm that has non-negligible advantage in solving LPN with n variables, t samples, and noise rate n−α for some constant α < 1. Then, for any constant β > 0 such that α+β < 1, and m = O(t2 n2β ), , either S can decode the code there are efficient algorithms S and D such that, for any A ∈ Fm×n 2 −(α+β) generated by A from random noise of rate n , or D can distinguish noisy codewords of the dual of this code from random for noise rate nβ /m. To the best of our knowledge, the complexity of decoding a generic linear code and decoding its dual are not known to be negatively correlated. So we expect the complexity of the task specified in the theorem to be the minimum of the worst-case complexity of an algorithm that can decode any code generated by an m × n matrix from random noise of rate n−(α+β) and that of an algorithm that can decode any code generated by an m × (m − n) matrix from random noise of rate nβ /m. As long as α and β are constants such that α + β < 1, the best known algorithms for both of these tasks run in sub-exponential time. Public-Key Cryptography. The most remarkable consequence of our reduction is that, making reasonable assumptions about the hardness of decoding worst-case codes and their duals from random noise, we can get the hardness of LPN required for constructions of Public-Key Encryption using the Alekhnovich paradigm [Ale03]. In particular, this requires hardness for LPN with t = 2n samples and noise rate n−1/2 , which can be obtained by setting the parameters in the theorem to, for instance, α = 0.5, β = 0.4, and m = O(n2.4 ). Challenges. While the observations stated earlier that lead to our reduction are relatively straightforward, realising them fully turns out to be quite challenging. The primary obstacle here is that computational randomness is much harder to obtain and use than actual randomness. One detail that we have been glossing over in our discussion so far is that for the smoothing reduction approach to work, it is not sufficient to show that rT A is close to uniform – one also needs to show that the joint distribution of (rT A, rT e) is close to (Un , Ber(α)), where Un is the uniform distribution over n bits and α is the noise rate of LPN one is reducing to. In the statistical setting of [BLVW19, YZ21], the Fourier analysis they use can easily show this using nearly the same argument that shows that rT A is close to uniform. 3
In our computational setting, however, we do not have powerful tools like Fourier analysis that can readily incorporate this additional biased bit. So even if we are promised that rT A is pseudorandom, and we also know that rT e is a Bernoulli variable with the appropriate parameter α, it is non-trivial to argue that (rT A, rT e) is computationally indistinguishable from (Un , Ber(α)). This is because the leakage rT e could lead to rT A becoming slightly distinguishable from uniform, and this could add up over many such samples to render the resulting distribution easily distinguishable from an LPN instance. It is due to this issue that our reduction only produces an S that decodes from random noise, whereas the earlier smoothing reductions could produce algorithms that can decode from worst-case noise. We show that for most choices of the set of vectors r chosen while constructing the LPN instance, even after fixing the r’s, the randomness in the e ensures that the set of bits rT e are independent Bernoulli variables. This also requires us to use a different error model for the dual code – the r’s are chosen to be vectors of some fixed Hamming weight, rather than as Bernoulli vectors (see Theorem 3.1). Nevertheless, we believe that our reduction should work even with r being a Bernoulli vector and e being any worst-case error vector of bounded Hamming weight. Proving that it works seems quite challenging, however, and will likely require the development of new analytical tools for computational entropy.
1.2
Future Directions
Our work opens up several natural directions for further investigation. More standard worst-case foundations. The worst-case assumption that we need, the simultaneous hardness of decoding a code and distinguishing syndromes of its dual from uniform, is non-standard and, to our knowledge, has not been independently studied. An important next step is to determine whether our approach can be instantiated from more widely studied worst-case assumptions, such as the hardness of the Nearest Codeword Problem (NCP) alone, or classical problems like the Minimum Distance Problem (MDP). More broadly, one would like to understand whether the joint hardness of a code and its dual is inherently needed to improve the smoothing approach to reductions, or whether there is some way around it. Worst-case noise. Our reduction produces a decoder S that works against random Bernoulli noise, whereas the smoothing-based reductions of Brakerski et al. [BLVW19] and Yu–Zhang [YZ21] yield decoders for worst-case bounded-weight noise. Extending our approach to worst-case noise would significantly strengthen the result, but appears to require new tools for reasoning about computational entropy in the presence of adversarially chosen error vectors. We believe this is a tractable and important challenge.
1.3
Paper Outline
In Section 2, we recall the notation and technical tools used throughout the paper. In Section 3, we present our main reduction. In Section 4, we instantiate our reduction with suitable parameters to derive useful hardness regimes for LPN.
4
2
Preliminaries
Notation We use xi to denote the i-th bit of the binary string (vector) x and A[i] as the i-th row of the matrix A. Denote D1 ≡ D2 if the distributions D1 and D2 are the same. The notation x ← D means that x is sampled from the distribution D; when D is a set (we abuse notation), it means x is sampled uniformly from the set. Let Fp denote the order-p prime field. Ber(η) is the Bernoulli distribution with parameter η. Write [n] := {1, 2, . . . , n}. The notation [n] s denotes the set of all vectors in Fn2 with Hamming weight s. Next, wt(v) denotes the Hamming weight of v ∈ Fn2 , and Supp(v) := {i ∈ [n] | vi ̸= 0} is the support of the vector. Fact 2.1. (Piling Up Lemma). Let X1 , X2 , . . . , Xk be independent random variables where Xi ← Ber(η), then therandom variable S = X1 + X2 + · · · + Xk , where addition is over F2 , follows the 1 − (1 − 2η)k distribution Ber . 2 Proof. Deferred to Section A We now define the set of vectors with fixed Hamming weight. Definition 2.2 (Fixed weight vector). Denote W(n, w) as the set of vector v ∈ Fn2 with wt(v) = w. Next, we formally define the Learning Parity with Noise problem (LPN). Definition 2.3 (Learning Parity with Noise (LPN)). Let n, m ∈ Z, and η ∈ [0, 1]. For sample count m, secret dimension n, and noise parameter η, algorithms SLPN and DLPN are said to have advantage ε ∈ [0, 1] in solving the Search LPN and Decision LPN problems, respectively, if they satisfy the following conditions: • Search LPN: SLPN recovers the secret s with probability at least ε: Pr
A←Fm×n 2 s←Fn 2 e←Ber(η)m
[SLPN (A, As + e) = s] ≥ ε.
• Decision LPN: DLPN distinguishes LPN samples from uniform with advantage at least ε:
Pr
A←Fm×n 2 s←Fn 2 e←Ber(η)m
[DLPN (A, As + e) = 1] −
Pr
A←Fm×n 2 b←Fm 2
[DLPN (A, b) = 1] ≥ ε.
We now define the Fixed Weight Syndrome Decoding problem SD, which can be viewed as a slight variation of the dual form of LPN. Definition 2.4 (Fixed Weight Random Syndrome Decoding (SD)). Let n, m ∈ Z, and θ ∈ [0, 1]. For code length m, code dimension n, and noise parameter θ, algorithms SSD and DSD are said to have advantage ε ∈ [0, 1] in solving the Search SD and Decision SD problems, respectively, if they satisfy the following conditions: 5
• Search SD: SSD decodes a syndrome with probability at least ε: [SSD (A, rT A) = r] ≥ ε.
Pr
A←Fm×n 2 r←W(m,θ·m)
• Decision SD: DSD distinguishes a syndrome from uniform with advantage at least ε:
Pr
A←Fm×n 2 r←W(m,θ·m)
[DSD (A, rT A) = 1] −
Pr
A←Fm×n 2 c←Fn 2
[DSD (A, cT ) = 1] ≥ ε.
Remark 2.5. Our definition of Syndrome Decoding Problem deviates from the more natural dual to LPN in that the distribution of r is a randomly sampled fixed weight vector rather than a Bernoulli vector.
3
Average-Case Reduction
Our main contribution is the following theorem, which shows that for every worst-case code generated by a matrix A, an LPN solver yields one of two consequences: either it can be used to solve a random decoding instance associated with A, or it can be used to distinguish fixed-weight random syndrome decoding instance with AT as the parity-check matrix from a random string. Theorem 3.1. Consider n, m, t ∈ Z and η, θ ∈ (0, 1) such that t2 θ2 m < 1. Suppose there exists an algorithm for Search LPN with sample count t, secret dimension n, and noise parameter τ = (1 − (1 − 2η)θ·m )/2, which runs in time T and has advantage ε. Then there exist algorithms D and , at least one of the following is true: S such that for every matrix A ∈ Fm×n 2 • S runs in time poly n, m, T, (1/ε)logm (m/ε) and decodes codewords of A from random noise such that, Pr
s←Fn 2 e←Ber(η)m
[S(A, As + e) = s′ and wt(As′ − (As + e)) ≤ 2ηm] ≥ ε/2 − o(ε).
• D runs in time poly(n, m) + T and distinguishes a sparse combination of rows of A from a uniform string such that, Pr [D(A, cT ) = 1] −
c←Fn 2
Pr
[D(A, rT A) = 1] ≥ ε/2t.
r←W(m,θ·m)
The rest of this section constitutes the proof of Theorem 3.1. Fix any set of parameters n, m, t, η, θ, and τ that satisfy the conditions in the theorem statement. Suppose there is an algorithm SLPN for Search LPN that has running time T and advantage ε as specified in the theorem. The main idea in the reduction is to check how good SLPN is at decoding a code whose generator matrix is derived by randomly combining rows of a given matrix A ∈ Fm×n , and based on this, using it to 2 either decode the code generated by A, or the code whose parity check matrix is A.
6
For any A ∈ Fm×n , let Adv(A) be the advantage of SLPN at decoding a noisy codeword of the 2 code generated by the matrix R · A ∈ Ft×n 2 , where R is a t × m matrix and each row of R is an independently sampled random vector of Hamming weight θ · m, written as R ← W(m, θ · m)t : Adv(A) =
Pr
s←Fn 2 e←Ber(τ )t R←W(m,θ·m)t
[SLPN (RA, RAs + e) = s]
(1)
We can then split into two cases. If Adv(A) is sufficiently large (i.e. Adv(A) ≥ ε/2), then SLPN can be used to construct an algorithm that decodes a noisy codeword As + e of A by running SLPN on (RA, R(As + e)). On the other hand, if Adv(A) is sufficiently smaller than ε (i.e. Adv(A) < ε/2), then this means RA does not look random to SLPN , and we can use a hybrid argument to distinguish the syndrome rT A from uniform when r ← W(m, θ · m). We next state the lemmas capturing the properties of the two resulting algorithms. Note that these lemmas are stated under the assumption that the algorithm SLPN as described above exists. The algorithms themselves and the proofs of these lemmas are presented in Sections 3.1 and 3.2. Together, these lemmas directly imply Theorem 3.1. Lemma 3.2 (Large Advantage). There exists an algorithm S that, for any A ∈ Fm×n such that 2 Adv(A) ≥ ε/2, decodes the code generated by A from random Bernoulli noise of rate η, with success probability at least ε/2 − o(ε). More precisely, Pr
s←Fn 2 e←Ber(η)m
[S(A, As + e) = s′ and wt(As′ − (As + e)) ≤ 2ηm] ≥ ε/2 − o(ε).
Further, S runs in time poly n, m, T, (1/ε)logm (m/ε) . such that Lemma 3.3 (Small Advantage). There exists an algorithm D that, for any A ∈ Fm×n 2 Adv(A) < ε/2, distinguishes between random syndromes of the code with parity check matrix A and the uniform distribution with advantage at least ε/2t. More precisely, Pr [D(A, cT ) = 1] −
c←Fn 2
Pr
[D(A, rT A) = 1] ≥ ε/2t.
r←W(m,θ·m)
Further, D runs in time T + poly(n, m).
3.1
Large Advantage
In this section, we prove Lemma 3.2, about the ability of an algorithm S to decode the code generated by A when Adv(A) ≥ ε/2. Lemma 3.2 (Large Advantage). There exists an algorithm S that, for any A ∈ Fm×n such that 2 Adv(A) ≥ ε/2, decodes the code generated by A from random Bernoulli noise of rate η, with success probability at least ε/2 − o(ε). More precisely, Pr
s←Fn 2 e←Ber(η)m
[S(A, As + e) = s′ and wt(As′ − (As + e)) ≤ 2ηm] ≥ ε/2 − o(ε).
Further, S runs in time poly n, m, T, (1/ε)logm (m/ε) . 7
Algorithm 1 Algorithm S(A ∈ Fm×n , b ∈ Fm 2 ) 2 1: Sample matrix R ← W(m, θ · m)t . 2: Set threshold = max(8 logm (m/ε) log(1/ε), 12). 3: Set C = {j ∈ [t] | ∃i < j : Supp(R[i]) ∩ Supp(R[j]) ̸= ∅}.
▷ Smoothing matrix ▷ Threshold ▷ Collision Set
4: Convert C into a list with arbitrary ordering. 5: if |C| ≥ threshold then
return ⊥. |C| 7: for each v ∈ F2 do 8: Set b′ ← Rb. 9: for each j in C do 10: Replace b′j ← (vj + Ber(τ ))
▷ Abort
6:
▷ Iterate through collided rows ▷ Recall that τ = (1 − (1 − 2η)θ·m )/2
Query s′ ← SLPN (RA, b′ ). 12: if wt(b − As′ ) ≤ 2ηm then 13: return s′ . 14: return ⊥
▷ Query oracle ▷ Verify answer
11:
The algorithm S that proves the lemma is described below, followed by the proof of the lemma. Here, SLPN is the assumed search algorithm for LPN that has running time T and advantange ε. Proof of Lemma 3.2. Fix an A such that Adv(A) ≥ ε/2. Recall that this means that SLPN has ε/2 probability of successfully recovering s when given a sample from the distribution (RA, RAs + Ber(τ )t ), with τ = (1 − (1 − 2η)θ·m )/2. To show the correctness of the algorithm, it suffices to prove that in at least one iteration, the input (RA, b′ ) provided to SLPN in line 11 has the same distribution as (RA, RAs+Ber(τ )t ), and also that the algorithm does not prematurely terminate at line 6. In the following claim, we show that the algorithm does not abort in line 6 with high probability. Claim 3.4. The probability that |C| ≥ threshold = max(8 logm (m/ε) log(1/ε), 12) is at most o(ε). Formally, Pr [|C| ≥ max(8 logm (m/ε) log(1/ε), 12)] ≤ o(ε). Proof. Using union bound, we first upperbound the probability that a column in R ← W(m, θ · m)t has at least k bits that are 1. Let Pi ∈ Ft2 be the i-th column vector of R. For any i ∈ [m], t θm k etθ k Pr [wt(Pi ) ≥ k] ≤ ( ) ≤( ) . (2) k m k √ Since t2 θ2 m < 1, which implies tθ < 1/ m. We can conveniently set k = 4 logm (m/ε) and do a union bound to say that with high probability 1 − o(ε), no columns will have more than k non-zero bits. Formally, e Pr [∃i ∈ [m], wt(Pi ) ≥ 4 logm (m/ε)] ≤ m( √ )4 logm (m/ε) = o(ε). m
8
(3)
Setting k = O(logm (m/ε)) is essentially having k being a constant when ε = 1/poly(n). Next, we show that with high probability 1 − o(ε), there are at most h = 2 log(1/ε) columns that have weight at least 2. This is done again by using union bound over all possible h subsets of columns, [m] m Pr ∃S ∈ , ∀j ∈ S, wt(Pj ) ≥ 2 ≤ Pr [∀j ∈ [h], wt(Pj ) ≥ 2] . (4) h h Since each row is a fixed weight vector, if a column happens to have a weight ≥ 2, conditioned on this event, the probability of the next column having weight ≥ 2 is smaller. This negative correlation property implies, Pr [∀j ∈ [h], wt(Pj ) ≥ 2] ≤ Pr [wt(P1 ) ≥ 2]h ≤ (
t2 θ 2 h ) . 2
Therefore, combining Eq. (4) and Eq. (5), gives us an upperbound 2 2 m t θ h emt2 θ2 h Pr[There exists at least h columns with weight ≥ 2] ≤ ( ) ≤( ) . h 2 2h
(5)
(6)
Since mt2 θ2 < 1. If ε ≤ 1/2, we can plug in h = 2 log(1/ε) to get (
e emt2 θ2 h ) ≤ ( )2 log(1/ε) = o(ε) 2h 4
Otherwise, if ε > 1/2, we can plug in h = 3 to get (
emt2 θ2 h e ) ≤ ( )3 = o(ε) 2h 6
Therefore, if h = max(2 log(1/ε), 3), the probability in Eq. (6) is upper bounded by o(ε). In summary, probability bounds we have on the two bad events are, • The probability that there exists a column in R with more than k = 4 logm (m/ε) is at most o(ε) (Eq. (3)). • The probability that there exists h = max(2 log(1/ε), 3) columns in R with weight ≥ 2 is at most o(ε) (Eq. (6)). By union bound, with probability 1 − o(ε), neither of the bad events happens. In that scenario, the maximum size of |C| is upper-bounded as follows, |C| < k · h = max(8 logm (m/ε) log(1/ε), 12 logm (m/ε)). Because the second value in the maximum expression happens only when ε > 1/2, that also means logm (m/ε) ≤ 1. Therefore, the statement can be further simplified |C| < k · h = max(8 logm (m/ε) log(1/ε), 12) Hence, the probability of the abort in line 6, i.e |C| ≥ max(8 logm (m/ε) log(1/ε), 12), is at most o(ε). 9
Now, assume that abort does not occur in line 6, we will show that in that case at least one iteration, the input (RA, b′ ) provided to SLPN in line 11 has the same distribution as (RA, RAs + Ber(τ )t ). By definition of C = {j ∈ [t] | ∃i < j : Supp(R[i]) ∩ Supp(R[j]) ̸= ∅}, we get that for all distinct p, q ∈ [t] \ C, Supp(R[p]) ∩ Supp(R[q]) = ∅. |C|×m
We can therefore split the smoothing matrix R into two parts: ‘touched’ submatrix Rt ∈ F2 , (t−|C|)×m consisting of the rows indexed by the elements of C and ‘untouched’ submatrix Rut ∈ F2 , consisting of the rows not indexed by the elements of C. Formally, viewing both C and [t] \ C as lists with arbitrary but fixed orderings, we define for every i ∈ [|C|],
Rt [i] := R[C[i]] and Rut [i] := R[([t] \ C)[i]]
for every i ∈ [t − |C|].
To simplify the argument, ignore the ordering of the rows in Rut and Rt as we can always combine them back to R and maintain the original ordering. For the rows represented by Rut , because the rows’ supports are disjoint, each bit of Rut ·e, where e ← Ber(η)m , is independently and identically distributed. The distribution of (Rut e)i is exactly the sum of θ · m independent and identically distributed Ber(η) random variables. By Fact 2.1, this is (Rut e)i ≡ Ber(τ ) where τ = (1 − (1 − 2η)θ·m )/2 and implies that (Rut , Rut e) ≡ (Rut , Ber(τ )t−|C| ). Then (Rut A, Rut b) = (Rut A, Rut As + Rut e) ≡ (Rut A, Rut As + Ber(τ )t−|C| ). |C|
For the rows represented by Rt , since we are enumerating all possible F2 assignments. There will be one assignment that is exactly the value of v = Rt As, and in this case the replacement procedure in line 10 sets the corresponding part of b′ to exactly Rt As + Ber(τ )|C| . Finally, we combine Rt and Rut back to R respecting the original ordering. Assuming that we are in the iteration of getting a correct assignment, v = Rt As, the bits in Rt b = Rt As + Rt e are replaced with Rt As + Ber(τ )|C| . This does not leak any information about Rut e, and the query to SLPN is exactly the distribution (RA, RAs + Ber(τ )m ). As SLPN has ε/2 probability of success on this distribution and the probability of abort in line 6 is at most o(ε), with probability at least ε/2 − o(ε), this execution SLPN (RA, b′ ) will return s′ = s. For the verification of the secret s in line 12, having the correct candidate secret s′ = s, the probability that error vector b − As′ has Hamming weight greater than 2ηm is exponentially small, and so the verification will fail with negligible probability. So the algorithm S succeeds with probability at least ε/2 − o(ε). The remaining possibility is that the algorithm SLPN (RA, b′ ) returns a candidate s′ that is not equal to s in some other iteration (i.e v ̸= Rt As). This is still fine because s′ must have the property that wt(b − As′ ) ≤ 2ηm to pass the verification. Therefore, S recovers a secret candidate s′ from noisy codeword samples of A with advantage at least ε/2 − o(ε). The runtime of the algorithm is determined by the size of the matrix A ∈ Fm×n and the 2 number of queries called to SLPN . Since |C| is upper bounded by max(8 logm (m/ε) log(1/ε), 12), logm (m/ε) log(1/ε) ) = O((1/ε)logm (m/ε) ) .Therefore, the runtime of S is the number of iterations is O(2 log (m/ε) poly n, m, T, (1/ε) m
10
3.2
Small Advantage
In this section, we prove Lemma 3.3, about the ability of an algorithm D to distinguish random syndromes from uniform when Adv(A) < ε/2 . Lemma 3.3 (Small Advantage). There exists an algorithm D that, for any A ∈ Fm×n such that 2 Adv(A) < ε/2, distinguishes between random syndromes of the code with parity check matrix A and the uniform distribution with advantage at least ε/2t. More precisely, Pr [D(A, cT ) = 1] −
c←Fn 2
[D(A, rT A) = 1] ≥ ε/2t.
Pr r←W(m,θ·m)
Further, D runs in time T + poly(n, m). The algorithm D that proves the lemma is described below, followed by the proof of the lemma. Here, SLPN is the assumed search algorithm for LPN that has running time T and advantage ε. ) , cT ∈ F1×n Algorithm 2 Algorithm D(A ∈ Fm×n 2 2 1: Sample i ← [0, t − 1].
▷ Select which hybrid to use
(t−1−i)×n 2: Sample matrices R ← W(m, θ · m)i , B ← F2
RA T t×n 3: Set H ← c ∈ F2 B t 4: Sample s ← Fn 2 and e ← Ber(τ ) 5: if SLPN (H, Hs + e) returns s then 6: return 1 7: else return 0
▷ Create a sample from the hybrid distribution ▷ Recall that τ = (1 − (1 − 2η)θ·m )/2 ▷ Check whether SLPN succeeds
Proof of Lemma 3.3. Fix an A such that Adv(A) < ε/2. We begin the proof by defining a sequence is defined by the of hybrid distributions. For any i ∈ [0, t], the hybrid distribution Hi over Ft×n 2 following sampling process: 1. Sample a matrix R ← W(m, θ · m)i . (t−i)×n
2. Sample a matrix B ← F2
RA 3. Output the row-concatenated matrix ∈ Ft×n 2 . B We now use the fact that, by our assumption in this case, the SLPN solver succeeds with low probability on the hybrid corresponding to i = t, whereas it succeeds with high probability on the hybrid corresponding to i = 0. To be concrete, first fix any i ∈ [0, t − 1], sample R ← W(m, θ · m)i , RA (t−i−1)×n B ← F2 , we can make the following conclusion on the distribution H of H = cT . B • If c ← Fm 2 , H is exactly Hi . 11
• If c = rT A where r ← W(m, θ · m), H is exactly Hi+1 . With s and e sampled as s ← Fn2 and e ← Ber(τ )t , define Adv0 , Adv1 as Adv0 =
Pr i←[0,t−1] H←Hi
[SLPN (H, Hs + e) = s],
Adv1 =
Pr i←[0,t−1] H←Hi+1
[SLPN (H, Hs + e) = s].
Then, the behavior of the algorithm D we defined can be described exactly with Adv0 , Adv1 Adv0 = Prn [D(A, cT ) = 1], c←F2
Adv1 =
Pr
[D(A, rT A) = 1].
r←W(m,θ·m)
By a standard hybrid argument, Adv0 and Adv1 have a gap of Adv0 − Adv1 ≥ ε/2t. This is stated in the following claim, whose proof we defer to Section A. Claim 3.5. (Hybrid Argument). Adv0 − Adv1 ≥ ε/2t. Therefore, algorithm D can distinguish random syndromes of A from uniform with advantage at least ε/2t. As D only calls SLPN once, its running time is poly(n, m) + T .
4
Corollaries
In this section, we discuss some implications of Theorem 3.1. We show how the theorem gives meaningful hardness for LPN with parameters that are within the statistical-computational gap. In particular, we will show that Theorem 3.1 gives partial worst-case hardness for some parameters for LPN that can be used to construct public-key cryptography. The next corollary describes the contrapositive statement of Theorem 3.1 with parameters simplified and rearranged. Corollary 4.1 (Hardness for LPN). Consider any polynomial 2 t(n) ∈ Z with t(n) > n, constants 2β α, β ∈ (0.01, 0.99) with α + β ∈ (0.01, 0.99), and m(n) = 2t n . Suppose that for every pair of PPT algorithms (S, D), there exists a negligible function negl such that, for all large enough n, there exists an F2 -matrix A of dimension m × n for which both of these conditions are true: • Pr[S(A, As + e) = s′ and wt(As′ − (As + e)) ≤ 2m/nα+β ] ≤ negl(n), where s ← Fn2 , e ← Ber(n−(α+β) )m . • Pr[D(A, cT ) = 1] − Pr[D(A, rT A) = 1] ≤ negl(n), where c ← Fn2 , r ← W(m, nβ ). Then, for the Search LPN problem with sample count t(n), secret dimension n, and noise parameter n−α , no PPT algorithm has non-negligible advantage. Proof. This corollary can be proven using the contrapositive statement of Theorem 3.1 with an appropriate setting of variables as follows: η=
1 nα+β
θ=
nβ m
The resulting noise rate of LPN from the theorem can be bounded as follows using the Bernoulli inequality, nβ ! 1 2 τ= 1 − 1 − α+β ≤ n−α . 2 n 12
The noise rate in the LPN instance can later be artificially increased to be equal to n−α as required. Next, we can also check that the condition of t2 θ2 m < 1 required by Theorem 3.1 (that the probability of intersection between two rows is bounded) is also satisfied , (t2 )n2β 1 (t)2 (nβ )2 ≤ 2 2β = < 1. m 2 2t n So if there is a polynomial-time algorithm for Search LPN that has non-negligible advantage ε(n) on infinitely many values of n, then by Theorem 3.1, it contradicts the assumption in the statement of the corollary. Note that the runtime of S resulting from the theorem is poly n, m, T, (1/ε)logm (m/ε) , and when ε = 1/poly(n), we have that (1/ε)logm (m/ε) = poly(n), so the runtime is still polynomial in n. That concludes the proof of the corollary. Non-Triviality of Hardness. For the reductions in Theorem 3.1 and Corollary 4.1 to be nontrivial and useful for cryptography, they have to show that under a reasonable worst-case hardness assumption, we can infer the hardness of LPN with parameters for which it is possible to solve statistically. For the Search LPN problem to be statistically feasible to solve, the parameters should be in a regime where the instance (A, As + e) contains enough information about the secret s. Using the fact that random linear codes achieve Shannon capacity for the binary symmetric channel [GRS12], an LPN instance with secret size n, noise rate η, and sample size t ≫ n/(1 − h(η)), where h is the binary entropy function, satisfies this condition. For η = n−α with α ∈ (0.01, 0.99), this condition is satisfied if t > n + ω(n1−α log n). To the best of our knowledge, to design a pair of algorithms (S, D) such that S can decode the code generated by a matrix A from random noise while D can distinguish random syndromes generated by it from uniform is to pick the optimal algorithm for each task separately, just keep the more efficient one as S or D, and let the other algorithm simply not do anything. If α, β ∈ (0.01, 0.99), the best such algorithms run in time exp(O(n1−(α+β) )) for S and exp(O(nβ )) for D [Pra62]. Thus, if (α + β) ∈ (0.01, 0.99), the best algorithms for the worst-case problem are still sub-exponential time. Parameter settings. It remains to show that we can set our parameters so that the above conditions are simultaneously satisfied. Some of these are as follow. For each setting of parameters below, we make the corresponding assumption as stated in the hypothesis of Corollary 4.1, and the conclusion is the result of applying the corollary with these parameters. 1. Setting α = 0.1, β = 0.1, and m = 8n2.2 implies the hardness of LPN with t = 2n samples and noise rate n−0.1 . 2. Setting α = 0.5, β = 0.45, and m = 8n2.9 implies the hardness of LPN with t = 2n samples and noise rate n−0.5 . 3. Setting α = 0.8, β = 0.1, and m = 2n6.2 implies the hardness of LPN with t = n3 samples and noise rate n−0.8 . Note that the last two parameter settings above, together with known search-to-decision reductions for LPN [Reg09, AIK07, MM11], are sufficient for use in Alekhnovich’s construction of a 13
Public-Key Encryption (PKE) scheme from the hardness of LPN [Ale03]. There are other viable settings of the parameter β for which this would be true as well. The following is one specific corollary of the many that are correspondingly possible. Corollary 4.2. If the hypothesis of Corollary 4.1 is satisfied for the parameter setting t = 2n, α = 0.5, β = 0.45 and m = 8n2.9 , then there is a secure construction of PKE.
5
Acknowledgements
We would like to thank Yuval Ishai for pointing us to relevant references on barriers to the statistical smoothing approach. This work was supported by the National Research Foundation, Singapore, under awards no. NRF-NRFF14-2022-0010 and NRF-NRFI09-0005.
References [AGZ26]
Divesh Aggarwal, Rishav Gupta, and Li Zeyong. Hardness amplification for (sparse) lpn, 2026. 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 of Lecture Notes in Computer Science, pages 92–110, Santa Barbara, CA, USA, August 19–23, 2007. Springer Berlin Heidelberg, Germany. doi:10.1007/ 978-3-540-74143-5_6.
[AK11]
Per Austrin and Subhash Khot. A simple deterministic reduction for the gap minimum distance of code problem. In Luca Aceto, Monika Henzinger, and Jiřı́ Sgall, editors, Automata, Languages and Programming, pages 474–485, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
[Ale03]
Michael Alekhnovich. More on average case vs approximation complexity. In 44th Annual Symposium on Foundations of Computer Science, pages 298–307, Cambridge, MA, USA, October 11–14, 2003. IEEE Computer Society Press. doi:10.1109/SFCS. 2003.1238204.
[BCLV26] Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, and Prashant Nalini Vasudevan. Decoding balanced linear codes with preprocessing. In Shubhangi Saraf, editor, 17th Innovations in Theoretical Computer Science Conference, ITCS 2026, Bocconi University, Milan, Italy, January 27-30, 2026, LIPIcs, pages 23:1–23:23. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2026. 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. Cryptographic primitives based on hard learning problems. In Douglas R. Stinson, editor, Advances in Cryptology – CRYPTO’93, volume 773 of Lecture Notes in Computer Science, pages 278–291, Santa Barbara, CA, USA, August 22–26, 1994. Springer Berlin Heidelberg, Germany. doi:10.1007/3-540-48329-2_24. 14
[BJMM12] Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer. Decoding random binary linear codes in 2n/20 : How 1 + 1 = 0 improves information set decoding. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 520–536, Cambridge, UK, April 15–19, 2012. 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, 2003. [BLVW19] Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, and Daniel Wichs. Worst-case hardness for LPN and cryptographic hashing via code smoothing. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Part III, volume 11478 of Lecture Notes in Computer Science, pages 619–635, Darmstadt, Germany, May 19–23, 2019. 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 22n/21 and McEliece security. In Proceedings of the Tenth International Workshop on Coding and Cryptography (WCC 2017), page 214, September 2017. 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, PostQuantum Cryptography - 9th International Conference, PQCrypto 2018, pages 25–46, Fort Lauderdale, Florida, United States, April 9–11, 2018. Springer, Cham, Switzerland. doi:10.1007/978-3-319-79063-3_2.
[DDRT23] Thomas Debris-Alazard, Léo Ducas, Nicolas Resch, and Jean-Pierre Tillich. Smoothing codes and lattices: Systematic study and new bounds. IEEE Trans. Inf. Theory, 69(9):6006–6027, 2023. doi:10.1109/TIT.2023.3276921. [DEEK24] Léo Ducas, Andre Esser, Simona Etinski, and Elena Kirshanova. Asymptotics and improvements of sieving for codes. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, Part VII, volume 14657 of Lecture Notes in Computer Science, pages 151–180, Zurich, Switzerland, May 26–30, 2024. 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 decoding via smoothing bounds. In Tibor Jager and Jiaxin Pan, editors, PKC 2025: 28th International Conference on Theory and Practice of Public Key Cryptography, Part II, volume 15675 of Lecture Notes in Computer Science, pages 363–392, Røros, Norway, May 12–15, 2025. Springer, Cham, Switzerland. doi:10.1007/978-3-031-91823-0_ 12.
[Dum91]
Ilya Dumer. On minimum distance decoding of linear codes. In G. Kabatianskii, editor, Proceedings of the 5th Joint Soviet-Swedish International Workshop on Information Theory, pages 50–52, Moscow, 1991. Nauka. 15
[GRS12]
Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory. Draft available at http://www. cse. buffalo. edu/atri/courses/coding-theory/book, 2(1), 2012.
[Lyu05]
Vadim Lyubashevsky. The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, volume 3624 of Lecture Notes in Computer Science, pages 378–389. Springer, 2005. doi:10.1007/11538462_32.
[MM11]
Daniele Micciancio and Petros Mol. Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions. In Phillip Rogaway, editor, Advances in Cryptology – CRYPTO 2011, volume 6841 of Lecture Notes in Computer Science, pages 465–484, Santa Barbara, CA, USA, August 14–18, 2011. 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 Õ(20.054n ). In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011, volume 7073 of Lecture Notes in Computer Science, pages 107– 124, Seoul, South Korea, December 4–8, 2011. 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 2015, Part I, volume 9056 of Lecture Notes in Computer Science, pages 203–228, Sofia, Bulgaria, April 26–30, 2015. 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 reduction via code smoothing. Designs, Codes and Cryptography, 93(7):2761–2778, 2025. 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, 2009. ACM Press. doi:10.1145/1536414.1536461.
[Pie12]
Krzysztof Pietrzak. Cryptography from learning parity with noise. In Conference on Current Trends in Theory and Practice of Informatics, 2012. 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 linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009.
[Ste89]
Jacques Stern. A method for finding codewords of small weight. In Gérard D. Cohen and Jacques Wolfmann, editors, Coding Theory and Applications, volume 388 of Lecture Notes in Computer Science, pages 106–113. Springer, 1989. doi:10.1007/BFb0019850.
16
[YZ16]
Yu Yu and Jiang Zhang. Cryptography with auxiliary input and trapdoor from constantnoise LPN. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology – CRYPTO 2016, Part I, volume 9814 of Lecture Notes in Computer Science, pages 214–243, Santa Barbara, CA, USA, August 14–18, 2016. 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 subexponential hardness for LPN. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part III, volume 12827 of Lecture Notes in Computer Science, pages 473–501, Virtual Event, August 16–20, 2021. Springer, Cham, Switzerland. doi:10.1007/978-3-030-84252-9_16.
A
Deferred Proof
Fact 2.1. (Piling Up Lemma). Let X1 , X2 , . . . , Xk be independent random variables where Xi ← Ber(η), then therandom variable S = X1 + X2 + · · · + Xk , where addition is over F2 , follows the 1 − (1 − 2η)k distribution Ber . 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 Y Y S Xi E (−1) = E = E (−1)Xi = (1 − 2η)k . (−1) i=1
i=1
From E (−1)S = Pr[S = 0] − Pr[S = 1] = 1 − 2 Pr[S = 1]. Hence
Pr[S = 1] =
1 − (1 − 2η)k . 2
Claim 3.5. (Hybrid Argument). Adv0 − Adv1 ≥ ε/2t. Proof. Suppose s ← Fn2 , e ← Ber(τ )t throughout the proof. Recall that, Adv =
Pr
R←W(m,θ·m)t
[SLPN (RA, RAs + e) = s].
From SLPN having advantage ε and Adv < ε/2, Pr
B←Ft×n 2
[SLPN (B, Bs + e) = s] −
Pr R←W(m,θ·m)t
[SLPN (RA, RAs + e) = s] ≥ ε/2.
(7)
Note that Ht is exactly the distribution RA, while H0 is the uniform distribution. Telescoping, Pr
B←Ft×n 2
=
X i∈[0,t−1]
[SLPN (B, Bs + e) = s] −
Pr R←W(m,θ·m)t
Pr [SLPN (Hi , Hi s + e) = s] −
Hi ←Hi
17
[SLPN (RA, RAs + e) = s]
Pr
Hi+1 ←Hi+1
[SLPN (Hi+1 , Hi+1 s + e) = s].
There are two components in the equation, look at each component individually, by the law of total probability, X Pr [SLPN (Hi , Hi s + e) = s] i∈[0,t−1]
=t
Hi ←Hi
1 · Pr [SLPN (Hi , Hi s + e) = s] t Hi ←Hi
X i∈[0,t−1]
=t
X i∈[0,t−1]
=t
Pr
[X = i]
X←[0,t−1]
Pr i←[0,t−1] Hi ←Hi
Pr
HX ←HX
[SLPN (HX , HX s + e) = s | X = i]
[SLPN (Hi , Hi s + e) = r] = t · Adv0 .
By a similar argument, X i∈[0,t−1]
Pr
Hi+1 ←Hi+1
[SLPN (Hi+1 , Hi+1 s + e) = s] = t · Adv1 .
Substitute into Eq. (7), and that concludes the claim t · Adv0 − t · Adv1 ≥ ε/2 =⇒ Adv0 − Adv1 ≥ ε/2t.
18