Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli

Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli Andrej Bogdanov∗

Kel Zin Tan†

Prashant Nalini Vasudevan‡

arXiv:2610.12913v1 [cs.CR] 9 Oct 2026

October 12, 2026

Abstract The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning problems widely used in cryptography, including Learning with Errors (LWE), Learning with Rounding (LWR), and Learning Parity with Noise (LPN). We present a new sample-preserving search-to-decision reduction for Noisy Linear Equations that has complexity poly(n, m, log q, q/σ), where n is the dimension of the secret, m is the number of samples, q is the modulus, and σ is the magnitude of the noise (defined suitably for the kind of noise involved). In particular, this implies search-to-decision reductions for LWE and LWR that run in time poly(n) even if the modulus q is exponentially large, as long as the noise-to-modulus ratio σ/q is non-negligible. Our reduction works for prime moduli q. If q is composite, it instead produces a list that contains a small multiple of the solution. Prior to this work, known search-to-decision reductions for LWE and LWR either did not preserve the parameters of the problem (i.e., m, n, σ, and q), or had complexity that scaled polynomially with either σ or the largest prime factor of q.

∗ † ‡

abogdano@uottawa.ca. University of Ottawa. kelzin@u.nus.edu. Department of Computer Science, National University of Singapore. prashvas@nus.edu.sg. Department of Computer Science, National University of Singapore.

i

Contents 1 Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Technical Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Paper Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 3 4 6

2 Preliminaries 2.1 Coprime secret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Noise Tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Fourier Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 7 8 9

3 Reduction 3.1 Threshold Distinguisher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Terminal Hybrid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Correlation With Threshold Function . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Heavy Fourier Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Fourier analysis of f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Learning Significant Fourier Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Proof of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10 10 12 12 14 16 17 18

4 Corollaries 18 4.1 Exact Secret Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5 Acknowledgments

20

A Supplementary Proofs 22 A.1 Hybrid Argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

ii

1

Introduction

The Noisy Linear Equations problem asks to recover the solution to a random system of linear m equations over Zq given noisy outputs. Let R : Zm q → Zp be a “noise” function. (This function could be randomised, and p may or may not be the same as q.) Given a random matrix A ∈ Zm×n q and the noisy evaluation R(Ax) for a random x ∈ Znq , the goal for the Search problem is to recover the solution x. For the Decision problem, similarly given A, the goal is to distinguish the noisy evaluations R(Ax) from a random vector in Zm p . This problem is clearly easy for some choices of the noise function R, such as the identity function. It is believed to be hard for certain choices of the noise function, such as the following: • R(v) = v + e mod q, where each entry in e is draws from the discrete Gaussian distribution. This is known as the Learning With Errors (LWE) problem [Reg09]. The hardness of LWE can be shown based on the worst-case hardness of lattice problems [Reg09, Pei09, BLP+ 13] • R(v) = ⌊p · v/q⌉ mod p, where p < q and ⌊·⌉ represents rounding to the nearest integer. This is called the Learning With Rounding (LWR) problem [BPR12], whose hardness follows from reductions from LWE [BPR12, AKPW13, BGM+ 16, AA16]. • R(v)i = vi + ai · bi for each i ∈ [m], where ai is a random element of Zq and bi is a biased random bit. This is the generalised Learning Parity with Noise (LPN) problem [BFKL93]. The above problems are of considerable importance to cryptography, and form the basis of numerous constructions of advanced cryptographic primitives [Reg09, BV11, BPR12, BLMR13, BP14]. Search-to-Decision Reductions. In the regimes of interest to public-key cryptography, the planted solution x is typically unique. Search is thus at least as hard as decision. A searchto-decision reduction establishes their equivalence: It efficiently converts a distinguisher (decision algorithm) into a solution finder (search algorithm). Cryptographic applications such as public-key encryption [Reg09], fully homomorphic encryption [BV11], and structured psedurorandom functions [BPR12, BLMR13, BP14] assume decision hardness. A search-to-decision reduction increases our confidence in their security. In order for this equivalence to be as tight as possible, it is desirable for such reductions to be computationally efficient, preserve the number of samples and variables in the problem instance (i.e., the parameters m and n), and preserve the noise function R. Recall that in the LWE problem, the noise function R(v) corresponds to adding to each entry in v a sample (called the “error”) from a discrete Gaussian distribution, say of standard deviation σ, modulo q. The first search-to-decision reduction for LWE is from Regev’s work that originally defined the problem [Reg09]. This reduction preserves the error distribution, but requires the modulus q to be prime. It is also not sample-preserving, with the search algorithm needing a Õ(1/ε2 )-factor of extra samples, where ε is the advantage of the distinguisher. Further, the complexity1 of the reduction scales polynomially with the modulus q. Several subsequent works have since extended this reduction to composite moduli q, under various conditions. Peikert [Pei09] obtained aP reduction for q = p1 · · · pk (for distinct primes pi ) that has runtime scaling polynomially P with ( i pi ), under the requirement that the advantage of the distinguisher ε is larger than Ω( i exp(−p2i σ 2 )). Applebaum et al. [ACPS09] obtained a 1

By “complexity”, we typically mean the product of the running time and the inverse of the success probability.

1

Work

Problem

Moduli

Noise

Samples

Complexity

[Reg09] [MP12] [BLP+ 13]+[MP12] [MM11] [BLP+ 13]+[MM11] [BGM+ 16] This Work

LWE LWE LWE LWE LWE LWR LWE/LWR

Prime pe11 · · · pekk All Prime Power All Prime Prime

Preserving Preserving √ O( n) loss Preserving √ O( n) loss Preserving Preserving

Õ(m/ε2 ) Õ(m/ε2 ) Õ(m/ε2 ) Preserving m + Õ(n) Preserving Preserving

poly(q) P poly( i pi + ei ) P poly( i p′i + e′i ) poly(σ) poly(log q, σ) poly(q) poly(log q, q/σ)

Table 1: Comparison of search-to-decision reductions. n is the dimension of the secret, m is the number of samples, σ is the noise magnitude (ratio of moduli in case of LWR), q is the modulus, and ε is the advantage of the decision algorithm. Complexity omits poly(m, n, 1/ε) factors. For reductions involving [BLP+ 13], the reduction is from Search LWE with a possibly different modulus ′e′

′e′

