On Lattices, Learning with Errors,
Random Linear Codes, and Cryptography

For an integer $n\geq 1$ and a real number $\varepsilon\geq 0$, consider the ‘learning from parity with error’ problem, defined as follows: the goal is to find an unknown $\mathbf{s}\in{\mathbb{Z}}_{2}^{n}$ given a list of ‘equations with errors’

where the $\mathbf{a}_{i}$’s are chosen independently from the uniform distribution on ${\mathbb{Z}}_{2}^{n}$, ${\langle{\mathbf{s},\mathbf{a}_{i}}\rangle}=\sum_{j}s_{j}(a_{i})_{j}$ is the inner product modulo $2$ of $\mathbf{s}$ and $\mathbf{a}_{i}$, and each equation is correct independently with probability $1-\varepsilon$. More precisely, the input to the problem consists of pairs $(\mathbf{a}_{i},b_{i})$ where each $\mathbf{a}_{i}$ is chosen independently and uniformly from ${\mathbb{Z}}_{2}^{n}$ and each $b_{i}$ is independently chosen to be equal to ${\langle{\mathbf{s},\mathbf{a}_{i}}\rangle}$ with probability $1-\varepsilon$. The goal is to find $\mathbf{s}$. Notice that the case $\varepsilon=0$ can be solved efficiently by, say, Gaussian elimination. This requires $O(n)$ equations and ${\rm{poly}}(n)$ time.

The problem seems to become significantly harder when we take any positive $\varepsilon>0$. For example, let us consider again the Gaussian elimination process and assume that we are interested in recovering only the first bit of $\mathbf{s}$. Using Gaussian elimination, we can find a set $S$ of $O(n)$ equations such that $\sum_{S}\mathbf{a}_{i}$ is $(1,0,\ldots,0)$. Summing the corresponding values $b_{i}$ gives us a guess for the first bit of $\mathbf{s}$. However, a standard calculation shows that this guess is correct with probability $\frac{1}{2}+2^{-\Theta(n)}$. Hence, in order to obtain the first bit with good confidence, we have to repeat the whole procedure $2^{\Theta(n)}$ times. This yields an algorithm that uses $2^{O(n)}$ equations and $2^{O(n)}$ time. In fact, it can be shown that given only $O(n)$ equations, the $\mathbf{s}^{\prime}\in{\mathbb{Z}}_{2}^{n}$ that maximizes the number of satisfied equations is with high probability $\mathbf{s}$. This yields a simple maximum likelihood algorithm that requires only $O(n)$ equations and runs in time $2^{O(n)}$.

Blum, Kalai, and Wasserman [11] provided the first subexponential algorithm for this problem. Their algorithm requires only $2^{O(n/\log n)}$ equations/time and is currently the best known algorithm for the problem. It is based on a clever idea that allows to find a small set $S$ of equations (say, $O(\sqrt{n})$) among $2^{O(n/\log n)}$ equations, such that $\sum_{S}\mathbf{a}_{i}$ is, say, $(1,0,\ldots,0)$. This gives us a guess for the first bit of $\mathbf{s}$ that is correct with probability $\frac{1}{2}+2^{-\Theta(\sqrt{n})}$. We can obtain the correct value with high probability by repeating the whole procedure only $2^{O(\sqrt{n})}$ times. Their idea was later shown to have other important applications, such as the first $2^{O(n)}$-time algorithm for solving the shortest vector problem [23, 5].

An important open question is to explain the apparent difficulty in finding efficient algorithms for this learning problem. Our main theorem explains this difficulty for a natural extension of this problem to higher moduli, defined next.

Let $p=p(n)\leq{\rm{poly}}(n)$ be some prime integer and consider a list of ‘equations with error’

