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