q ′ = p1 1 · · · pk k . reduction for q = pe (for prime p) that has runtime scaling polynomially with p and e. Micciancio and Peikert [MP12] combined both results and obtained P a reduction for q = pe11 · · · pekk (for distinct primes pi ) that has runtime scaling polynomially with (pi + ei ) and a similar requirement on P 2ei 2 2 the distinguisher’s advantage: ε > Ω( i exp(−pi σ /q )). All of these reductions also have a Õ(1/ε2 )-factor increase in the number of samples needed by the search algorithm. Later work by Brakerski et al. [BLP+ 13] showed how to reduce Decision LWE over a modulus ′ q to Decision LWE over any modulus q ≤ q ′ , with runtime scaling only polylogarithmically in q ′ . Combined with the other reductions mentioned above, this enables reductions from Search LWE over a nice q ′ (that has efficient search-to-decision reductions) to Decision LWE over any q ≤ q ′ . Search-LWEm′ ,q′ ,σ′ =⇒ Decision-LWEm′ ,q′ ,σ′ =⇒ Decision-LWEm,q,σ The price of Brakersi et al.’s reduction is that the noise-to-modulus ratio of the resulting instance √ is larger: σ/q = Ω( n · σ ′ /q ′ ). The number of variables remains the same, while the number of samples decreases by Ω(n + log log q) (i.e., m = m′ − Ω(n + log log q)). Most relevant to our work is the search-to-decision reduction of Micciancio and Mol [MM11], which is the only known sample-preserving classical reduction for LWE.2 Their reduction avoids the dependence on q and has runtime scaling polynomially with the noise magnitude σ instead. In the special case when q is of the form pe and the noise is restricted to be at most (p/2) in each element, the complexity reduces to linear in p (and polylogarithmic in q). More recently, Sudo et al. [SHTY25] showed a quantum sample-preserving search-to-decision reduction for LWE that uses only two queries to the distinguisher, but succeeds only with probability inverse polynomial in q. Using techniques related to those of Micciancio and Mol, Bogdanov et al. [BGM+ 16] effectively showed the only known search-to-decision reduction for LWR, which has complexity polynomial in the modulus q.3 Limitations of Existing Reductions. The easy reduction from decision to search for Noisy Linear Equations preserves all parameters: secret dimension, number of samples, error magnitude, 2 3

The sample-preserving reduction of Applebaum et al. for LPN [AIK09] is based on similar ideas. The focus of their work is different, but this result is implicit in the proof of their Lemmas 3 and 4.

2

and modulus. To establish equivalence of search and decision, so should the reverse reduction. As described above, all currently known reductions either fail to preserve one or more of these, or else have running time that is polynomial in the modulus or error magnitude (and hence are not efficient when these are large). The features of these reductions are summarised in Table 1.

1.1

Our Results

We construct a new parameter-preserving search-to-decision reduction for the Noisy Linear Equations problem for noise functions that are robust to ℓ∞ perturbations (see below for details). Where it applies, our reduction is sample-preserving and, roughly speaking, its complexity scales with the noise-to-modulus ratio rather than with the magnitude of the noise or the modulus. Among other corollaries (see Section 4), our results imply the following for any prime modulus q: • Search-to-decision reduction for LWE that preserves the dimension of the secret n, number of samples m, modulus q, and error magnitude σ, with running time that is poly(n, m, log q, q/σ) • Search-to-decision reduction for LWR that preserves the dimension of the secret n, number of samples m, modulus q, and rounding modulus p, with running time that is poly(n, m, log q, p) In particular, our reduction for LWE runs in polynomial time even if the modulus q is exponentially large, as long as the error rate σ/q is inverse-polynomial. More generally, our reduction applies to Noisy Linear Equations problems with a noise function R that can tolerate small perturbations. We say R is B-smooth if for every v of ℓ∞ -norm at most B, with sufficiently high probability over the choice of A, the distribution of R(Ax + v) is very close to that of R(Ax). LWE is smooth when B is somewhat smaller than the error magnitude σ. LWR is smooth when the B is somewhat smaller than the ratio of the moduli q/p. (See Section 2 for the relevant formal definitions and statements.) Theorem 1.1 (Informal, see Theorem 3.1 and Section 4). Consider any n, m, p, q ∈ Z+ , with m q being prime, and a B-smooth noise function R : Zm q → Zp . For the Noisy Linear Equations problem over Zq with sample count m, secret dimension n, and noise function R, there exists an algorithm that, given a decision algorithm that runs in time T and has advantage ε, solves the search problem in time poly(n, m, log q, q/Bε, T ) with success probability Ω̃(Bε/q). Beyond prime moduli, our reductions also work as above for moduli q that do not have any small prime factors (see Section 4 for details). Our reductions also work for general moduli q in some special cases, such as the entries in the secret vector being very small. Otherwise, for general q, our search algorithm instead produces a list of size Õ((B/qε)2 ) of candidate vectors that contains a vector c · x for some 0 < |c| ≤ Õ((B/qε)2 ), where x is the secret vector. If c turns out to be coprime with q, then by trial and error over all elements in the list and all c, we would be able to recover the secret if equipped with an algorithm to verify the solution. When c is not coprime to q, the output of our reduction reveals only partial information about the secret. This is, in fact, a limitation of all known parameter-preserving reductions for the following reason. When q is not prime, an LWE distinguisher could censor substantial information about the secret. For example, if the modulus q is even, the distinguisher might base its decision only on the value of the instance reduced modulo q/2. The output of the distinguisher would then be identical for every pair of secrets congruent modulo q/2. All known parameter-preserving 3

reductions, including ours, either leave the secret intact or modify it by an affine transformation. Such reductions can therefore at best recover the secret up to congruencies modulo small factors of q. Bogdanov et al. [BGM+ 16, Lemma 4] point out a related limitation in a step of their reduction from search LWE to decision LWR. Open Problems. Neither our algorithm nor that of Micciancio and Mol [MM11] runs in time poly(n) in a parameter setting where the error magnitude is both ω(poly(n)) and o(q/poly(n)). Ideally, we would like to have a parameter-preserving reduction whose complexity scales only with polylog(q) for all noise parameter settings. We do not see a fundamental barrier to such a reduction, but it seems out of the reach of existing techniques. The other open problem is to perform exact secret recovery reduction when q is an arbitrary composite modulus, without any restrictions on the secret x.

1.2

Technical Overview

In this subsection, we first analyse why most existing reductions have a complexity that scales linearly with the size of the modulus. Then we discuss how [MM11] achieves a sample-preserving reduction that scales with the size of the error. Finally, we introduce our reduction technique. Prior Reductions. Regev’s initial reduction for LWE [Reg09] uses a coordinate-guessing technique to recover the secret. Make a guess g ∈ Zq for the first co-ordinate of secret x1 . For each sample (a, ⟨a, x⟩+ e), it is modified to (a+(b, 0, . . . , 0), ⟨a, x⟩+e +b·g) where b is randomly sampled from Zq . If g = x1 , then the distribution stays the same. Otherwise, it becomes random. Because the reduction has to iterate through all possible guesses, the reduction complexity grows with the size of the domain. Later works by [Pei09, ACPS09, MP12] extend this technique to support larger modulus q = pe11 · · · pekk . The rough idea is to use the Chinese Remainder Theorem and guess the value of the secret moduloP the small primes. Therefore, the complexity of the reduction has a polynomial dependence on i (pi + ei ). Micciancio and Mol obtain a sample-preserving reduction [MM11] using an approach analogous to the sample-preserving reduction for LPN with q = 2 by Applebaum, Ishai and Kushilevitz [AIK09]. The main idea is to use the distinguisher to construct a weak inner product predictor P(y) that “predicts” ⟨y, x⟩ mod q, where y ∈ Znq is an input and x is the secret. This can be done by transforming (A, Ax + e) to (A + ry ⊤ , Ax + e + rg) where r is a random vector from Zm q and g ∈ Fq is a guess for the value ⟨y, x⟩. If g = y ⊤ x, then the distribution stays the same. Otherwise, it becomes random. The predictor P performs this transformation, runs the LWE distinguisher on the resulting instance, and outputs whatever it outputs. They show that this weak predictor P(y) has significant Fourier weight at x, and use the learning algorithm from Akavia, Goldwasser and Safra [AGS03] to recover its heavy Fourier coefficients, and thus the secret. Making a guess for the value of ⟨y, x⟩ mod q degrades the advantage by 1/q, which causes the overall learning algorithm to have a running time polynomial in q. To avoid this polynomial dependency on the modulus, they use the equivalence of LWE and Knapsack and instead construct a predictor for ⟨y, e⟩, where e is the error vector. The domain of the predictor P(y) is changed to y ∈ Zm p , where p is a prime and p ≥ max ei , the output is then P(y) = ⟨y, e⟩ mod p. This prime p scales with the error size and not with the original modulus q. When each term of the yi is at most p, the predictor guessing range for g = ⟨y, e⟩ (without modulo p) is reduced to p · m · maxi ei .