where this time $\mathbf{s}\in{\mathbb{Z}}_{p}^{n}$, $\mathbf{a}_{i}$ are chosen independently and uniformly from ${\mathbb{Z}}_{p}^{n}$, and $b_{i}\in{\mathbb{Z}}_{p}$. The error in the equations is now specified by a probability distribution $\chi:{\mathbb{Z}}_{p}\to\mathbb{R}^{+}$ on ${\mathbb{Z}}_{p}$. Namely, for each equation $i$, $b_{i}={\langle{\mathbf{s},\mathbf{a}_{i}}\rangle}+e_{i}$ where each $e_{i}\in{\mathbb{Z}}_{p}$ is chosen independently according to $\chi$. We denote the problem of recovering $\mathbf{s}$ from such equations by $\mbox{\sc LWE}_{p,\chi}$ (learning with error). For example, the learning from parity problem with error $\varepsilon$ is the special case where $p=2$, $\chi(0)=1-\varepsilon$, and $\chi(1)=\varepsilon$. Under a reasonable assumption on $\chi$ (namely, that $\chi(0)>1/p+1/{\rm{poly}}(n)$), the maximum likelihood algorithm described above solves $\mbox{\sc LWE}_{p,\chi}$ for $p\leq{\rm{poly}}(n)$ using ${\rm{poly}}(n)$ equations and $2^{O(n\log n)}$ time. Under a similar assumption, an algorithm resembling the one by Blum et al. [11] requires only $2^{O(n)}$ equations/time. This is the best known algorithm for the LWE problem.

Our main theorem shows that for certain choices of $p$ and $\chi$, a solution to $\mbox{\sc LWE}_{p,\chi}$ implies a quantum solution to worst-case lattice problems.

The exact definition of $\bar{\Psi}_{\alpha}$ will be given later. For now, it is enough to know that it is a distribution on ${\mathbb{Z}}_{p}$ that has the shape of a discrete Gaussian centered around 0 with standard deviation $\alpha p$, as in Figure 1. Also, the probability of $0$ (i.e., no error) is roughly $1/(\alpha p)$. A possible setting for the parameters is $p=O(n^{2})$ and $\alpha=1/(\sqrt{n}\log^{2}n)$ (in fact, these are the parameters that we use in our cryptographic application).

GapSVP and SIVP are two of the main computational problems on lattices. In GapSVP, for instance, the input is a lattice, and the goal is to approximate the length of the shortest nonzero lattice vector. The best known polynomial time algorithms for them yield only mildly subexponential approximation factors [24, 38, 5]. It is conjectured that there is no classical (i.e., non-quantum) polynomial time algorithm that approximates them to within any polynomial factor. Lattice-based constructions of one-way functions, such as the one by Ajtai [2], are based on this conjecture.

One might even conjecture that there is no quantum polynomial time algorithm that approximates GapSVP (or SIVP) to within any polynomial factor. One can then interpret the main theorem as saying that based on this conjecture, the LWE problem is hard. The only evidence supporting this conjecture is that there are no known quantum algorithms for lattice problems that outperform classical algorithms, even though this is probably one of the most important open questions in the field of quantum computing.²²2If forced to make a guess, the author would say that the conjecture is true.

In fact, one could also interpret our main theorem as a way to disprove this conjecture: if one finds an efficient algorithm for LWE, then one also obtains a quantum algorithm for approximating worst-case lattice problems. Such a result would be of tremendous importance on its own. Finally, we note that it is possible that our main theorem will one day be made classical. This would make all our results stronger and the above discussion unnecessary.

The LWE problem can be equivalently presented as the problem of decoding random linear codes. More specifically, let $m={\rm{poly}}(n)$ be arbitrary and let $\mathbf{s}\in{\mathbb{Z}}_{p}^{n}$ be some vector. Then, consider the following problem: given a random matrix $Q\in{\mathbb{Z}}_{p}^{m\times n}$ and the vector $\mathbf{t}=Q\mathbf{s}+\mathbf{e}\in{\mathbb{Z}}_{p}^{m}$ where each coordinate of the error vector $\mathbf{e}\in{\mathbb{Z}}_{p}^{m}$ is chosen independently from $\bar{\Psi}_{\alpha}$, recover $\mathbf{s}$. The Hamming weight of $\mathbf{e}$ is roughly $m(1-1/(\alpha p))$ (since a value chosen from $\bar{\Psi}_{\alpha}$ is $0$ with probability roughly $1/(\alpha p)$). Hence, the Hamming distance of $\mathbf{t}$ from $Q\mathbf{s}$ is roughly $m(1-1/(\alpha p))$. Moreover, it can be seen that for large enough $m$, for any other word $\mathbf{s}^{\prime}$, the Hamming distance of $\mathbf{t}$ from $Q\mathbf{s}^{\prime}$ is roughly $m(1-1/p)$. Hence, we obtain that approximating the nearest codeword problem to within factors smaller than $(1-1/p)/(1-1/(\alpha p))$ on random codes is as hard as quantumly approximating worst-case lattice problems. This gives a partial answer to the important open question of understanding the hardness of decoding from random linear codes.

