# CRYSTALS-Kyber - Decryption and Decoding

I have a question about the decryption in Kyber [1]. I will first give important statements of the paper and then ask my actual question with an example.

In the paper it is stated:

... decrypt to a 1 if $$v-s^Tu$$ is closer to $$\lceil \frac{q}{2} \rfloor$$ then to 0, and decrypt to a 0 otherwise.

On the other hand, when decrypting, it is stated in Algorithm 3:

retrun $$Compress_q(v-s^Tu,1)$$

And note that $$Compress_q(v-s^Tu,1) = \lceil \frac{2}{q}x \rfloor \text{ mod}^+ \, 2$$

My background is as follows, I have constructed an example to understand more precisely how Kyber works. However, in the example, I largely omit compression and decompression in the encryption/decryption, except for decryption at the end (this is necessary).

I obtained the following result in the context of the example $$v-s^Tu = 7x^3 +14x^2 +7x +5,$$ where $$q=17$$ (Other parameters are not relevant here, because I am only interested in the decryption based on this result).

Using the quoted statements from above, there are two ways I can decode this, and that's the tricky part, because these two statements don't give the same result!

1. decryption ($$v-s^Tu = 7x^3 +14x^2 +7x +5$$) according to the first quote:
• I proceed component by component:
• 7 is closer to $$\lceil \frac{q=17}{2} \rfloor = 9$$ than to 0, so this is decoded to a 1.
• 14 is closer to $$\lceil \frac{q=17}{2} \rfloor = 9$$ than to 0, therefore this is decoded to a 1.
• 7 is closer to $$\lceil \frac{q=17}{2} \rfloor = 9$$ than to 0, therefore this is decoded to a 1.
• 5 is closer to $$\lceil \frac{q=17}{2} \rfloor = 9$$ than to 0, therefore this is decoded to a 1.
1. decryption ($$v-s^Tu = 7x^3 +14x^2 +7x +5$$) according to the second quote:
• I proceed component-wise:
• $$\lceil \frac{2}{q=17}7 \rfloor \text{ mod}^+ \, 2 = 1$$
• $$\lceil \frac{2}{q=17}14 \rfloor \text{ mod}^+ \, 2 = 0$$
• $$\lceil \frac{2}{q=17}7 \rfloor \text{ mod}^+ \, 2 = 1$$
• $$\lceil \frac{2}{q=17}5 \rfloor \text{ mod}^+ \, 2 = 1$$

So we see that the results are not the same when decoding.

Open question:

• The question for me is whether the first quote is somewhat incomplete? Because the first quote automatically implies, to my understanding, that elements larger than $$\lceil \frac{q}{2} \rfloor$$ are automatically decoded as 1, because they are closer to $$\lceil \frac{q}{2} \rfloor$$ then to 0.

• In the context of the first quote, it would then also be interesting to see how decoding would be performed if an element is located exactly between 0 and $$\lceil \frac{q}{2} \rfloor$$.

• When we talk about closer in the context of modular reduction, we include the wrap-around feature. Thus the distance between 14 and 0 is 3 when we work modulo 17. This is smaller than the distance between 14 and 9 which is 5. We therefore decode to 0. Apr 15, 2023 at 10:14
• Ah ok! That is understandable. Even though I have to admit that this is not quite clear to me from the first quote. Apr 15, 2023 at 10:20