4

They will make a guess g ∈ [0, p · m · maxi ei ] for the value of ⟨y, e⟩ without modulo p. The loss in advantage is then a factor of 1/poly(p, m). Running the learning algorithm on such a predictor has running time polynomial in poly(p, log q). Ultimately, existing known reductions involve iterating through all possible guesses for some secret value, which incurs a reduction complexity that scales linearly with the size of the domain of this value (q in the case of [Reg09], |e|∞ in the case of [MM11], etc.). If iteration through the domain is used in the reduction, it will be difficult to obtain a reduction that runs in time polylogarithmic in the size of the modulus, secret and error. Threshold Distinguisher. To obtain a better dependence on q, we would need to use the singlebit output of the distinguisher more effectively than to rule out just one possible guess each time. Ideally, we hope that a single query to the distinguisher would split the search space in half, similar to a binary search. Consider a distinguishing algorithm D for the Noisy Linear Equation problem that takes as input (A, R(Ax)) for some A ∈ Zm×n and x ∈ Znq , and outputs a bit from {−1, 1}. We use this to q construct an algorithm P that takes as input (A, R(Ax)) and also a vector y ∈ Znq , and somehow signals whether |⟨y, x⟩q | ≤ B or |⟨y, x⟩q | > B, for some parameter B. The closer B is to q/2, the better, because that reveals more information about inner produce ⟨y, x⟩, and thus the secret x. To see how the construction is done, consider taking the input (A, R(Ax)) and adding vy ⊤ ∈ Zm×n to the matrix, where v ← {0, 1}m . In other words, the input becomes q (A + vy ⊤ , R(Ax)) Since A is random, this distribution is essentially (A + vy ⊤ , R(Ax)) ≡ (A, R(Ax − vy ⊤ x)) If y ⊤ x = |⟨y, x⟩q | ≤ B is small, this is like adding a small vector to the already noisy R(Ax). If the noise function R absorbs it, then the distribution is close to the noisy linear equations distribution. (A, R(Ax − vy ⊤ x)) ≈ (A, R(Ax)) Otherwise, if y ⊤ x = |⟨y, x⟩q | is large, it overwhelms the noise. And if we add many such vy ⊤ to A, it essentially becomes randomised and independent of R(Ax). Unfortunately, we cannot afford to set B = q/2 because it will overwhelm the noise in most natural noise distributions. The actual B that we use is the largest B such that for any vector z whose elements have magnitude at most B, the statistical distance between R(Ax + z) and R(Ax) is bounded by O(ε). In the proof, starting with the observation about adding vy ⊤ mentioned above, we will use a hybrid argument to construct the algorithm P. Informally, what we will show is the following (Section 3.1): Pr[P(y, A, R(Ax)) = 1| |⟨y, x⟩q | ≤ B] ≥ Ω̃(ε) − Pr[P(y, A, R(Ax)) = 1| |⟨y, x⟩q | > B] Where y ← Znq , A ← Zm×n , x ← Znq q

5

