Classical Hardness of Learning with Errors

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.


Introduction
Over the last decade, lattices have emerged as a very attractive foundation for cryptography. The appeal of lattice-based primitives stems from the fact that their security can be based on worst-case hardness assumptions, that they appear to remain secure even against quantum computers, that they can be quite efficient, and that, somewhat surprisingly, for certain advanced tasks such as fully homomorphic encryption no other cryptographic assumption is known to suffice.
Virtually all recent lattice-based cryptographic schemes are based directly upon one of two natural average-case problems that have been shown to enjoy worst-case hardness guarantees: the short integer solution (SIS) problem and the learning with errors (LWE) problem. The former dates back to Ajtai's groundbreaking work [Ajt96], who showed that it is at least as hard as approximating several worst-case lattice problems, such as the (decision version of the) shortest vector problem, known as GapSVP, to within a polynomial factor in the lattice dimension. This hardness result was tightened in followup work (e.g., [MR04]), leading to a somewhat satisfactory understanding of the hardness of the SIS problem. The SIS problem has been the foundation for one-way [Ajt96] and collision-resistant hash functions [GGH96], identification schemes [MV03,Lyu08,KTX08], and digital signatures [GPV08,CHKP10,Boy10,MP12,Lyu12].
Our focus in this paper is on the latter problem, learning with errors. In this problem our goal is to distinguish with some non-negligible advantage between the following two distributions: ((a i , a i , s + e i mod q)) i and ((a i , u i )) i , where s is chosen uniformly from Z n q and so are the a i ∈ Z n q , u i are chosen uniformly from Z q , and the "noise" e i ∈ Z is sampled from some distribution supported on small numbers, typically a (discrete) Gaussian distribution with standard deviation αq for α = o(1).
Contrary to the SIS problem, however, the hardness of LWE is not sufficiently well understood. The main hardness reduction for LWE [Reg05] is similar to the one for SIS mentioned above, except that it is quantum. This means that the existence of an efficient algorithm for LWE, even a classical (i.e., non-quantum) one, only implies the existence of an efficient quantum algorithm for lattice problems. This state of affairs is quite unsatisfactory: even though one might conjecture that efficient quantum algorithms for lattice problems do not exist, our understanding of quantum algorithms is still at its infancy. It is therefore highly desirable to come up with a classical hardness reduction for LWE.
Progress in this direction was made by [Pei09] (with some simplifications in the followup by Lyubashevsky and Micciancio [LM09]). The main result there is that LWE with exponential modulus is as hard as some standard lattice problems using a classical reduction. As that hardness result crucially relies on the exponential modulus, the open question remained as to whether LWE is hard for smaller moduli, in particular polynomial moduli. In addition to being an interesting question in its own right, this question is of special importance since many cryptographic applications, as well as the learning theory result of Klivans and Sherstov [KS06], are instantiated in this setting. Some additional evidence that reducing the modulus is a fundamental question comes from the Learning Parity with Noise (LPN) problem, which can be seen as LWE with modulus 2 (albeit with a different error distribution), and whose hardness is a long-standing open question. We remark that [Pei09] does include a classical hardness of LWE with polynomial modulus, albeit one based on a non-standard lattice problem, whose hardness is arguably as debatable as that of the LWE problem itself.
To summarize, prior to our work, the existence of an efficient algorithm for LWE with polynomial modulus was only known to imply an efficient quantum algorithm for lattice problems, or an efficient classical algorithm for a non-standard lattice problem. While both consequences are unlikely, they are arguably not as earth-shattering as an efficient classical algorithm for lattice problems. Hence, some concern about the hardness of LWE persisted, tainting the plethora of cryptographic applications based on it.
Main result. We provide the first classical hardness reduction of LWE with polynomial modulus. Our reduction is the first to show that the existence of an efficient classical algorithm for LWE with any subexponential modulus would indeed have earth-shattering consequences: it would imply an efficient algorithm for worst-case instances of standard lattice problems.
Theorem 1.1 (Informal). Solving n-dimensional LWE with poly(n) modulus implies an equally efficient solution to a worst-case lattice problem in dimension √ n.
modulus and the approximation ratio both remain fixed independently of the target {0, 1}-LWE algorithm. As mentioned above, our alternative to the reduction in [GKPV10] is based on a hybrid argument combined with a new hardness reduction for the "extended LWE" problem, which is a variant of LWE in which in addition to the LWE samples, we also get to see the inner product of the vector of error terms with a vector z of our choosing. This problem has its origins in the cryptographic literature, namely in the work of O'Neill, Peikert, and Waters [OPW11] on (bi)deniable encryption and the later work of Alperin-Sheriff and Peikert [AP12] on key-dependent message security. The hardness reductions included in those papers are not sufficient for our purposes, as they cannot handle large moduli or error terms, which is crucial in our setting. We therefore provide an alternative reduction which is conceptually much simpler, and essentially subsumes both previous reductions. Our reduction works equally well with exponential moduli and correspondingly long error vectors, a case earlier reductions could not handle.
Broader perspective. As a byproduct of the proof of Theorem 1.1, we obtain several results that shed new light on the hardness of LWE. Most notably, our modulus reduction result in Section 3 is actually far more general, and can be used to show a "modulus expansion/dimension reduction" tradeoff. Namely, it shows a reduction from LWE in dimension n and modulus p to LWE in dimension n/k and modulus p k (see Corollary 3.4). Combined with our modulus reduction, this has the following interesting consequence: the hardness of n-dimensional LWE with modulus q is a function of the quantity n log 2 q. In other words, varying n and q individually while keeping n log 2 q fixed essentially preserves the hardness of LWE.
Although we find this statement quite natural (since n log 2 q represents the number of bits in the secret), it has some surprising consequences. One is that n-dimensional LWE with modulus 2 n is essentially as hard as n 2 -dimensional LWE with polynomial modulus. As a result, n-dimensional LWE with modulus 2 n , which was shown in [Pei09] to be as hard as n-dimensional lattice problems using a classical reduction, is actually as hard as n 2 -dimensional lattice problems using a quantum reduction. The latter is presumably a much harder problem, requiring exp( Ω(n 2 )) time to solve. This corollary highlights an inherent quadratic loss in the classical reduction of [Pei09] (and as a result also our Theorem 1.1) compared to the quantum one in [Reg05].
A second interesting consequence is that 1-dimensional LWE with modulus 2 n is essentially as hard as n-dimensional LWE with polynomial modulus. The 1-dimensional version of LWE is closely related to the Hidden Number Problem of Boneh and Venkatesan [BV96]. It is also essentially equivalent to the Ajtai-Dwork-type [AD97] cryptosystem in [Reg03], as follows from simple reductions similar to the one in the appendix of [Reg10a]. Moreover, the 1-dimensional version can be seen as a special case of the Ring-LWE problem introduced in [LPR10] (for ring dimension 1, i.e., ring equal to Z). This allows us, via the ring switching technique from [GHPS12], to obtain the first hardness proof of Ring-LWE, with arbitrary ring dimension and exponential modulus, under the hardness of problems on general lattices (as opposed to just ideal lattice problems). In addition, this leads to the first hardness proof for the Ring-SIS problem [LM06,PR06] with exponential modulus under the hardness of general lattice problems, via the standard LWE-to-SIS reduction. (We note that since both results are obtained by scaling up from a ring of dimension 1, the hardness does not improve as the ring dimension increases.) A final interesting consequence of our reductions is that (the decision form of) LWE is hard with an arbitrary huge modulus, e.g., a prime; see Corollary 3.3. Previous results (e.g., [Reg05,Pei09,MM11,MP12]) required the modulus to be smooth, i.e., all its prime divisors had to be polynomially bounded.
Open questions. As mentioned above, our Theorem 1.1 inherits from [Pei09] a quadratic loss in the dimension, which does not exist in the quantum reduction [Reg05] nor in the known hardness reductions for SIS. At a technical level, this quadratic loss stems from the fact that the reduction in [Pei09] is not iterative. In contrast, the quantum reduction in [Reg05] as well as the reductions for SIS are iterative, and as a result do not incur the quadratic loss. We note that an additional side effect of the non-iterative reduction is that the hardness in Theorem 1.1 and [Pei09] is based only on the worst-case lattice problem GapSVP (and the essentially equivalent BDD and uSVP [LM09]), and not on problems like SIVP, which the quantum reduction of [Reg05] and the hardness reductions for SIS can handle. One case where this is very significant is when dealing with ideal lattices, as in the hardness reduction for Ring-LWE, since GapSVP turns out to be an easy problem there.
We therefore believe that it is important to understand whether there exists a classical reduction that does not incur the quadratic loss inherent in [Pei09] and in Theorem 1.1. In other words, is n-dimensional LWE with polynomial modulus classically as hard as n-dimensional lattice problems (as opposed to √ ndimensional)? This would constitute the first full dequantization of the quantum reduction in [Reg05]. While it is natural to conjecture that the answer to this question is positive, a negative answer would be quite tantalizing. In particular, it is conceivable that there exists a (classical) algorithm for LWE with polynomial modulus running in time 2 O( √ n) . Due to the quadratic expansion in Theorem 1.1, this would not lead to a faster classical algorithm for lattice problems; it would, however, lead to a 2 O( √ n) -time quantum algorithm for lattice problems using the reduction in [Reg05]. The latter would be a major progress in quantum algorithms, yet is not entirely unreasonable; in fact, a 2 O( √ n) -time quantum algorithm for a somewhat related quantum task was discovered by Kuperberg [Kup05] (see also [Reg02]).

