3
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Daniel S
    Apr 15, 2023 at 10:14
  • $\begingroup$ Ah ok! That is understandable. Even though I have to admit that this is not quite clear to me from the first quote. $\endgroup$
    – P_Gate
    Apr 15, 2023 at 10:20

0

Your Answer

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

Browse other questions tagged or ask your own question.