1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – user108142
    Commented Mar 15, 2023 at 9:41
  • $\begingroup$ Additionally, can I know how to generate errors for ciphertext (u, v), where they match with the binary message m? $\endgroup$
    – user108142
    Commented Mar 15, 2023 at 11:03
  • $\begingroup$ 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. $\endgroup$
    – Daniel S
    Commented Mar 16, 2023 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.