2
$\begingroup$

I have a question about the implementation of the functions

$$Compress_q(x,d) = \left\lfloor (2^d/q)\cdot x\right\rceil mod^{+}2^d$$

and

$$Decompress_q(x,d) = \left\lfloor (q/2^d)\cdot x\right\rceil$$

from Kyber.

I have copied two lines from the GitRepo, which contain the compression:

t[k]  = ((((uint32_t)t[k] << 11) + KYBER_Q/2)/KYBER_Q) & 0x7ff;

and the decompression

r->vec[i].coeffs[8*j+k] = ((uint32_t)(t[k] & 0x7FF)*KYBER_Q + 1024) >> 11;

for the case $d=11$.

  • Regarding the first code snippet, why do we add $q/2$, what is the idea behind it? The shift is clear and with $0x7FF$ we can reduce this to values $mod^{+} 2^d$.

  • In the second snippet why do we add $1024$? Wouldn't we have to shift first and then round down? So, how is the function $\left\lfloor ... \right\rceil$ represented?

  • For me it seems that they have implemented it by using $\lfloor x \rceil = \lfloor x + 1/2\rfloor$.

$\endgroup$

1 Answer 1

1
$\begingroup$

In the first line of code the addition of $q/2$ is to change the floor value $[2^dx/q]$ returned by the integer division into the rounded value $\lfloor 2^d/q\rceil$ value required for the function.

The constant 0x7ff = $2^{11}-1=2^d-1$ is used to mask off the low 11-bits which is the same as reducing mod $2^d-1$.

In the second line of code the 0x7ff seems to be a defensive measure to ensure that the t[k] has been reduced mod $2^d$. The addition of $2^{10}=2^d/2$ is again to convert the floor value returned by the left shift to the rounded value returned by the function.

$\endgroup$
6
  • $\begingroup$ Hi Daniel S, I agree with most of the things you said. The expression 0x7ff has the special character of working as $mod^{+} 2^d$. It seems as they have used $\lfloor x \rceil = \lfloor x + 1/2\rfloor$. The addition with $2^d/2$ is not so clear... $\endgroup$
    – TreeBook1
    Commented Mar 19 at 8:44
  • 1
    $\begingroup$ @TreeBook1 Note $[qx/2^d+1/2]=[(qx+2^d/2)/2^d]$=(q*x+1024)>>11 for $d=11$. $\endgroup$
    – Daniel S
    Commented Mar 19 at 8:46
  • $\begingroup$ Ok, I see it :) (Just write down what it says. :) ) And then similarily $\lfloor 2^d x / q\rceil = [(2^dx + q/2)/q] = ((x << 11) + q/2)/q$ $\endgroup$
    – TreeBook1
    Commented Mar 19 at 8:56
  • $\begingroup$ Your left hand side should read something like $\lfloor 2^dx/q\rceil=[2^dx/q+1/2]=...$, but yes, I think that you have it. $\endgroup$
    – Daniel S
    Commented Mar 19 at 8:58
  • $\begingroup$ Thanks! It think the crucial part is to note $\lfloor x \rceil = \lfloor x + 1/2\rfloor$. By the way is there a "clear" (mathematical) explanation of the rounding function $\lfloor x \rceil$ in the literature (I see this function often in a lattice crypto context... With definition: "rounding up to the nearest integer")? The border cases are interesting. $\endgroup$
    – TreeBook1
    Commented Mar 19 at 9:02

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.