It turns out that certain problems, which are seemingly easier than the LWE problem, are in fact equivalent to the LWE problem. We establish these equivalences in Section 4 using elementary reductions. For example, being able to distinguish a set of equations as above from a set of equations in which the $b_{i}$’s are chosen uniformly from ${\mathbb{Z}}_{p}$ is equivalent to solving LWE. Moreover, it is enough to correctly distinguish these two distributions for some non-negligible fraction of all $\mathbf{s}$. The latter formulation is the one we use in our cryptographic applications.

In Section 5 we present a public key cryptosystem and prove that it is secure based on the hardness of the LWE problem. We use the standard security notion of semantic, or IND-CPA, security (see, e.g., [20, Chapter 10]). The cryptosystem and its security proof are entirely classical. In fact, the cryptosystem itself is quite simple; the reader is encouraged to glimpse at the beginning of Section 5. Essentially, the idea is to provide a list of equations as above as the public key; encryption is performed by summing some of the equations (forming another equation with error) and modifying the right hand side depending on the message to be transmitted. Security follows from the fact that a list of equations with error is computationally indistinguishable from a list of equations in which the $b_{i}$’s are chosen uniformly.

By using our main theorem, we obtain that the security of the system is based also on the worst-case quantum hardness of approximating SIVP and GapSVP to within $\tilde{O}(n^{1.5})$. In other words, breaking our cryptosystem implies an efficient quantum algorithm for approximating SIVP and GapSVP to within $\tilde{O}(n^{1.5})$. Previous cryptosystems, such as the Ajtai-Dwork cryptosystem [4] and the one by Regev [36], are based on the worst-case (classical) hardness of the unique-SVP problem, which can be related to GapSVP (but not SIVP) through the recent result of Lyubashevsky and Micciancio [26].

Another important feature of our cryptosystem is its improved efficiency. In previous cryptosystems, the public key size is $\tilde{O}(n^{4})$ and the encryption increases the size of messages by a factor of $\tilde{O}(n^{2})$. In our cryptosystem, the public key size is only $\tilde{O}(n^{2})$ and encryption increases the size of messages by a factor of only $\tilde{O}(n)$. This possibly makes our cryptosystem practical. Moreover, using an idea of Ajtai [3], we can reduce the size of the public key to $\tilde{O}(n)$. This requires all users of the cryptosystem to share some (trusted) random bit string of length $\tilde{O}(n^{2})$. This can be achieved by, say, distributing such a bit string as part of the encryption and decryption software.

We mention that learning problems similar to ours were already suggested as possible sources of cryptographic hardness in, e.g., [10, 7], although this was done without establishing any connection to lattice problems. In another related work [3], Ajtai suggested a cryptosystem that has several properties in common with ours (including its efficiency), although its security is not based on worst-case lattice problems.

This paper is almost entirely classical. In fact, quantum is needed only in one step in the proof of the main theorem. Making this step classical would make the entire reduction classical. To demonstrate the difficulty, consider the following situation. Let $L$ be some lattice and let $d=\lambda_{1}(L)/n^{10}$ where $\lambda_{1}(L)$ is the length of the shortest nonzero vector in $L$. We are given an oracle that for any point $\mathbf{x}\in\mathbb{R}^{n}$ within distance $d$ of $L$ finds the closest lattice vector to $\mathbf{x}$. If $\mathbf{x}$ is not within distance $d$ of $L$, the output of the oracle is undefined. Intuitively, such an oracle seems quite powerful; the best known algorithms for performing such a task require exponential time. Nevertheless, we do not see any way to use this oracle classically. Indeed, it seems to us that the only way to generate inputs to the oracle is the following: somehow choose a lattice point $\mathbf{y}\in L$ and let $\mathbf{x}=\mathbf{y}+\mathbf{z}$ for some perturbation vector $\mathbf{z}$ of length at most $d$. Clearly, on input $\mathbf{x}$ the oracle outputs $\mathbf{y}$. But this is useless since we already know $\mathbf{y}$!