Preliminaries
Let T = R/Z denote the cycle, i.e., the additive group of reals modulo 1. We also denote by T q its cyclic subgroup of order q, i.e., the subgroup given by {0, 1/q, . . . , (q − 1)/q}. For two probability distributions P, Q over some discrete domain, we define their statistical distance as |P (i) − Q(i)|/2 where i ranges over the distribution domain, and extend this to continuous distributions in the obvious way. We recall the following easy fact (see, e.g., [AD87, Eq. (2.3)] for a proof).
Claim 2.1. If P and Q are two probability distributions such that P (i) ≥ (1 − ε)Q(i) holds for all i, then the statistical distance between P and Q is at most ε.
We will use the following immediate corollary of the leftover hash lemma [HILL99].
A distinguishing problem P is defined by two distributions P 0 and P 1 , and a solution to the problem is the ability to distinguish between these distributions. The advantage of an algorithm A with binary output on P is defined as A reduction from a problem P to a problem Q is an efficient (i.e., polynomial-time) algorithm A B that solves P given access to an oracle B that solves Q. Most of our reductions (in fact all except the one in Lemma 2.15) are what we call "transformation reductions:" these reductions perform some transformation to the input and then apply the oracle to the result.

Lattices
An n-dimensional (full-rank) lattice Λ ⊆ R n is the set of all integer linear combinations of some set of n linearly independent basis vectors B = {b 1 , . . . , b n } ⊆ R n , The dual lattice of Λ ⊂ R n is defined as Λ * = {x ∈ R n : Λ, x ⊆ Z}. The minimum distance (or first successive minimum) λ 1 (Λ) of a lattice Λ is the length of a shortest nonzero lattice vector, i.e., λ 1 (Λ) = min 0 =x∈Λ x . For an approximation ratio γ = γ(n) ≥ 1, the GapSVP γ is the problem of deciding, given a basis B of an n-dimensional lattice Λ = L(B) and a number d, between the case where λ 1 (L(B)) ≤ d and the case where λ 1 (L(B)) > γd. We refer to [Kho10,Reg10b] for a recent account on the computational complexity of GapSVP γ .

