# Kyber - Compression and Decompression Implementation Example

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

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.
• 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... Commented Mar 19 at 8:44
• @TreeBook1 Note $[qx/2^d+1/2]=[(qx+2^d/2)/2^d]$=(q*x+1024)>>11 for $d=11$. Commented Mar 19 at 8:46
• 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$ Commented Mar 19 at 8:56
• 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. Commented Mar 19 at 8:58
• 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. Commented Mar 19 at 9:02