# Understand LWE(Learning With Error) negligible error probability

According to Regev's paper, p15

Correctness. Note that if not for the error in the LWE samples, $b-⟨a, s⟩$ would be either 0 or ⌊ q ⌋ depending on the encrypted bit, and decryption would always be correct. Hence we see that a decryption error occurs only if the sum of the error terms over all S is greater than q/4. Since we are summing at most m normal error terms, each with standard deviation αq, the standard deviation of the sum is at most $\sqrt{m}\alpha q < q \log{n}$; a standard calculation shows that the probability that such a normal variable is greater than q/4 is negligible.

I did a little experiment with mathematica and the resulting probability of decryption error is around 0.28. Can you point out where I was wrong?

Firstly I build the the following variables as in the paper:

In:= n=10
q=RandomPrime[{n^2,2n^2}]
m=1.1*n*Log[q]
α=1/(Sqrt[n]*Log[n]^2)
σ=α * q
Floor[q/2]
q/4
Out= 10
Out= 131
Out= 53.6272
Out= 1/(Sqrt*Log^2)
Out= 131/(Sqrt*Log^2)
Out= 65
Out= 131/4


Then I calculate the maximum probability that the error terms sum is greater than q/4 by calculating the value of the Cumulative Probability function when x is -q/4:

In:= (*Probability that sum is greater than q/4*)
CDF[NormalDistribution[0,Sqrt[m]*α*q],-q/4]
Out= 0.279785


As you can see, it's too large for "negligible" so I think there's something wrong with my calculation.

Here are the PDF for a single error $e$ and the sum of errors: Single error Sum of errors

## 2 Answers

Denote by $X$ the random variable which is the sum over all $S$. As mentioned, this is a Gaussian of standard deviation at most $\sqrt{m}r$ with $r = \alpha q$. Hence, by properties of the (sub-)Gaussian distribution you have that

$$\operatorname{Pr}\left[|X| > t\right]\leq 2\exp\left(\frac{-\pi t^2}{r^2m}\right)$$

so, for $t = \frac{q}{2}$ you have

$$\operatorname{Pr}\left[|X| > \frac{q}{2}\right]\leq 2\underbrace{\exp\left(\frac{-\pi \left(\frac{q}{2}\right)^2}{r^2m}\right)}_{\varepsilon(n)}$$

From there you can see that by choosing $q(n)$ appropriately (e.g. with the parameters proposed in the paper), you can make of $\varepsilon(n)$ a negligible function. This does not necessarily mean that, once you fix a particular $n$, this probability is 'small'. What it means intuitively is that as $n$ grows this probability gets smaller and smaller at a good rate, while keeping the parameters 'practical' (i.e. polynomial).

The probability of error is negligible "as a function of $n$", meaning that the probability of error will decrease (quickly) as $n$ grows. Increasing $n$ should solve your issue.