Gaussian measures
For r > 0, the n-dimensional Gaussian function ρ r : R n → (0, 1] is defined as We extend this definition to sets, i.e., ρ r (A) = x∈A ρ r (x) ∈ [0, +∞] for any A ⊆ R n . The (spherical) continuous Gaussian distribution D r is the distribution with density function proportional to ρ r . More generally, for a matrix B, we denote by D B the distribution of Bx where x is sampled from D 1 . When B is nonsingular, its probability density function is proportional to A basic fact is that for any matrices B 1 , B 2 , the sum of a sample from D B 1 and an independent sample from D B 2 is distributed like D C for C = (B 1 B T 1 + B 2 B T 2 ) 1/2 . For an n-dimensional lattice Λ and a vector u ∈ R n , we define the discrete Gaussian distribution D Λ+u,r as the discrete distribution with support on the coset Λ + u whose probability mass function is proportional to ρ r . There exists an efficient procedure that samples within negligible statistical distance of any (not too narrow) discrete Gaussian distribution ([GPV08, Theorem 4.1]; see also [Pei10]). In the next lemma, proved in Section 5, we modify this sampler so that the output is distributed exactly as a discrete Gaussian. This also allows us to sample from slightly narrower Gaussians. Strictly speaking, the lemma is not needed for our results, and we could use instead the original sampler from [GPV08]. Using our exact sampler leads to slightly cleaner proofs as well as a (miniscule) improvement in the parameters of our reductions, and we include it here mainly in the hope that it finds further applications in the future.

Lemma 2.3.
There is a probabilistic polynomial-time algorithm that, given a basis B of an n-dimensional lattice Λ = L(B), c ∈ R n , and a parameter r ≥ B · ln(2n + 4)/π, outputs a sample distributed according to D Λ+c,r .
Here, B denotes the Gram-Schmidt orthogonalization of B, and B is the length of the longest vector in it. We recall the definition of the smoothing parameter from [MR04].
We now collect some known facts on Gaussian distributions and lattices.

Lemma 2.6 ([MR04, Lemma 4.1]). For any
Lemma 2.8 ([Reg05, Claim 3.9]). Let Λ be an n-dimensional lattice, let u ∈ R n be arbitrary, let r, s > 0 and let t = √ r 2 + s 2 . Assume that rs/t = 1/ 1/r 2 + 1/s 2 ≥ η ε (Λ) for some ε < 1/2. Consider the continuous distribution Y on R n obtained by sampling from D Λ+u,r and then adding a noise vector taken from D s . Then, the statistical distance between Y and D t is at most 4ε.

Lemma 2.10 (Special case of [Pei10, Theorem 3.1]).
Let Λ be a lattice and r, s > 0 be such that s ≥ η ε (Λ) for some ε ≤ 1/2. Then if we choose x from the continuous Gaussian D r and then choose y from the discrete Gaussian D Λ−x,s then x + y is within statistical distance 8ε of the discrete Gaussian D Λ,(r 2 +s 2 ) 1/2 .