It turns out that quantumly, such an oracle is quite useful. Indeed, being able to compute $\mathbf{y}$ from $\mathbf{x}$ allows us to uncompute $\mathbf{y}$. More precisely, it allows us to transform the quantum state ${|{\mathbf{x},\mathbf{y}}\rangle}$ to the state ${|{\mathbf{x},0}\rangle}$ in a reversible (i.e., unitary) way. This ability to erase the contents of a memory cell in a reversible way seems useful only in the quantum setting.

Unlike previous constructions of lattice-based public-key cryptosystems, the proof of our main theorem uses an ‘iterative construction’. Essentially, this means that instead of ‘immediately’ finding very short vectors in a lattice, the reduction proceeds in steps where in each step shorter lattice vectors are found. So far, such iterative techniques have been used only in the construction of lattice-based one-way functions [2, 12, 27, 29]. Another novel aspect of our main theorem is its crucial use of quantum computation. Our cryptosystem is the first classical cryptosystem whose security is based on a quantum hardness assumption (see [30] for a somewhat related recent work).

Our proof is based on the Fourier transform of Gaussian measures, a technique that was developed in previous papers [36, 29, 1]. More specifically, we use a parameter known as the smoothing parameter, as introduced in [29]. We also use the discrete Gaussian distribution and approximations to its Fourier transform, ideas that were developed in [1].

The main open question raised by this work is whether Theorem 1.1 can be dequantized: can the hardness of LWE be established based on the classical hardness of SIVP and GapSVP? We see no reason why this should be impossible. However, despite our efforts over the last few years, we were not able to show this. As mentioned above, the difficulty is that there seems to be no classical way to use an oracle that solves the closest vector problem within small distances. Quantumly, however, such an oracle turns out to be quite useful.

Another important open question is to determine the hardness of the learning from parity with errors problem (i.e., the case $p=2$). Our theorem only works for $p>2\sqrt{n}$. It seems that in order to prove similar results for smaller values of $p$, substantially new ideas are required. Alternatively, one can interpret our inability to prove hardness for small $p$ as an indication that the problem might be easier than believed.

Finally, it would be interesting to relate the LWE problem to other average-case problems in the literature, and especially to those considered by Feige in [15]. See Alekhnovich’s paper [7] for some related work.

We now describe some of the followup work that has appeared since the original publication of our results in 2005 [37].

One line of work focussed on improvements to our cryptosystem. First, Kawachi, Tanaka, and Xagawa [21] proposed a modification to our cryptosystem that slightly improves the encryption blowup to $O(n)$, essentially getting rid of a $\log$ factor. A much more significant improvement is described by Peikert, Vaikuntanathan, and Waters in [34]. By a relatively simple modification to the cryptosystem, they managed to bring the encryption blowup down to only $O(1)$, in addition to several equally significant improvements in running time. Finally, Akavia, Goldwasser, and Vaikuntanathan [6] show that our cryptosystem remains secure even if almost the entire secret key is leaked.

Another line of work focussed on the design of other cryptographic protocols whose security is based on the hardness of the LWE problem. First, Peikert and Waters [35] constructed, among other things, CCA-secure cryptosystems (see also [33] for a simpler construction). These are cryptosystems that are secure even if the adversary is allowed access to a decryption oracle (see, e.g., [20, Chapter 10]). All previous lattice-based cryptosystems (including the one in this paper) are not CCA-secure. Second, Peikert, Vaikuntanathan, and Waters [34] showed how to construct oblivious transfer protocols, which are useful, e.g., for performing secure multiparty computation. Third, Gentry, Peikert, and Vaikuntanathan [16] constructed an identity-based encryption (IBE) scheme. This is a public-key encryption scheme in which the public key can be any unique identifier of the user; very few constructions of such schemes are known. Finally, Cash, Peikert, and Sahai [13] constructed a public-key cryptosystem that remains secure even when the encrypted messages may depend upon the secret key. The security of all the above constructions is based on the LWE problem and hence, by our main theorem, also on the worst-case quantum hardness of lattice problems.