Heavy Fourier Coefficients. Just having P is still not enough to recover the secret x. As we would like to have a sample-preserving reduction, we use an idea similar to [MM11, BGM+ 16], where the information about x is obtained by looking into the Fourier coefficients of P. We show that for a good fixed input (A, x, R(Ax)), the function P(y) = P(y, A, R(Ax)) has a heavy Fourier coefficient at some character c · x, where c is a small integer and x is the secret of the noisy linear equations. We can then recover a list containing c · x with the algorithm of Akavia, Goldwasser, and Safra [AGS03] (Section 3.6). To analyse the Fourier spectrum of P, we use an intermediate threshold function S to isolate the important Fourier characters (Definition 3.6). The function S is defined as ( −1 if |⟨y, x⟩q | ≤ B S(y) = 1 otherwise with y being the input vector, and x being the secret of the noisy linear equations. Because of the properties of P described earlier, we can show that P is correlated with S (Section 3.3). E [(P(y) − µP )(S(y) − µS )] ≥ Ω̃(

Bε ) q

where µP = E [P ] and µS = E [S]. This correlation implies that P must have some non-negligible Fourier weight on the heavy Fourier characters of S. By definition of S, it only has non-zero Fourier coefficients at multiples of x. Furthermore, we show that the Fourier weight of S concentrates on the characters c · x where c is small (Section 3.4). Due to their correlation, this implies that P also contains at least one heavy Fourier coefficient at a character c · x where c is small. Recovering the Secret Finally, if q is a prime or c turns out to be coprime with q, we can go through every element in the output list and try every possible c. Since the list and |c| are bounded by poly(q/Bε), this process finishes in time that grows polynomially with q/Bε. If a verification algorithm exists, we can check each answer candidate and return the correct one. Alternatively, randomly pick an element from the list and choose a random c, incurring some loss in the success probability.

1.3

Paper Outline

In Section 2, we present the notation and technical tools used throughout the paper. In Section 3, we prove the main theorem. In Section 4, we derive various corollaries of our main theorem, including the reductions for LWE and LWR.

2

Preliminaries

Notation We use xi to denote the i-th bit of the binary string (vector) x and Ai to denote the i-th row of the matrix A. Let Fp denote the order-p prime field. Let Zq denote the integer ring modulo q. Write [n] := {1, 2, . . . , n}. Write ⌊x⌉ as the number x rounded to the nearest integer. Write ⟨y, x⟩q ∈ Zq as the inner product of vectors x and y modulo q. Define |x|, where x ∈ Zq , as |x| = min(x′ , x′ − q) where x′ is x lifted to the integer ring. 6

Distributions Denote D1 ≡ D2 if the distributions D1 and D2 are the same. Let U (D) be the uniform distribution on the set D. 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 from U (D). Definition 2.1 (Discrete Gaussian Distribution). Define Dσ as the discrete Gaussian distribution over integers with parameter σ > 0 and centre at 0. ρσ (x) = exp(−x2 /2σ 2 ) X Pr[Dσ = x] = ρσ (x)/ ρσ (y) y∈Z

Definition 2.2 (Noisy Linear Equations). Let n, m, p, q ∈ Z+ . For sample count m, secret dim mension n, and a noise function R : Zm q → Zp , algorithms S and D are said to have advantage ε ∈ [0, 1] in solving the Search and Decision Noisy Linear Equations problem, respectively, if they satisfy the following conditions: • Search: Suppose A ← Zm×n , x ← Znq , S recovers the secret x with probability at least ε: q Pr[S(A, R(Ax)) = x] ≥ ε. , x ← Znq , b ← Zm • Decision: Suppose A ← Zm×n q , D distinguishes samples from uniform with q advantage at least ε: |Pr[D(A, R(Ax)) = 1] − Pr[D(A, R(b)) = 1]| ≥ ε. Definition 2.3 (Learning With Error (LWE)). The Learning With Error (LWE) problem with m noise parameter σ is a Noisy Linear Equations problem with the noise function R : Zm q → Zq defined as R(y) = (y + e) mod q, where e ← Dσm . Definition 2.4 (Learning With Rounding (LWR)). The Learning With Rounding (LWR) problem m with modulus p < q is a Noisy Linear Equations problem with the noise function R : Zm q → Zp   p ′ defined, for each i ∈ [m], as R(y)i = y mod p, where yi′ is yi lifted to the reals. q i

2.1

Coprime secret

Throughout the proof, we will only consider secrets of the noisy linear equations (that is, the vector x in Definition 2.2) that satisfy gcd(x, q) = gcd(x1 , . . . , xn , q) = 1. This is a mild assumption when we sample x at random because the event of obtaining such a secret occurs with very high probability. We can precisely calculate the probability of this event using the Chinese Remainder Theorem. Y 1 1 log q Pr[gcd(x1 , . . . , xn , q) = 1] = (1 − n ) ≥ (1 − n )log q ≥ 1 − n p 2 2 p|q p is prime

which is a value that is exponentially close to 1. Definition 2.5. Define P(Znq ) = {x ∈ Znq | gcd(x1 , . . . , xn , q) = 1} Proposition 2.6. For any q ∈ Z≥2 , T V (U (P(Znq )), U (Znq )) ≤ 7

log q 2n

2.2

Noise Tolerance

In this subsection, we show that both LWE noise and LWR noise can absorb small deviations in the noisy codeword (which is the term we shall use to refer to Ax). Specifically, we will be adding a vector v ← {0, B}m to the noisy codeword of LWE and LWR, where B is something much smaller than the noise magnitude. We show that the total variation distance to the original distribution will still be close despite adding v. This property is essential for our search-to-decision reduction. m Definition 2.7 (Noise Tolerance). Let n, m, p, q, B ∈ Z+ and ε ∈ [0, 1]. Let R : Zm q → Zp be a noise function. We say that R is (B, ε)-noise tolerant if for every |b| ≤ B and every v ∈ {0, b}m ,   T V (A, R(Ax)), (A, R(Ax + v)) ≤ ε

where A ← Zm×n and x ← P(Znq ). q ′ Let B (R, ε) ∈ Z be the largest B such that such that R is (B, ε)-noise tolerant. The tolerance bound function is defined as B(R, ε) = min(B ′ (R, ε), ⌊q/4 − 1⌋). Proposition 2.8 (LWE Noise Tolerance). Let n, m, q, B ∈ Z+ , σ ∈ R, and R be the LWE noise function with noise parameter σ. Suppose A ∈ Zm×n , x ∈ Znq , v ∈ {0, b}m where |b| ≤ B, then q   B √m T V (A, R(Ax)), (A, R(Ax + v)) ≤ 2σ √ Which implies B(R, ε) ≥ min(2εσ/ m, ⌊q/4 − 1⌋). Proof. Expanding the noise function R, then by data processing inequality     T V (A, R(Ax)), (A, R(Ax + v)) = T V (A, Ax + e), (A, Ax + e + v) ≤ T V (e, e + v) Where e ← Dσm and addition is done over Z. Without loss of generality, assume that b ≥ 0. Looking at a single dimension i ∈ [m] such that vi = b, and write down the KL divergence X Pr[b + ei = z] DKL (b + ei ∥ ei ) = Pr[b + ei = z] log Pr[ei = z] z∈Z

=

X

=

X

Pr[b + ei = z] log exp(

z∈Z

Pr[b + ei = z]

z∈Z

(z)2 (z − b)2 − ) 2σ 2 2σ 2

2bz − b2 2σ 2

Let Y = b + ei , and simplify the statement above   X 2bz − b2 2bY − b2 2b E [Y ] − b2 b2 B2 Pr[Y = z] = E = = ≤ Y ∼b+Dσ 2σ 2 2σ 2 2σ 2 2σ 2 2σ 2 z For m dimensions, Pinsker’s Inequality bounds the total variation by r r √ 1 m B m T V (e + v, e) ≤ DKL (e + v ∥ e) = DKL (ei + vi ∥ ei ) ≤ . 2 2 2σ 8

Proposition 2.9 (LWR Noise Tolerance). Let n, m, p, q ∈ Z+ , p < q and R be the LWR noise function with rounding modulus p. Suppose A ← Zm×n , x ∈ P(Znq ), v ∈ {0, b}m where |b| ≤ B < q q/p, then   pBm T V (A, R(Ax)), (A, R(Ax + v)) ≤ q Which implies B(R, ε) ≥ min(qε/pm, ⌊q/4 − 1⌋). Proof. Without loss of generality, assume that b ≥ 0. Let E be the event that R(Ax) = R(Ax + v). This event happens when every value in Ax is far away from the boundary where rounding occurs.   p ′ ′ In other words, for each coordinate value (Ax)i , lifted to the reals (Ax)i , we have that (Ax)i ≡ q   p ((Ax)′i + b) mod p. The total variation distance can then be upper-bounded using this event. q   T V (A, R(Ax)), (A, R(Ax + v)) ≤ Pr[Ē] As gcd(x, q) = 1 and A is randomly sampled, Ax is distributed just as a random vector over Zm q . For a list of elements in Zq that round to the same element in Zp , only the last b elements in the list would round to a different element after adding the value b, while the rest stay the same. This means that at most pB elements in Zq will change value after addition. So for a random element in Zq the probability that it falls into this boundary region is at most pB/q. By union bound, the probability of Ē is upper bounded.   pBm . T V (A, R(Ax)), (A, R(Ax + v)) ≤ Pr[Ē] ≤ q

2.3

Fourier Analysis

Here we describe the basics of Fourier Analysis and establish the choice of basis in the paper. Denote ωq = e−2πi/q . Definition 2.10 (Fourier Transform). Let n, q ∈ Z+ . The Fourier transform of a function S : Fnq → C is another function Ŝ : Fnq → C defined as h i Ŝ(χ) = E m S(y)ωq⟨χ,y⟩ y←Zq

Proposition 2.11 (Inverse Fourier Transform). Let Ŝ be the Fourier transform of S : Fnq → C. Then X S(y) = Ŝ(χ)ωq−⟨χ,y⟩ χ∈Zm q

Proposition 2.12 (Parseval–Plancherel). Let n, q ∈ Z+ , functions P, S : Fm q →C   h i X X P̂ (χ)ωq−⟨χ,y⟩ )( Ŝ(χ)ωq⟨χ,y⟩ ) E P (y)S(y) = E ( y←Zn q

y←Zn q

=

X

χ∈Zm q

P̂ (χ)Ŝ(χ)

χ∈Zm q

9

χ∈Zm q

In particular, this implies the following for any such functions P h i X 2 P̂ (χ) E n |P (y)|2 =

y←Zq

3

χ∈Zm q

Reduction

This section describes the proof of the main theorem. m Theorem 3.1. Consider any n, m, p, q ∈ Z+ , a noise function R : Zm q → Zp , and any ε ∈ (0, 1]. Let t = ⌈4 log(qm/ε)⌉, denote by B the noise tolerance bound B(R, ε/4t), and set ε′ = (Bε/2qt). Suppose there exists an algorithm for the Decision Noisy Linear Equations problem over Zq with sample count m, secret dimension n, and noise function R, and that the algorithm runs in time T and has advantage ε. Then there exists an algorithm as follows. Given an input (A, R(Ax)), where A ← Zm×n and q n ′ 2 x ← P(Z  q ), itoutputs a list of size Õ(1/(ε ) ) that contains c · x for some c ∈ Zq \ {0} such that |c| ≤ 32/(ε′ )2 . This algorithm runs in time poly(n, m, log q, 1/ε′ , T ) and successfully outputs such a list with probability Ω(ε′ ).

Proof overview is described in Section 1.2 Section Outline In Section 3.1 and Section 3.2, we will talk about the threshold distinguisher. Section 3.3 is on the correlation of P and S. Section 3.4 and Section 3.5 are on the concentration of the Fourier weight of S. Finally, in Section 3.6 we state the algorithm from [AGS03] to learn heavy Fourier coefficients.

3.1

Threshold Distinguisher

In this subsection, we describe the construction of a threshold distinguisher P that can distinguish whether |⟨y, x⟩q | ≤ B or |⟨y, x⟩q | > B. Note that the inner product is performed over Zq . m Lemma 3.2. Let n, m, p, q ∈ Z+ , ε ∈ (0, 1], a noise function R : Zm q → Zp , t = ⌈4 log(qm/ε)⌉ , B = B(R, ε/4t). Suppose there exists an algorithm D for the Decision Noisy Linear Equations problem over Zq with sample count m, secret dimension n, noise function R, that has advantage ε. Then there exists an algorithm P that outputs a value in {−1, 1} such that

Pr[P(y, A, R(Ax)) = 1| |⟨y, x⟩q | ≤ B] − Pr[P(y, A, R(Ax)) = 1| |⟨y, x⟩q | > B]

≥ ε/4t

Where y ← Znq , A ← Zm×n , x ← P(Znq ). q Proof. The construction of P is as follows: Algorithm P: On input (y, A, b = R(Ax)) and Decision algorithm D, 1 Sample k ← [0, t − 1] and v ← {0, 1}m 2 Sample matrices Vk ← {0, 1}m×k and Yk ← Zk×n q 3 Output D(A + Vk Yk + vy ⊤ , b) 10

We use the hybrid argument to prove the lemma. First, define the hybrid distribution Hk over Zm×n × Zm q p as Hk = (A + Vk Yk , R(Ax)) Claim 3.3. For any k ∈ Z≥0 , let H = (A + Vk Yk + vy ⊤ , R(Ax)). • If |⟨y, x⟩q | ≤ B, then T V (H, Hk ) ≤ ε/4t • If no condition is imposed, then H ≡ Hk+1 Proof. Suppose that |⟨y, x⟩q | ≤ B, rewrite H ≡ (A + Vk Yk + vy ⊤ , R(Ax)) ≡ (A + Vk Yk , R(Ax − vy ⊤ x)) The vector vy ⊤ x = v⟨y, x⟩q is uniformly random in {0, ⟨y, x⟩q }m . By the definition of noise tolerance (Definition 2.7), and the fact that B = B(R, ε/4t), T V (H, Hk ) ≤ ε/4t On the other hand, if no condition is imposed on y, it is uniformly random and H ≡ (A + Vk Yk + vy ⊤ , b) ≡ (A + Vk+1 Yk+1 , b) ≡ Hk+1 . It is clear from the definition that H0 is distributed as a Noisy Linear Equation instance. We claim that once t is large enough, the terminal hybrid Ht is distributed as a random instance. , b ← Zm Claim 3.4. (Terminal hybrid). Let t = ⌈4 log(qm/ε)⌉, A ← Zm×n q , q   T V Ht , (A, R(b)) ≤ ε2 /2qm ≪ ε We defer the proof of the claim to the next section (Section 3.2). With this claim, we can then use hybrid argument to conclude a ε/2t advantage in distinguishing between Hk and Hk+1 where k ← [0, t − 1]. Proposition 3.5. Pr k←[0,t−1]

[D(Hk ) = 1] −

Pr k←[0,t−1]

[D(Hk+1 ) = 1] ≥ ε/2t

Proof. Standard hybrid argument with Claim 3.4. Details deferred to Section A.1 Let H be the distribution sent to the decision algorithm D in line 3 of the algorithm P. Using Claim 3.3 and Proposition 3.5, we obtain a distinguisher that behaves differently under the condition of |⟨y, x⟩q | ≤ B and no condition. i.e. Pr [D(H) = 1 | |⟨y, x⟩q | ≤ B] − Pr n [D(H) = 1] ≥ ε/2t − ε/4t = ε/4t

y←Zn q

y←Zq

Where the loss of ε/4t is from the total variation distance between H and Hk when |⟨y, x⟩q | ≤ B.

11

The condition |⟨y, x⟩q | > B can be imposed on the second term at no cost. Let E be the event that |⟨y, x⟩q | ≤ B. By law of total probability, Pr [D(H) = 1|E] − Pr [D(H) = 1]   = Pr[Ē] · Pr [D(H) = 1|E] − Pr D(H) = 1|Ē Which implies   ε/4t Pr [D(H) = 1|E] − Pr D(H) = 1|Ē ≥ ≥ ε/4t. Pr[Ē]

3.2

Terminal Hybrid

Here, we show the proof of the claim that the terminal hybrid is close to the uniform distribution. Claim 3.4. (Terminal hybrid). Let t = ⌈4 log(qm/ε)⌉, A ← Zm×n , b ← Zm q q , 



T V Ht , (A, R(b)) ≤ ε2 /2qm ≪ ε Proof. Start by writing Ht = (A + V Y, R(Ax)) ≡ (A, R(Ax − V Y x)) Where A ← Zm×n , V ← {0, 1}m×t , Y ← Zt×n q q , x ← P(Zq ). t×n Since Y is a random matrix in Zq , and gcd(x, q) = 1, y = Y x is uniformly random in Zm q , even given x. As every row v of V is a random {0, 1} vector of min-entropy 2−tp , and dot product with y is a universal hash, by the leftover hash lemma [ILL89], (y, ⟨v, y⟩) is 21 q2−t -statistically close to (y, r) for a uniformly random r. By a hybrid argument, the statistical distance between (y, ⟨v1 , y⟩, . . . , ⟨vm , y⟩)

and

(y, r1 , . . . , rm ),

p where vi are the rows of V , is at most m times larger. In particular, V y is 12 m q2−t -close to uniform. By our choice of parameters, this is at most p 1 m q(ε/qm)4 ≤ ε2 /2qm 2

3.3

Correlation With Threshold Function

Lemma 3.2 essentially shows that the algorithm P is correlated with the indicator for the event |⟨y, x⟩q | ≤ B. For analytic purposes it will be convenient to express this correlation in terms of the covariance of P and a random variable defined by sampling the inputs to the following function at random. Definition 3.6 (Threshold Function). Let n, q, B ∈ Z+ . Define S : Znq × Znq → {−1, 1} as ( 1 S(y, x) = −1

if |⟨y, x⟩q | ≤ B otherwise 12

The conversion from difference in conditional expectations to the covariance of ±1-valued random variables is given by the following formula. Lemma 3.7. For any {−1, 1}-valued random variables X and Y , E [(X − µX )(Y − µY )] =

Var(Y ) · (E [X|Y = 1] − E [X|Y = −1]), 2

where µX = E [X], µY = E [Y ]. Proof. We can rewrite the variance of Y in terms of probabilities   Var(Y ) = E Y 2 − E [Y ]2 = 1 − ((1 − Pr[Y = −1]) − Pr[Y = −1])2 = −4 Pr[Y = −1]2 + 4 Pr[Y = −1] = 4 · Pr[Y = −1](1 − Pr[Y = −1]) = 4 Pr[Y = −1] Pr[Y = 1] Expand E [(X − µX )(Y − µY )] using law of total probability, E [(X − µX )(Y − µY )] = E [XY ] − µX µY = E [X|Y = 1] Pr[Y = 1] − E [X|Y = −1] Pr[Y = −1] − (E [X|Y = 1] Pr[Y = 1] + E [X|Y = −1] Pr[Y = −1])µY = E [X|Y = 1] Pr[Y = 1](1 − µY ) + E [X|Y = −1] Pr[Y = −1](−1 − µY ) Substitute µY = Pr[Y = 1] − Pr[Y = −1], then 1 − µY = 2 Pr[Y = −1] and (−1 − µY ) = −2 Pr[Y = 1] Finally with Var(Y ) = 4 Pr[Y = −1] Pr[Y = 1], E [XY ] − µX µY =2 E [X|Y = 1] Pr[Y = 1] Pr[Y = −1] − 2 E [X|Y = −1] Pr[Y = −1] Pr[Y = 1] Var(Y ) (E [X|Y = 1] − E [X|Y = −1]). = 2 Applying Lemma 3.7 to P and S gives the following corollary. Corollary 3.8. Using the same parameter definitions as in Lemma 3.2, E [(P(y, A, R(Ax)) − µP )(S(y, x) − µS )] ≥ (

Bε Var(S) )(ε/4t) ≥ 2 2qt

Where A ← Zm×n , x ← P(Znq ), y ← Znq . q Proof. From Lemma 3.2, without loss of generality, Pr[P(y, A, R(Ax)) = 1|S(y, x) = 1] − Pr[P(y, A, R(Ax)) = 1|S(y, x) = −1] ≥ ε/4t Then the statement follows from Lemma 3.7. The calculation of the variance of S is shown as follows: 2B + 1 2B + 1 4B Var(S) = 4 Pr[S = 1] Pr[S = −1] = 4( )(1 − )≥ q q q Where the last inequality is from B ≤ ⌊q/4 − 1⌋ 13

3.4

Heavy Fourier Coefficients

To analyse the Fourier coefficients of P, it is more convenient to fix the input problem instance (A, x, R(Ax)) to be any good instance. We say an instance (A, x, R(Ax)) is ε-good if E [(P(y, A, R(Ax)) − µP )(S(y, x) − µS )] ≥ ε

y←Zn q

By definition, (P − µP )(S − µS ) takes value in [−4, 4]. By Markov’s inequality (Proposition 3.9), E n [(P(y, A, R(Ax)) − µP )(S(y, x) − µS )] ≥

y←Zq

ε 2

(1)

for a ε/8 fraction of A, x, and R (if randomized). We fix these choices from here on and view P and S as functions of y only. P(y) = P(y, A, R(Ax)) and S(y) = S(y, x) Proposition 3.9. If |X| ≤ 4 and E [X] ≥ ε, then for any random variable Y , we have E [X|Y ] ≥ ε/2 with probability at least ε/8 over Y . Proof. Let E be the set of Y for which E [X|Y ] ≤ ε/2. By the law of total expectation, ε ≤ E [X] ≤ E [X|Y ̸∈ E] Pr(Y ̸∈ E) + E [X|Y ∈ E] ≤ 4 Pr(Y ̸∈ E) + ε/2 so that Pr(Y ̸∈ E) ≥ ε/8. By Plancherel’s formula (see Proposition 2.12), (1) has an equivalent formulation in the Fourier domain: X ε P̂(χ) · Ŝ(χ) ≥ . (2) 2 m χ̸=0

(Ŝ will turn out to be real so we omit complex conjugation.) The function S(y) can be expressed as 2f (⟨y, x⟩)−1, where f : Zq → C is the univariate function 1(|t| ≤ B). Making the substitution t = ⟨y, x⟩ in the Fourier transform of f X f (t) = fˆ(c)ω −ct c∈Zq

gives the Fourier expansion X S(y) = 2fˆ(c) · ω −c⟨y,x⟩ − 1 =

X

2fˆ(c) · ω −⟨y,χ⟩ − 1

χ s.t. χ=c·x

c∈Zq

Comparing this to the inverse Fourier Transform (Proposition 2.11) of S, we have the following observations: • For any χ that is not of the form c · x for some c ∈ Fq , the Fourier coefficients S(χ) is 0. • When c ̸= 0, Ŝ(c · x) = 2fˆ(c). • Ŝ(0n ) = 2fˆ(0n ) − 1 14

Inequality (2) therefore simplifies to X c̸=0

ε P̂(c · x) · fˆ(c) ≥ . 4

(3)

As f is a threshold function, most of its Fourier mass is concentrated on low frequencies (see Figure 1). 0.3 0.2 0.1 0 −0.1 −15

−10

−5

0

5

10

15

Figure 1: Fourier spectrum of f with q = 31 and B = 4. Claim 3.10. Let τ ∈ Z+ and define the light weight set Wl = {c ∈ Zq | |c| > τ }, then X

fˆ(c)

2

≤ 1/2τ

c∈Wl

Claim 3.11. Let τ ∈ Z+ and define the heavy weight set Wh = {c ∈ Zq | 0 < |c| ≤ τ }, then X

fˆ(c) ≤ 1 + ln τ

c∈Wh

Proofs of the two claims are deferred to the next section (Section 3.5). We now use these to show that (3) forces a heavy Fourier coefficient of the form P̂(c · x).   Lemma 3.12. Assuming (1), there exists c ∈ Zq such that c ̸= 0, |c| ≤ 32/ε2 and P̂(c · x) ≥

ε . 16 ln(14/ε)

  Proof. Set τ to 32/ε2 . As explained in the text above, (1) is equivalent to (3). The sum in (3) splits as X X P̂(c · x)fˆ(c) + P̂(c · x)fˆ(c) ≥ ε/4. c∈Wh

c∈Wl

15

By the Cauchy-Schwarz inequality, Parseval’s formula, and Claim 3.10, s s X X X 2 2 ˆ P̂(c · x)f (c) ≤ P̂(c · x) fˆ(c) c∈Wl

c∈Wl

≤

c∈Wl

s X p 2 2 fˆ(c) ≤ ε2 /64 = ε/8 E n [P(y) ]

r

y←Zq

c∈Wl

Therefore, the sum over the heavy terms is lower bounded by X P̂(c · x) · fˆ(c) ≥ ε/8 c∈Wh

By Claim 3.11, the sum of all |fˆ(c)| terms is at most ln τ . Therefore at least one of the terms P̂ (c · x) must have magnitude at least ε/8 ε ε/8 = ≥ 2 1 + ln τ ln ⌈64e/ε ⌉ 16 ln(14/ε) by our choice of τ .

3.5

Fourier analysis of f

Next, we prove Claims 3.10 and 3.11. We will make use of the following proposition. Proposition 3.13. For c ∈ Zq , fˆ(c) ≤

1 . q| sin(cπ/q)|

Proof. The Fourier coefficients of f are B   1 X 1(|t| ≤ B) · ωqc·t = ωqc·t t←Zq q

fˆ(c) = E

t=−B

Using the geometric progression formula, B

c(2B+1)

1 X c·t ωq−cB (1 − ωq ωq = q q(1 − ωqc )

)

c(2B+1)/2

=

ωq−cB ωq

c/2 qωq

t=−B

−c(2B+1)/2

·

(ωq

c(2B+1)/2

− ωq

)

−c/2 c/2 (ωq − ωq )

Since ωq−a − ωqa = −2i sin(2πa/q), we can simplify to B

1 X c·t sin(c(2B + 1)π/q) ωq = q q sin(cπ/q) t=−B

Since the denominator is always a positive number when c ∈ Zq and the numerator is within range [−1, 1], |fˆ(c)| ≤ 1/q| sin(cπ/q)|. Claim 3.10. Let τ ∈ Z+ and define the light weight set Wl = {c ∈ Zq | |c| > τ }, then X

fˆ(c)

2

c∈Wl

16

≤ 1/2τ

Proof. From Proposition 3.13, X

fˆ(c)

2

≤

1 X 1 · q2 sin(cπ/q)2 c∈Wl

c∈Wl

As sin2 is an even function, ⌊q/2⌋ 1 1 2 X 1 X = 2 2 2 q sin(cπ/q) q sin(cπ/q)2 c=τ +1

c∈Wl

As the sin function is concave downward from 0 to π/2, the function is lower-bounded by the line that connects the origin and the point at (π/2, 1), i.e., sin t ≥ 2t/π. ⌊q/2⌋ ⌊q/2⌋ ⌊q/2⌋ 2 X 1 2 X q2 1 X 1 ≤ 2 = q2 sin(cπ/q)2 q 4c2 2 c2 c=τ +1

c=τ +1

c=τ +1

Because 1/t2 is a decreasing function for t > 0, we can apply the integral bound to obtain Z ⌊q/2⌋ 1 X 1 1 q/2 1 1 ≤ dc ≤ . 2 2 2 c 2 τ c 2τ c=τ +1

Claim 3.11. Let τ ∈ Z+ and define the heavy weight set Wh = {c ∈ Zq | 0 < |c| ≤ τ }, then X fˆ(c) ≤ 1 + ln τ c∈Wh

Proof. From Proposition 3.13, using sin t ≥ 2t/π in the relevant range, τ

X c∈Wh

fˆ(c) ≤

X 1 1 =2 q| sin(cπ/q)| q sin(cπ/q) c=1 c∈Wh Z τ τ X 1 1 ≤ ≤1+ dc ≤ 1 + ln τ. c 1 c X

c=1

3.6

Learning Significant Fourier Coefficients

With Lemma 3.12, we know that there exists a small |c| such that the Fourier coefficient P̂(c · x) is large, say at least α. To find c · x, we use the Learning Significant Fourier Coefficients algorithm from Akavia, Goldwasser and Safra [AGS03] to find all Fourier Coefficients with magnitude at least α. First, we show that the number of such coefficients is at most 1/α2 . Proposition 3.14. Let α ∈ (0, 1], W = {χ ∈ Znq | P̂(χ) ≥ α}, then |W| ≤ 1/α2   Proof. Since P : Znq → {−1, 1}, Ey←Znq P(y)2 = 1. So X X X   |W|α2 = α2 ≤ P̂(χ)2 ≤ P̂(χ)2 = E n P(y)2 ≤ 1 χ∈W

χ∈W

χ∈Zn q

17

y←Zq

Theorem 3.15 ([AGS03]). Let α ∈ (0, 1]. There exists an algorithm that, given a function P : Znq → {−1, 1} and α, outputs W = {χ ∈ Znq | P̂(χ) ≥ α}, except with probability o(α), and runs in time poly(n, log q, 1/α).

3.7

Proof of Theorem 3.1

From Lemma 3.2 and Corollary 3.8, we get an algorithm P such that E [(P(y, A, R(Ax)) − µP )(S(y, x) − µS )] ≥

Bε 2qt

Let ε′ = (Bε/2qt). With probability at least ε′ /8 we get a ε′ /2-good instance (A, In a  x, R(Ax)).  good instance, Lemma 3.12 says that there exists c ∈ Zq such that c ̸= 0, |c| ≤ 32/(ε′ )2 and P̂(c · x) ≥

ε′ = α. 16 ln(14/ε′ )

Then, we run the [AGS03] algorithm from Theorem 3.15 on P with α to obtain a list that contains c · x. By Proposition 3.14, this list has size at most Õ(1/(ε′ )2 ). The final runtime of the algorithm is poly(n, m, log q, 1/ε′ , T ), where T is the running time of the algorithm for the Decision Noisy Linear Equations problem. The success probability of the algorithm depends on whether we obtain an ε′ /2-good instance and whether the [AGS03] algorithm from Theorem 3.15 returns the list correctly. By the union bound, the algorithm will succeed with probability ε′ /8 − o(ε′ ) = Ω(ε′ )

4

Corollaries

We can derive corollaries from Theorem 3.1 for the specific noise functions corresponding to LWE and LWR. From Proposition 2.6, the total variation distance of U (P(Znq )) and U (Znq ) is small. Therefore, we write the following with the distribution of the secret being U (Znq ) instead. Corollary 4.1 (Partial Secret Recovery for LWE/LWR). Consider any n, m, q ∈ Z+ , and any ε ∈ (0, 1]. Consider the LWE/LWR problem over Zq with sample count m, secret dimension n. √ • Under LWE noise with parameter σ ∈ R, σ < q, set ε′ = σε2 /q m, or, • Under LWR noise with rounding modulus p ∈ Z+ , p < q, set ε′ = ε2 /pm Suppose there exists an algorithm for the corresponding Decision LWE/LWR that runs in time T and has advantage ε. Then there exists an algorithm that, given the problem instance, outputs a list of size Õ(1/(ε′ )2 ) that contains c · x, where x is the solution, for some c ∈ Zq \ {0} such that |c| ≤ Õ(1/(ε′ )2 ). This algorithm runs in time poly(n, m, log q, 1/ε′ , T ) and successfully outputs such a list with probability Ω̃(ε′ ). √ Proof. For LWE, by Proposition 2.8, set B = min(2εσ/ m, ⌊q/4 − 1⌋). For LWR, by Proposition 2.9, set B = min(qε/pm, ⌊q/4 − 1⌋). The rest follows from Theorem 3.1.

18

We note that, assuming that the search problem and decision problem are defined over the same secret distribution, our reduction also applies to secret distributions other than uniform over Zm q , as long as the secret x satisfies gcd(x1 , . . . , xn , q) = 1 with very high probability.

4.1

Exact Secret Recovery

So far, we have shown that our algorithm can compute a list of vectors that contains some small multiple of the secret. Under certain conditions, the exact secret can be recovered from this list. We describe a few sufficient conditions for the recovery. The first requirement for recovery is the existence of an efficient verification algorithm V for the Noisy Linear Equations problem. Definition 4.2 (Verification Algorithm). A verification algorithm V for a Noisy Linear Equations problem is an algorithm in which the following holds with high probability over A, x, and R: ( 1 if x′ = x ′ n ′ ∀x ∈ Zq , V(x , A, R(Ax)) = −1 if x′ ̸= x For typical Noisy Linear Equations problems, such a verification algorithm exists when m is large enough, and the error is small enough for unique recovery. In particular, a verification algorithm for LWE exists when n log q ≪ m log(q/σ), while it exists for LWR when n log q ≪ m log p. The next requirement is to be able to recover x ∈ Znq given c · x and c. Definition 4.3 (Recovery Algorithm). A recovery algorithm G for a Noisy Linear Equations problem is an algorithm such that, for all x, and c ∈ Zq \ {0}: G(c · x, c) = x Some settings were such a G exists are when q is a prime, or if we are guaranteed that c·maxi xi ≤ q. For example, when the secret x is uniform over {0, 1}n and |c| < q (Binary secret LWE problem [BLP+ 13]). Since the algorithm’s output list size is Õ(1/(ε′ )2 ) and |c| ≤ Õ(1/(ε′ )2 ), in time Õ(1/(ε′ )4 ) we can try all candidates c on every element in the output list. If G returns x on any one of them, the verification algorithm V would tell us that we got the right answer. Suppose a verification algorithm does not exist, but G exists. We can still perform recovery at the cost of lowering the success probability by randomly choosing an element from the output list and randomly choosing a c. The success probability of the search algorithm would then become Ω((ε′ )5 ). Corollary 4.4 (Search-to-Decision Reduction for LWE/LWR). Consider any n, m, q, p ∈ Z+ , a m noise function R : Zm q → Zp , and any ε ∈ (0, 1]. For the LWE/LWR over Zq with sample count m, secret dimension n, √ • Under LWE noise with parameter σ ∈ R, σ < q, set ε′ = σε2 /q m 19

• Under LWR noise with rounding modulus p ∈ Z+ , p < q, set ε′ = ε2 /pm Suppose there exists a Decision algorithm that runs in time TD and has advantage ε, and a Recovery algorithm that runs in time TG . Then there exists a Search algorithm that runs in time poly(n, m, log q, 1/ε′ , TD , TG ) with success probability at least Ω̃((ε′ )5 ). Furthermore, if a Verification algorithm that runs in time TV exists, there exists a Search algorithm that runs in time poly(n, m, log q, 1/ε′ , TD , TV , TG ) with success probability at least Ω̃(ε′ ). Specifically, this applies to LWE when n log q ≪ m log(q/σ), σ ≪ o(p) and LWR when n log q ≪ m log p, p ≪ q

5

Acknowledgments

This work was supported by the National Research Foundation, Singapore, under its NRF Fellowship programme, award no. NRF-NRFF14-2022-0010 and by an NSERC Discovery Grant. AI tools were used as typing assistants for grammar and basic editing.

References [AA16]

Jacob Alperin-Sheriff and Daniel Apon. Dimension-preserving reductions from LWE to LWR. IACR Cryptol. ePrint Arch., 2016:589, 2016.

[ACPS09]

Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In Shai Halevi, editor, Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings, volume 5677 of Lecture Notes in Computer Science, pages 595–618. Springer, 2009.

[AGS03]

Adi Akavia, Shafi Goldwasser, and Shmuel Safra. Proving hard-core predicates using list decoding. In 44th Symposium on Foundations of Computer Science, FOCS 2003, Cambridge, MA, USA, October 11-14, 2003, Proceedings, pages 146–157. IEEE Computer Society, 2003.

[AIK09]

Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography with constant input locality. J. Cryptol., 22(4):429–469, 2009.

[AKPW13] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs. Learning with rounding, revisited - new reduction, properties and applications. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 57–74. Springer, 2013. [BFKL93] 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, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings, volume 773 of Lecture Notes in Computer Science, pages 278–291. Springer, 1993. 20

[BGM+ 16] Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, and Alon Rosen. On the hardness of learning with rounding over small modulus. In Eyal Kushilevitz and Tal Malkin, editors, Theory of Cryptography - 13th International Conference, TCC 2016A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part I, volume 9562 of Lecture Notes in Computer Science, pages 209–224. Springer, 2016. [BLMR13] Dan Boneh, Kevin Lewi, Hart William Montgomery, and Ananth Raghunathan. Key homomorphic prfs and their applications. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 410–428. Springer, 2013. [BLP+ 13]

Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardness of learning with errors. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 575–584. ACM, 2013.

[BP14]

Abhishek Banerjee and Chris Peikert. New and improved key-homomorphic pseudorandom functions. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I, volume 8616 of Lecture Notes in Computer Science, pages 353–370. Springer, 2014.

[BPR12]

Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom functions and lattices. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, volume 7237 of Lecture Notes in Computer Science, pages 719–737. Springer, 2012.

[BV11]

Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 97–106. IEEE Computer Society, 2011.

[ILL89]

Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-random generation from one-way functions (extended abstracts). In David S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, pages 12–24. ACM, 1989.

[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 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science, pages 465–484. Springer, 2011.

[MP12]

Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology

21

- EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, volume 7237 of Lecture Notes in Computer Science, pages 700–718. Springer, 2012. [Pei09]

Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 333–342. ACM, 2009.

[Reg09]

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1–34:40, 2009.

[SHTY25] Kyohei Sudo, Keisuke Hara, Masayuki Tezuka, and Yusuke Yoshida. Quantum searchto-decision reduction for the LWE problem. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 108(2):104–116, 2025.

A

Supplementary Proofs

A.1

Hybrid Argument

Proposition 3.5. Pr k←[0,t−1]

[D(Hk ) = 1] −

Pr k←[0,t−1]

[D(Hk+1 ) = 1] ≥ ε/2t

  Proof of Proposition 3.5. Using T V Ht , (A, R(b)) ≤ ε2 /2qt from Claim 3.4, Pr i←[0,t−1]

=

t−1 X 1 i=0

=

t

[D(Hi ) = 1] −

Pr[D(Hi ) = 1] −

Pr i←[0,t−1]

[D(Hi+1 ) = 1]

1 Pr[D(Hi+1 ) = 1] t

1 (Pr[D(H0 ) = 1] − Pr[D(Ht ) = 1]) t

≥ε/t − ε2 /2qt ≥ ε/2t

22

Related documents

• Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli#1297265
• Deriving Approximate Message Passing from the Convex Gaussian Min-Max Theorem#1342543
• Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits#1202286
• A method for the solution of certain non-linear problems in least squares#6874
• Strongly Refuting Semirandom Linear Systems in Subexponential Time#1078123