Learning with Errors
For integers n, q ≥ 1, an integer vector s ∈ Z n , and a probability distribution φ on R, let A q,s,φ be the distribution over T n q × T obtained by choosing a ∈ T n q uniformly at random and an error term e from φ, and outputting the pair (a, b = a, s + e) ∈ T n q × T.
Definition 2.11. For integers n, q ≥ 1, an error distribution φ over R, and a distribution D over Z n , the (average-case) decision variant of the LWE problem, denoted LWE n,q,φ (D), is to distinguish given arbitrarily many independent samples, the uniform distribution over T n q ×T from A q,s,φ for a fixed s sampled from D. The variant where the algorithm only gets a bounded number of samples m ∈ N is denoted LWE n,m,q,φ (D).
Notice that the distribution A q,s,φ only depends on s mod q, and so one can assume without loss of generality that s ∈ {0, . . . , q − 1} n . Moreover, using a standard random self-reduction, for any distribution over secrets D, one can reduce LWE n,q,φ (D) to LWE n,q,φ (U ({0, . . . , q − 1} n )), and we will occasionally use LWE n,q,φ to denote the latter (as is common in previous work). When the noise is a Gaussian with parameter α > 0, i.e., φ = D α , we use the shorthand LWE n,q,α (D). Since the case when D is uniform over {0, 1} n plays an important role in this paper, we will denote it by binLWE n,q,φ (and by binLWE n,m,q,φ when the algorithm only gets m samples). Finally, as we show in the following lemma, one can efficiently reduce LWE to the case in which the secret is distributed according to the (discretized) error distribution and is hence somewhat short. This latter form of LWE, known as the "normal form," was first shown hard in [ACPS09] for the case of prime q. Here we observe that the proof extends to non-prime q, the new technical ingredient being Claim 2.13 below.
Proof. Consider the first 16n + 4 ln ln q samples (a, b). Using Claim 2.13, with probability at least 1 − 2e −1 ≥ 1/4, we can efficiently find a subsequence of the samples such that the matrix A 0 ∈ Z n×n q whose columns are formed by the a in the subset (scaled up by q) has an inverse A −1 0 ∈ Z n×n q modulo q. If we cannot find such a subsequence, we abort. Let b 0 ∈ T n be the vector formed by the corresponding b in the subsequence.
We then apply the given LWE oracle to the resulting m ′ pairs and output its result. We now analyze the reduction. First notice that the construction of A 0 depends only on the a component of the input samples, and hence the probability of finding it is the same in case the input is uniform and in case it consists of LWE samples. It therefore suffices in the following to show that there is a distinguishing gap conditioned on successfully finding an A 0 . To that end, first observe that if the input samples (a, b) are uniform in T n q × T then so are the output samples (a ′ , b ′ ). Next consider the case that the input samples are distributed according to A q,s,Dα for some s ∈ Z n . Then since s ≥ η ε (q −1 Z) by Lemma 2.5, using Lemma 2.10 we get that where e is an independent error from D α . Therefore, the output samples are distributed according to A q,−qe 0 ,Dα , completing the proof.
Claim 2.13. For any q ≥ 25, n ≥ 1, and t 1 ≥ 4, t 2 ≥ 1, given a sequence of t 1 n + t 2 ln ln q vectors a 1 , a 2 , . . . chosen uniformly and independently from Z n q , except with probability e −t 1 n/16 + e −t 2 /4 , there exists a subsequence of n vectors such that the n × n matrix they form is invertible modulo q. Moreover, such a subsequence can be found efficiently.
Proof. We consider the following procedure. Let k be a counter, initialized to 0, indicating the number of vectors currently in the subsequence, and let A ∈ Z n×k q be the matrix whose columns are formed by the current subsequence. We also maintain a unimodular matrix U ∈ Z n×n , initially set to the identity, satisfying the invariant that U · A ∈ Z n×k q has the following form: its top k × k submatrix is upper triangular with each diagonal coefficient coprime with q; its bottom (n − k) × k submatrix is zero. The procedure considers the vectors a i one by one. For each vector a, if it is such that the gcd of the last n − k entries of U a, call it g, is coprime with q, then it does the following: it adds a to the subsequence, computes (using, say, the extended GCD algorithm) a unimodular matrix V that acts as identity on the first k coordinates and for which the last n − k coordinates of V U a are (g, 0, . . . , 0), replaces U with V U , and increments k.
It is easy to see that the procedure's output is correct if it reaches k = n. It therefore suffices to analyze the probability that this event happens. For this we use the following two facts to handle the cases k < n − 1 and k = n − 1, respectively. First, the probability that the gcd of two uniformly random numbers modulo q is coprime with q is where ζ is the Riemann zeta function. Second, the probability that one uniformly random number modulo q is coprime with q is ϕ(q)/q, where ϕ is Euler's totient function. By [BS96,Theorem 8.8.7], this probability is at least (e γ ln ln q + 3/(ln ln q)) −1 where γ is Euler's constant, which for q ≥ 25 is at least (4 ln ln q) −1 .
Using the (multiplicative) Chernoff bound, the first fact, and the fact that U a is uniform in Z n q since U is unimodular, we see that the probability that k < n − 1 after considering t 1 n vector is at most e −t 1 n/16 . Moreover, once k = n − 1, using the second fact we get that the probability that after considering t 2 ln ln q additional vectors we still have k = n − 1 is at most e −t 2 /4 . Unknown (Bounded) Noise Rate. We also consider a variant of LWE in which the amount of noise is some unknown β ≤ α (as opposed to exactly α), with β possibly depending on the secret s. As the following lemma shows, this does not make the problem significantly harder.
Lemma 2.15. Let A be an algorithm for LWE n,m,q,α with advantage at least ε > 0. Then there exists an algorithm B for LWE n,m ′ ,q,≤α using oracle access to A and with advantage at least 1/3, where both m ′ and its running time are poly(m, 1/ε, n, log q).
The proof is standard (see, e.g., [Reg05, Lemma 3.7] for the analogous statement for the search version of LWE). The idea is to use Chernoff bound to estimate A's success probability on the uniform distribution, and then add noise in small increments to our given distribution and estimate A's behavior on the resulting distributions. If there is a gap between any of these and the uniform behavior, the input distribution is deemed non-uniform. The full proof is omitted.
Relation to Lattice Problems. Regev [Reg05] and Peikert [Pei09] showed quantum and classical reductions (respectively) from the worst-case hardness of the GapSVP problem to the search version of LWE. (We note that the quantum reduction in [Reg05] also shows a reduction from SIVP.) As mentioned in the introduction, the classical reduction only works when the modulus q is exponential in the dimension n. This is summarized in the following theorem, which is derived from [Reg05, Theorem 3.1] and [Pei09, Theorem 3.1].
Theorem 2.16. Let n, q ≥ 1 be integers and let α ∈ (0, 1) be such that αq ≥ 2 √ n. Then there exists a quantum reduction from worst-case n-dimensional GapSVP O(n/α) to LWE n,q,α . If in addition q ≥ 2 n/2 then there is also a classical reduction between those problems.
In order to obtain hardness of the decision version of LWE, which is the one we consider throughout the paper, one employs a search-to-decision reduction. Several such reductions appear in the literature (e.g., [Reg05,Pei09,MP12]). The most recent reduction by Micciancio and Peikert [MP12], which essentially subsumes all previous reductions, requires the modulus q to be smooth. Below we give the special case when the modulus is a power of 2, which suffices for our purposes. It follows from our results that (decision) LWE is hard not just for a smooth modulus q, as follows from [MP12], but actually for all moduli q, including prime moduli, with only a small deterioration in the noise (see Corollary 3.3). 3.1]). Let q be a power of 2, and α satisfy 1/q < α < 1/ω( √ log n). Then there exists an efficient reduction from search LWE n,q,α to (decision) LWE n,q,α ′ for α ′ = α · ω(log n).

