LWE encryption: Errors for encrypted messages

I am following this paper Encryption from Learning with Errors for the generation of errors e1 and e2 to retrieve the ciphertext u and v as described below.

u = Ar + e1
v = br + m (q/2) + e2


For this text:

We require for this algorithm to work that the χ distribution has a mean of zero and, with overwhelming probability falls into the range [−q/4, q/4]. If we require perfect correctness, then we can round e into this range.

I am not exactly sure what it means. Does [−q/4, q/4] refer to numerical values or does it refer to the modulo arithmetic of 1/4 mod q?

If it refers to numerical value, can I confirm what type of error is it referring to? As far as I know, there are two types of errors for encryption and decryption. The errors added to message e1 and e2, and the common error e retrieved in the decryption phase after v - s*u

For example, in the decryption, we have: v – s * u = (br + m (q/2) + e2) – s (Ar + e1) = (e2 – e1) + m(q/2). = e + m(q/2)

e = e2 - e1 falls in the range of (-q/4, q/4). Is the same also true for e1 and e2?

Note: throughout I use the notation of the paper where non-bold letters represent (scalar) numerical values, bold lower case letter represent (column) vectors and bold uppercase letters represent matrices.

The range is for (rational) numerical values. For example, if $$q=31$$ the range is $$[-7\frac34,7\frac34]$$ and as the value of $$e$$ is an integer this means $$e\in \{-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7\}$$.

The value $$e$$ referred to is the difference between the values $$v$$ and $$\mathbf s^T\mathbf u$$.

However, your example is an incorrect expansion because $$v-\mathbf s^T\mathbf u=(\mathbf b^T\mathbf r +\mu(q/2)+ e_1)-\mathbf s^T(\mathbf A \mathbf r+\mathbf e_2)=(e_1+\mathbf e_0^T\mathbf r-\mathbf s^T\mathbf e_2)+\mu(q/2)$$ where $$\mathbf e_0=\mathbf b-\mathbf A\mathbf s$$.

Note that this error is the sum of $$m+n+1$$ terms, $$m+n$$ of which are products of entries of $$\mathbf e_0$$ and $$\mathbf e_2$$ with entries of $$\mathbf r$$ and $$\mathbf s$$. Thus we expect this accumulated error to be significantly bigger than the components of $$\mathbf e_0$$, $$e_1$$, and $$\mathbf e_2$$.

• Thanks, can I know what range do the errors of the ciphertext (u, v) in the encryption process fall into? How can I derive the values for them? Mar 15, 2023 at 9:41
• Additionally, can I know how to generate errors for ciphertext (u, v), where they match with the binary message m? Mar 15, 2023 at 11:03
• If the entries to $\mathbf r$, $\mathbf s$, $\mathbf e_0$ and $\mathbf e_1$ are all less than $\sqrt{q/4(m+n+1)}$ an $e$ is less than $q/4(m+n+1)$ then the accumulated error is sure to be less than $q/4$ is size and so successful decryption would be assured. OTOH It is safer cryptanalytically to allow large entries. The paper that you quote suggests sampling these values from a discrete Gaussian. Choosing a Gaussian with variance around $q/4(m+n+1)$ will produce few failures. In practical implementations such as Kyber a centred binomial distribution is preferred for ease of implementation. Mar 16, 2023 at 14:21