The LWE problem has also been used by Klivans and Sherstov to show hardness results related to learning halfspaces [22]. As before, due to our main theorem, this implies hardness of learning halfspaces based on the worst-case quantum hardness of lattice problems.

Finally, we mention two results giving further evidence for the hardness of the LWE problem. In the first, Peikert [32] somewhat strengthens our main theorem by replacing our worst-case lattice problems with their analogues for the $\ell_{q}$ norm, where $2\leq q\leq\infty$ is arbitrary. Our main theorem only deals with the standard $\ell_{2}$ versions.

In another recent result, Peikert [33] shows that the quantum part of our proof can be removed, leading to a classical reduction from GapSVP to the LWE problem. As a result, Peikert is able to show that public-key cryptosystems (including many of the above LWE-based schemes) can be based on the classical hardness of GapSVP, resolving a long-standing open question (see also [26]). Roughly speaking, the way Peikert circumvents the difficulty we described earlier is by noticing that the existence of an oracle that is able to recover $\mathbf{y}$ from $\mathbf{y}+\mathbf{z}$, where $\mathbf{y}$ is a random lattice point and $\mathbf{z}$ is a random perturbation of length at most $d$, is by itself a useful piece of information as it provides a lower bound on the length of the shortest nonzero vector. By trying to construct such oracles for several different values of $d$ and checking which ones work, Peikert is able to obtain a good approximation of the length of the shortest nonzero vector.

Removing the quantum part, however, comes at a cost: the construction can no longer be iterative, the hardness can no longer be based on SIVP, and even for hardness based on GapSVP, the modulus $p$ in the LWE problem must be exponentially big unless we assume the hardness of a non-standard variant of GapSVP. Because of this, we believe that dequantizing our main theorem remains an important open problem.

For two real numbers $x$ and $y>0$ we define $x~{}{\rm{mod}}~{}y$ as $x-{\lfloor x/y\rfloor}y$. For $x\in\mathbb{R}$ we define ${\lfloor x\rceil}$ as the integer closest to $x$ or, in case two such integers exist, the smaller of the two. For any integer $p\geq 2$, we write ${\mathbb{Z}}_{p}$ for the cyclic group $\{0,1,\ldots,p-1\}$ with addition modulo $p$. We also write $\mathbb{T}$ for $\mathbb{R}/{\mathbb{Z}}$, i.e., the segment $[0,1)$ with addition modulo $1$.

We define a negligible amount in $n$ as an amount that is asymptotically smaller than $n^{-c}$ for any constant $c>0$. More precisely, $f(n)$ is a negligible function in $n$ if $\lim_{n\to\infty}n^{c}f(n)=0$ for any $c>0$. Similarly, a non-negligible amount is one which is at least $n^{-c}$ for some $c>0$. Also, when we say that an expression is exponentially small in $n$ we mean that it is at most $2^{-\Omega(n)}$. Finally, when we say that an expression (most often, some probability) is exponentially close to $1$, we mean that it is $1-2^{-\Omega(n)}$.

We say that an algorithm ${\cal A}$ with oracle access is a distinguisher between two distributions if its acceptance probability when the oracle outputs samples of the first distribution and its acceptance probability when the oracle outputs samples of the second distribution differ by a non-negligible amount.

Essentially all algorithms and reductions in this paper have an exponentially small error probability, and we sometimes do not state this explicitly.

For clarity, we present some of our reductions in a model that allows operations on real numbers. It is possible to modify them in a straightforward way so that they operate in a model that approximates real numbers up to an error of $2^{-n^{c}}$ for arbitrary large constant $c$ in time polynomial in $n$.

Given two probability density functions $\phi_{1},\phi_{2}$ on $\mathbb{R}^{n}$, we define the statistical distance between them as

(notice that with this definition, the statistical distance ranges in $[0,2]$). A similar definition can be given for discrete random variables. The statistical distance satisfies the triangle inequality, i.e., for any $\phi_{1},\phi_{2},\phi_{3}$,

Another important fact which we often use is that the statistical distance cannot increase by applying a (possibly randomized) function $f$, i.e.,