Modulus-Dimension Switching
The main results of this section are Corollaries 3.2 and 3.4 below. Both are special cases of the following technical theorem. We say that a distribution D over Z n is (B, δ)-bounded for some reals B, δ ≥ 0 if the probability that x ← D has norm greater than B is at most δ.
Then there is an efficient (transformation) reduction from LWE n,m,q,≤α (D) to LWE n ′ ,m,q ′ ,≤β (G · D) that reduces the advantage by at most δ + 14εm.
Here we use the notation B from Lemma 2.3. We also note that if needed, the distribution on secrets produced by the reduction can always be turned into the uniform distribution on Z n ′ q ′ , as mentioned after Definition 2.11. Also, we recall that there exists an elementary reduction from LWE n ′ ,q ′ ,≤β to LWE n ′ ,q ′ ,β (see Lemma 2.15).
In particular, by using the normal form of LWE (Lemma 2.12), in which the secret has distribution D = D Z n , √ 2αq , we can switch to a power-of-2 modulus with only a small loss in the noise rate, as described in the following corollary. Together with the known search-to-decision reduction (Theorem 2.17), this extends the known hardness of (decision) LWE to any modulus q. Here we use that D = D Z n ,r is (Cr n log(n/δ), δ)bounded for some universal constant C > 0, which follows by taking union bound over the n coordinates. (Alternatively, one could use that it is (r √ n, 2 −n )-bounded, as follows from [Ban93, Lemma 1.5], leading to a slightly tighter statement for large n.) Corollary 3.3. Let δ ∈ (0, 1/2), m ≥ n ≥ 1, q ′ ≥ 25. Let also q ∈ [q ′ , 2q ′ ) be the smallest power of 2 not smaller than q ′ and α ≥ ln(2n(1 + 16/δ)/π)/q. There exists an efficient (transformation) reduction from LWE n,m,q,α to LWE n,m ′ ,q ′ ,≤β where m ′ = m − (16n + 4 ln ln q) and β = Cα √ n log(n/δ) log(m/δ) for some universal constant C > 0, that turns advantage of ζ into an advantage of at least (ζ − δ)/4.
Another corollary illustrates a modulus-dimension tradeoff. Assume n = kn ′ for some k ≥ 1, and let q ′ = q k . Let G = I n ′ ⊗ g, where g = (1, q, q 2 , . . . , q k−1 ) T ∈ Z k . We then have Λ = q −k G T Z n ′ + Z n . A basis of Λ is given by this is since the column vectors of B belong to Λ and the determinants match. Orthogonalizing from left to right, we have B = q −1 I and so B = q −1 . We therefore obtain the following corollary, showing that we can trade off the dimension against the modulus, holding n log q = n ′ log q ′ fixed. For example, letting D = D Z n ,αq (corresponding to a secret in normal form, see Lemma 2.12), which is (αq √ n, 2 −n )bounded, the reduction increases the error rate by about a √ n factor.
Theorem 3.1 follows immediately from the following lemma.
There is an efficient mapping from T n q × T to T n ′ q ′ × T, which has the following properties: • If the input is uniformly random, then the output is within statistical distance 4ε from the uniform distribution.
Proof. The main idea behind the reduction is to encode T n q into T n ′ q ′ , so that the mod-1 inner products between vectors in T n q and a short vector s ∈ Z n , and between vectors in T n ′ q ′ and Gs ∈ Z n ′ , are nearly equivalent. In a bit more detail, the reduction will map its input vector a ∈ T n q (from the given LWE-oruniform distribution) to a vector a ′ ∈ T n ′ q ′ , so that a ′ , Gs = G T a ′ , s ≈ a, s mod 1 for any (unknown) s ∈ Z n . To do this, it randomly samples a ′ so that G T a ′ ≈ a mod Z n , where the approximation error will be a discrete Gaussian of parameter r.
We can now formally define the reduction, which works as follows. On an input pair (a, b) ∈ T n q × T, it does the following: • Choose f ← D Λ−a,r using Lemma 2.3 with basis B, and let v = a + f ∈ Λ/Z n . (The coset Λ − a is well defined since a =ā + Z n is some coset of Z n ⊆ Λ.) Choose a uniformly random solution a ′ ∈ T n ′ q ′ to the equation G T a ′ = v mod Z n . This can be done by computing a basis of the solution set G T a ′ = 0 mod Z n , and adding a uniform element from that set to an arbitrary solution to the equation G T a ′ = v mod Z n .
• Choose e ′ ← D rB and let b ′ = b + e ′ ∈ T.
We now analyze the reduction. First, if the distribution of the input is uniform, then it suffices to show that a ′ is (nearly) uniformly random, because both b and e ′ are independent of a ′ , and b ∈ T is uniform. To prove this claim, notice that it suffices to show that the coset v ∈ Λ/Z n is (nearly) uniformly random, because each v has the same number of solutions a ′ to G T a ′ = v mod Z n . Next, observe that for anȳ a ∈ T n q andf ∈ Λ −ā, we have by Lemma 2.7 (using that r ≥ η ε (Λ) by Lemma 2.5) that where C = q −n /ρ r (Λ) is a normalizing value that does not depend onā orf . Therefore, by summing over allā,f satisfyingā +f =v, we obtain that for anyv ∈ Λ/Z n , Since r ≥ η ε (q −1 Z n ) (by Lemma 2.5), Lemma 2.7 implies that Pr[v =v] ∈ 1−ε 1+ε , 1+ε 1−ε C ′ for a constant C ′ that is independent ofv. By Claim 2.1, this shows that a ′ is within statistical distance 1−((1−ε)/(1+ε)) 2 ≤ 4ε of the uniform distribution.
It remains to show that the reduction maps A q,s,Dα to A q ′ ,Gs,D β . Let the input sample from the former distribution be (a, b = a, s + e), where e ← D α . As argued above, the output a ′ is (nearly) uniform over T n ′ q ′ . So condition now on any fixed value a ′ ∈ T n ′ q ′ of a ′ , and letv = G T a ′ mod Z n . We have b ′ = a, s + e + e ′ = a ′ , Gs + e + −f , s + e ′ mod 1.

Hardness of LWE with Binary Secret
The following is the main theorem of this section.
For most purposes the sum over prime factors of q in (4.1) is negligible. For instance, in deriving the formal statement of Theorem 1.1 above, we used a q that is a power of 2, in which case the sum is 2 −k−1 = 2 − √ n−1 , which is negligible. If needed, one can improve this by applying the modulus switching reduction (Corollary 3.3) before applying Theorem 4.1 in order to make q prime. (Strictly speaking, one also needs to apply Lemma 2.15 to replace the "unknown noise" variant of LWE given by Corollary 3.3 with the fixed noise variant.) This improves the advantage loss to q − √ n−1 which is roughly 2 −n .
In a high level, the proof of the theorem follows by combining three main steps. The first, given in Section 4.1, reduces LWE to a variant in which the first equation is errorless. The second, given in Section 4.2, reduces the latter to the intermediate problem extLWE, another variant of LWE in which some information on the noise elements is leaked. Finally, in Section 4.3, we reduce extLWE to LWE with {0, 1} secret. We note that the first reduction is relatively standard; it is the other two that we consider as the main contribution of this section. We now proceed with more details (see also Figure 1).
Proof. First, since m ≥ n, Lemma 4.3 provides a transformation reduction from LWE k,m,q,α to first-iserrorless LWE k+1,n,q,α , while reducing the advantage by at most 2 −k+1 . Next, Lemma 4.7 with Z = {0, 1} n , which is of quality ξ = 2 by Claim 4.6, reduces the latter problem to extLWE k+1,n,q, √ 5α,{0,1} n while reducing the advantage by at most 33ε/2. Then, Lemma 4.8 reduces the latter problem to extLWE m k+1,n,q, √ 5α,{0,1} n , while losing a factor of m in the advantage. Finally, Lemma 4.9 provides three reductions to binLWE n,m,q,≤ √ 10nα : two from the latter problem, and one from LWE k+1,m,q, √ 5nα , guaranteeing that the sum of advantages is at least the original advantage minus 4mε + δ. Together with the trivial reduction from LWE k,m,q,α to LWE k+1,m,q, √ 5nα (which incurs no loss in advantage), this completes the proof.