see, e.g., [28]. In particular, this implies that the acceptance probability of any algorithm on inputs from $X$ differs from its acceptance probability on inputs from $Y$ by at most $\frac{1}{2}\Delta(X,Y)$ (the factor half coming from the choice of normalization in our definition of $\Delta$).

Recall that the normal distribution with mean 0 and variance $\sigma^{2}$ is the distribution on $\mathbb{R}$ given by the density function $\frac{1}{\sqrt{2\pi}\cdot\sigma}{{\mathrm{exp}}\left(-\frac{1}{2}(\frac{x}{\sigma})^{2}\right)}$ where ${{\mathrm{exp}}\left(y\right)}$ denotes $e^{y}$. Also recall that the sum of two independent normal variables with mean 0 and variances $\sigma_{1}^{2}$ and $\sigma_{2}^{2}$ is a normal variable with mean 0 and variance $\sigma_{1}^{2}+\sigma_{2}^{2}$. For a vector $\mathbf{x}$ and any $s>0$, let

be a Gaussian function scaled by a factor of $s$. We denote $\rho_{1}$ by $\rho$. Note that $\int_{\mathbf{x}\in\mathbb{R}^{n}}\rho_{s}(\mathbf{x})d\mathbf{x}=s^{n}$. Hence,

is an $n$-dimensional probability density function and as before, we use $\nu$ to denote $\nu_{1}$. The dimension $n$ is implicit. Notice that a sample from the Gaussian distribution $\nu_{s}$ can be obtained by taking $n$ independent samples from the $1$-dimensional Gaussian distribution. Hence, sampling from $\nu_{s}$ to within arbitrarily good accuracy can be performed efficiently by using standard techniques. For simplicity, in this paper we assume that we can sample from $\nu_{s}$ exactly.⁴⁴4In practice, when only finite precision is available, $\nu_{s}$ can be approximated by picking a fine grid, and picking points from the grid with probability approximately proportional to $\nu_{s}$. All our arguments can be made rigorous by selecting a sufficiently fine grid. Functions are extended to sets in the usual way; i.e., $\rho_{s}(A)=\sum_{\mathbf{x}\in A}\rho_{s}(\mathbf{x})$ for any countable set $A$. For any vector $\mathbf{c}\in\mathbb{R}^{n}$, we define $\rho_{s,\mathbf{c}}(\mathbf{x}):=\rho_{s}(\mathbf{x}-\mathbf{c})$ to be a shifted version of $\rho_{s}$. The following simple claim bounds the amount by which $\rho_{s}(\mathbf{x})$ can shrink by a small change in $\mathbf{x}$.

• Proof:

  Using the inequality $e^{-z}\geq 1-z$,

  $\displaystyle\rho_{s}(\mathbf{y})=e^{-\pi\|\mathbf{y}/s\|^{2}}$

  $\displaystyle\geq e^{-\pi(\|\mathbf{x}\|/s+l/s)^{2}}=e^{-\pi(2l\|\mathbf{x}\|/s^{2}+(l/s)^{2})}\rho_{s}(\mathbf{x})\geq(1-\pi(2lt+l^{2})/s^{2})\rho_{s}(\mathbf{x}).$

   

For any countable set $A$ and a parameter $s>0$, we define the discrete Gaussian probability distribution $D_{A,s}$ as

See Figure 2 for an illustration.

For $\beta\in\mathbb{R}^{+}$ the distribution $\Psi_{\beta}$ is the distribution on $\mathbb{T}$ obtained by sampling from a normal variable with mean $0$ and standard deviation $\frac{\beta}{\sqrt{2\pi}}$ and reducing the result modulo $1$ (i.e., a periodization of the normal distribution),

Clearly, one can efficiently sample from $\Psi_{\beta}$. The following technical claim shows that a small change in the parameter $\beta$ does not change the distribution $\Psi_{\beta}$ by much.

• Proof:

  We will show that the statistical distance between a normal variable with standard deviation $\alpha/\sqrt{2\pi}$ and one with standard deviation $\beta/\sqrt{2\pi}$ is at most $9(\frac{\beta}{\alpha}-1)$. This implies the claim since applying a function (modulo $1$ in this case) cannot increase the statistical distance. By scaling, we can assume without loss of generality that $\alpha=1$ and $\beta=1+\varepsilon$ for some $0<\varepsilon\leq 1$. Then the statistical distance that we wish to bound is given by

  	$\displaystyle\int_{\mathbb{R}}\bigg{|}e^{-\pi x^{2}}-\frac{1}{1+\varepsilon}\,e^{-\pi x^{2}/(1+\varepsilon)^{2}}\bigg{|}dx$	$\displaystyle\leq\int_{\mathbb{R}}\big{|}e^{-\pi x^{2}}-e^{-\pi x^{2}/(1+\varepsilon)^{2}}\big{|}dx+\int_{\mathbb{R}}\bigg{|}\Big{(}1-\frac{1}{1+\varepsilon}\Big{)}e^{-\pi x^{2}/(1+\varepsilon)^{2}}\bigg{|}dx$
  		$\displaystyle=\int_{\mathbb{R}}\big{|}e^{-\pi x^{2}}-e^{-\pi x^{2}/(1+\varepsilon)^{2}}\big{|}dx+\varepsilon$
  		$\displaystyle=\int_{\mathbb{R}}\big{|}e^{-\pi(1-1/(1+\varepsilon)^{2})x^{2}}-1\big{|}\,e^{-\pi x^{2}/(1+\varepsilon)^{2}}dx+\varepsilon.$

  Now, since $1-z\leq e^{-z}\leq 1$ for all $z\geq 0$,

  $\displaystyle\big{|}e^{-\pi(1-1/(1+\varepsilon)^{2})x^{2}}-1\big{|}\leq\pi(1-1/(1+\varepsilon)^{2})x^{2}\leq 2\pi\varepsilon x^{2}.$

  Hence we can bound the statistical distance above by

  $\displaystyle\varepsilon+2\pi\varepsilon\int_{\mathbb{R}}x^{2}e^{-\pi x^{2}/(1+\varepsilon)^{2}}dx=\varepsilon+\varepsilon(1+\varepsilon)^{3}\leq 9\varepsilon.$

   

For an arbitrary probability distribution with density function $\phi:\mathbb{T}\rightarrow\mathbb{R}^{+}$ and some integer $p\geq 1$ we define its discretization $\bar{\phi}:{\mathbb{Z}}_{p}\rightarrow\mathbb{R}^{+}$ as the discrete probability distribution obtained by sampling from $\phi$, multiplying by $p$, and rounding to the closest integer modulo $p$. More formally,

As an example, $\bar{\Psi}_{\beta}$ is shown in Figure 1.

Let $p\geq 2$ be some integer, and let $\chi:{\mathbb{Z}}_{p}\rightarrow\mathbb{R}^{+}$ be some probability distribution on ${\mathbb{Z}}_{p}$. Let $n$ be an integer and let $\mathbf{s}\in{\mathbb{Z}}_{p}^{n}$ be a vector. We define $A_{\mathbf{s},\chi}$ as the distribution on ${\mathbb{Z}}_{p}^{n}\times{\mathbb{Z}}_{p}$ obtained by choosing a vector $\mathbf{a}\in{\mathbb{Z}}_{p}^{n}$ uniformly at random, choosing $e\in{\mathbb{Z}}_{p}$ according to $\chi$, and outputting $(\mathbf{a},{\langle{\mathbf{a},\mathbf{s}}\rangle}+e)$, where additions are performed in ${\mathbb{Z}}_{p}$, i.e., modulo $p$. We also define $U$ as the uniform distribution on ${\mathbb{Z}}_{p}^{n}\times{\mathbb{Z}}_{p}$.

For a probability density function $\phi$ on $\mathbb{T}$, we define $A_{\mathbf{s},\phi}$ as the distribution on ${\mathbb{Z}}_{p}^{n}\times\mathbb{T}$ obtained by choosing a vector $\mathbf{a}\in{\mathbb{Z}}_{p}^{n}$ uniformly at random, choosing $e\in\mathbb{T}$ according to $\phi$, and outputting $(\mathbf{a},{\langle{\mathbf{a},\mathbf{s}}\rangle}/p+e)$, where the addition is performed in $\mathbb{T}$, i.e., modulo $1$.