First-is-errorless LWE
We first define a variant of LWE in which the first equation is given without error, and then show in Lemma 4.3 that it is still hard.
Definition 4.2. For integers n, q ≥ 1 and an error distribution φ over R, the "first-is-errorless" variant of the LWE problem is to distinguish between the following two scenarios. In the first, the first sample is uniform over T n q × T q and the rest are uniform over T n q × T. In the second, there is an unknown uniformly distributed s ∈ {0, . . . , q − 1} n , the first sample we get is from A q,s,{0} (where {0} denotes the distribution that is deterministically zero) and the rest are from A q,s,φ . Lemma 4.3. For any n ≥ 2, m, q ≥ 1, and error distribution φ, there is an efficient (transformation) reduction from LWE n−1,m,q,φ to the first-is-errorless variant of LWE n,m,q,φ that reduces the advantage by at most p p −n , with the sum going over all prime factors of q. Notice that if q is prime the loss in advantage is at most q −n . Alternatively, for any number q we can bound it by which might be good enough when n is large.
Proof. The reduction starts by choosing a vector a ′ uniformly at random from {0, . . . , q − 1} n . Let r be the greatest common divisor of the coordinates of a ′ . If it is not coprime to q, we abort. The probability that this happens is at most p prime, p|q p −n .
Assuming we do not abort, we proceed by finding a matrix U ∈ Z n×n that is invertible modulo q and whose leftmost column is a ′ . Such a matrix exists, and can be found efficiently. For instance, using the extended GCD algorithm, we find an n × n unimodular matrix R such that Ra ′ = (r, 0, . . . , 0) T . Then R −1 · diag(r, 1, . . . , 1) is the desired matrix. We also pick a uniform element s 0 ∈ {0, . . . , q − 1}. The reduction now proceeds as follows. The first sample it outputs is (a ′ /q, s 0 /q). The remaining samples are produced by taking a sample (a, b) from the given oracle, picking a fresh uniformly random d ∈ T q , and outputting (U(d|a), b + (s 0 · d)) with the vertical bar denoting concatenation. It is easy to verify correctness: given uniform samples, the reduction outputs uniform samples (with the first sample's b component uniform over T q ), up to statistical distance 2 −n+1 ; and given samples from A q,s,φ , the reduction outputs one sample from A q,s ′ ,{0} and the remaining samples from A q,s ′ ,φ , up to statistical distance 2 −n+1 , where s ′ = (U −1 ) T (s 0 |s) mod q. This proves correctness since U, being invertible modulo q, induces a bijection on Z n q , and so s ′ is uniform in {0, . . . , q − 1} n .

Extended LWE
We next define the intermediate problem extLWE. (This definition is of an easier problem than the one considered in previous work [AP12], which makes our hardness result stronger.) Definition 4.4. For n, m, q, t ≥ 1, Z ⊆ Z m , and a distribution χ over 1 q Z m , the extLWE t n,m,q,χ,Z problem is as follows. The algorithm gets to choose z ∈ Z and then receives a tuple Its goal is to distinguish between the following two cases. In the first, A ∈ T n×m q is chosen uniformly, e i ∈ 1 q Z m are chosen from χ, and b i = A T s i + e i mod 1 where s i ∈ {0, . . . , q − 1} n are chosen uniformly. The second case is identical, except that the b i are chosen uniformly in T m q independently of everything else.
When t = 1, we omit the superscript t. Also, when χ is D q −1 Z m ,α for some α > 0, we replace the subscript χ by α. We note that a discrete version of LWE can be defined as a special case of extLWE by setting Z = {0 m }. We next define a measure of quality of sets Z.
Definition 4.5. For a real ξ > 0 and a set Z ⊆ Z m we say that Z is of quality ξ if given any z ∈ Z, we can efficiently find a unimodular matrix U ∈ Z m×m such that if U ′ ∈ Z m×(m−1) is the matrix obtained from U by removing its leftmost column then all of the columns of U ′ are orthogonal to z and its largest singular value is at most ξ.
The idea in this definition is that the columns of U ′ form a basis of the lattice of integer points that are orthogonal to z, i.e., the lattice {b ∈ Z m : b, z = 0}. The quality measures how "short" we can make this basis.
Proof. Let z ∈ Z and assume without loss of generality that its first k ≥ 1 coordinates are 1 and the remaining m − k are 0. Then consider the upper bidiagonal matrix U whose diagonal is all 1s and whose diagonal above the main diagonal is (−1, . . . , −1, 0, . . . , 0) with −1 appearing k − 1 times. The matrix is clearly unimodular and all the columns except the first one are orthogonal to z. Moreover, by the triangle inequality, we can bound the operator norm of U by the sum of that of the diagonal 1 matrix and the off-diagonal matrix, both of which clearly have norm at most 1.
Proof. We first describe the reduction. Assume we are asked to provide samples for some z ∈ Z. We compute a unimodular U ∈ Z m×m for z as in Definition 4.5, and let U ′ ∈ Z m×(m−1) be the matrix formed by removing the first column of U. We then take m samples from the given distribution, resulting in . We also sample a vector f from the m-dimensional continuous Gaussian distribution D α(ξ 2 I−U ′ U ′T ) 1/2 , which is well defined since ξ 2 I − U ′ U ′T is a positive semidefinite matrix by our assumption on U. The output of the reduction is the tuple where b ′ = Ub+f , and c is chosen from the discrete Gaussian distribution D q −1 Z m −b ′ ,r (using Lemma 2.3). We now prove the correctness of the reduction. Consider first the case that we get valid LWE equations, i.e., A is uniform in T n×m q and b = A T s + e ∈ T m where s ∈ {0, . . . , q − 1} n is uniformly chosen, the first coordinate of e ∈ R m is 0, and the remaining m − 1 coordinates are chosen from D α . Since U is unimodular, A ′ = AU T is uniformly distributed in T n×m q as required. From now on we condition on an arbitrary A ′ and analyze the distribution of the remaining two components of (4.2). Next, Since Ue is distributed as a continuous Gaussian D αU ′ , the vector Ue + f is a distributed as a spherical continuous Gaussian D αξ . Moreover, since A ′T s ∈ T m q , the coset q −1 Z m − b ′ is identical to q −1 Z m − (Ue + f ), so we can see c as being chosen from D q −1 Z m −(Ue+f ),r . Therefore, by Lemma 2.10 and using that r ≥ η ε (q −1 Z m ) by Lemma 2.5, the distribution of Ue + f + c is within statistical distance 8ε of D q −1 Z m ,(α 2 ξ 2 +r 2 ) 1/2 . This shows that the second component in (4.2) is also distributed correctly. Finally, for the third component, by our assumption on U and the fact that the first coordinate of e is zero, and so the third component gives the inner product of the noise with z, as desired.
We now consider the case where the input is uniform, i.e., that A is uniform in T n×m q and b is independent and uniform in T q × T m−1 . We first observe that by Lemma 2.6, since α ≥ η ε/m (q −1 Z) (by Lemma 2.5), the distribution of (A, b) is within statistical distance ε/2 of the distribution of (A, e ′ + e) where e ′ is chosen uniformly in T m q , the first coordinate of e is zero, and its remaining m − 1 coordinates are chosen independently from D α . So from now on assume our input is (A, e ′ + e). The first component of (4.2) is uniform in T n×m q as before, and moreover, it is clearly independent of the other two. Moreover, and so c is distributed identically to the case of a valid LWE equation, and in particular is independent of e ′ . This establishes that the third component of (4.2) is correctly distributed; moreover, since e ′ is independent of the first and third components, and Ue ′ is uniform in T m q (since U is unimodular), we get that the second component is uniform and independent of the other two, as desired.
We end this section by stating the standard reduction to the multi-secret (t ≥ 1) case of extended LWE.
Lemma 4.8. Let n, m, q, χ, Z be as in Definition 4.4 with χ efficiently sampleable, and let t ≥ 1 be an integer. Then there is an efficient (transformation) reduction from extLWE n,m,q,χ,Z to extLWE t n,m,q,χ,Z that reduces the advantage by a factor of t.
The proof is by a standard hybrid argument. We bring it here for the sake of completeness. We note that the distribution of the secret vector s needs to be sampleable but otherwise it plays no role in the proof. The lemma therefore naturally extends to any (sampleable) distribution of s.
Proof. Let A be an algorithm for extLWE t n,m,q,χ,Z , let z be the vector output by A in the first step (note that this is a random variable) and let H i denote the distribution where u i+1 , . . . , u t are sampled independently and uniformly in T m q . Then by definition Adv We now describe an algorithm B for extLWE n,m,q,χ,Z : First, B runs A to obtain z and sends it to the challenger as its own z. Then, given an input (A, d, z, y) for extLWE n,m,q,χ,Z , the distinguisher B samples i * ← [t], and in addition s 1 , . . . , s i * −1 ← Z n q , e 1 , . . . , e i * −1 , e i * +1 , . . . , e t ← χ m , u i * +1 , . . . , u t ← T m q . It sets b i = A T · s i + e i (mod 1), and sends the following to A: (A, {b 1 , . . . , b i * −1 , d, u i * +1 , . . . , u t }, z, { z, e 1 , . . . , z, e i * −1 , y, z, e i * +1 , . . . , z, e t }) .
Finally, B outputs the same output as A did.
Note that when the input to B is distributed as P 0 = (A, b, z, z T · e) with b = A T · s + e (mod 1), then B feeds A with exactly the distribution H i * . On the other hand, if the input to B is P 1 = (A, u, z, z T · e) with u ← T m q , then B feeds A with H i * −1 . Since i * is uniform in [t], we get that and the result follows.
Proof. The proof follows by a sequence of hybrids. Let k, n, m, q, ε, α, β, γ be as in the lemma statement. We consider z ← {0, 1} n and e ← D m α ′ for α ′ = β 2 z 2 + γ 2 ≤ √ 2nβ = α. In addition, we let A ← T n×m q , u ← T m , and define b:=A T · z + e (mod 1). We consider an algorithm A that distinguishes between (A, b) and (A, u).
We let H 0 denote the distribution (A, b) and H 1 the distribution where N ← D n×m q −1 Z,β andê ← D m γ . Using z ≤ √ n and that β ≥ √ 2η ε (Z n )/q (by Lemma 2.5), it follows by Lemma 2.9 that the statistical distance between −N T z +ê and D m α ′ is at most 4mε. It thus follows that We define a distribution H 2 as follows. Let B ← T k×m q and C ← T k×n q . LetÂ:=qC T · B + N (mod 1). Finally, H 2 = (Â,Â T · z − N T z +ê) = (Â, qB T · C · z +ê) .
We now argue that there exists an adversary B 1 for problem extLWE m k,n,q,β,{0,1} n , such that This is because H 1 , H 2 can be viewed as applying the same efficient transformation on the distributions (C, A, N T z) and (C,Â, N T z) respectively. Since distinguishing the latter distributions is exactly the extLWE m k,n,q,β,{0,1} n problem (where the columns of q · B are interpreted as the m secret vectors), the distinguisher B 1 follows by first applying the aforementioned transformation and then applying A.
For the next hybrid, we define H 3 = (Â, B T · s +ê), for s ← Z k q . It follows that by the leftover hash lemma (see Lemma 2.2), since H 2 , H 3 can be derived from (C, qC · z) and (C, s) respectively, whose statistical distance is at most δ. Our next hybrid makes the second component uniform: Eq. (4.7) is derived very similarly to Eq. (4.4): We notice that H 4 , H 5 can be viewed as applying the same efficient transformation on the distributions (C,Â) and (C, A) respectively. Since distinguishing the latter distributions is exactly the extLWE m k,n,q,β,{0 n } problem (where the columns of q · B are interpreted as the m secret vectors), the distinguisher B 3 follows by first applying the aforementioned transformation and then applying A.

Exact Gaussian Sampler
In this section we prove Lemma 2.3. As in [GPV08], the proof consists of two parts. In the first we consider the one-dimensional case, and in the second we use it recursively to sample from arbitrary lattices. Our one-dimensional sampler is based on rejection sampling, just like the one in [GPV08]. Unlike [GPV08], we use the continuous normal distribution as the source distribution which allows us to avoid truncation, and as a result obtain an exact sample. Our second part uses the same recursive routine as in [GPV08], but adds a rejection sampling step to it in order to take care of the deviation of its output from the desired distribution.

The one-dimensional case
Here we show how to sample from the discrete Gaussian distribution on arbitrary cosets of one-dimensional lattices. We use a standard rejection sampling procedure (see, e.g. [Dev86, Page 117] for a very similar procedure). By scaling, we can restrict without loss of generality to the lattice Z, i.e., we consider the task of sampling from D Z+c,r for a given coset representative c ∈ [0, 1) and parameter r > 0. The sampling procedure is as follows. Let Z 0 = ∞ c ρ r (x)dx, and Z 1 = c−1 −∞ ρ r (x)dx. These two numbers can be computed efficiently by expressing them in terms of the error function. Let Z = Z 0 + Z 1 + ρ r (c)+ ρ r (c− 1). The algorithm repeats the following until it outputs an answer: • With probability ρ r (c)/Z it outputs c; • With probability ρ r (c − 1)/Z it outputs c − 1; • With probability Z 0 /Z it chooses x from the restriction of the continuous normal distribution D r to the interval [c, ∞). Let y be the smallest element in Z + c that is larger than x. With probability ρ r (y)/ρ r (x) output y, and otherwise repeat; • With probability Z 1 /Z it chooses x from the restriction of the continuous normal distribution D r to the interval (−∞, c − 1]. Let y be the largest element in Z + c that is smaller than x. With probability ρ r (y)/ρ r (x) output y, and otherwise repeat.
Consider now one iteration of the procedure. The probability of outputting c is ρ r (c)/Z, that of outputting c − 1 is ρ r (c − 1)/Z, that of outputting c + k for some k ≥ 1 is and similarly, that of outputting c−1−k for some k ≥ 1 is ρ r (c−1−k)/Z. From this it follows immediately that conditioned on outputting something, the output distribution has support on Z + c and probability mass function proportional to ρ r , and is therefore the desired discrete Gaussian distribution D Z+c,r . Moreover, the probability of outputting something is Therefore at each iteration the procedure has probability of at least 1/2 to terminate. As a result, the probability that the number of iterations is greater than t is at most 2 −t , and in particular, the expected number of iterations is at most 2.

The general case
For completeness, we start by recalling the SampleD procedure described in [GPV08]. This is a recursive procedure that gets as input a basis B = (b 1 , . . . , b n ) of an n-dimensional lattice Λ = L(B), a parameter r > 0, and a vector c ∈ R n , and outputs a vector in Λ + c whose distribution is close to that of D Λ+c,r . Let b 1 , . . . , b n be the Gram-Schmidt orthogonalization of b 1 , . . . , b n , and let b 1 , . . . , b n be the normalized Gram-Schmidt vectors, i.e., b i = b i / b i . The procedure is the following.
1. Let c n ← c. For i ← n, . . . , 1, do: (a) Choose v i from D b i Z+ c i ,b i ,r using the exact one-dimensional sampler.
It is easy to verify that the procedure always outputs vectors in the coset Λ+c. Moreover, the probability of outputting any v ∈ Λ + c is where c i are the values computed in the procedure when it outputs v. Notice that by Lemma 2.5 and our assumption on r, we have that r ≥ η 1/(n+1) ( b i Z) for all i. Therefore, by Lemma 2.7, we have that for all c ∈ R, ρ r ( b i Z + c) ∈ 1 − 2 n + 2 , 1 ρ r ( b i Z).
In order to get an exact sample, we combine the above procedure with rejection sampling. Namely, we apply SampleD to obtain some vector v. We then output v with probability ∈ 1 − 2 n + 2 n , 1 ⊆ (e −2 , 1], (5.1) and otherwise repeat. This probability can be efficiently computed, as we will show below. As a result, in any given iteration the probability of outputting the vector v ∈ Λ + c is .
Since the denominator is independent of v, we obtain that in any given iteration, conditioned on outputting something, the output is distributed according to the desired distribution D Λ+c,r , and therefore this is also the overall output distribution of our sampler. Moreover, by (5.1), the probability of outputting something in any given iteration is at least e −2 , and therefore, the probability that the number of iterations is greater than t is at most (1 − e −2 ) t , and in particular, the expected number of iterations is at most e 2 . It remains to show how to efficiently compute the probability in (5.1). By scaling, it suffices to show how to compute ρ r (Z + c) = k∈Z exp(−π(k + c) 2 /r 2 ) for any r > 0 and c ∈ [0, 1). If r < 1, the sum decays very fast, and we can achieve any desired t bits of accuracy in time poly(t), which agrees with our notion of efficiently computing a real number (following, e.g., the treatment in [Lov86, Section 1.4]). For r ≥ 1, we use the Poisson summation formula (see, e.g., [MR04, Lemma 2.8]) to write ρ r (Z + c) = r · k∈Z exp(−πk 2 r 2 + 2πick) = r · k∈Z exp(−πk 2 r 2 ) cos(2πck), which again decays fast enough so we can compute it to within any desired t bits of accuracy in time poly(t).