2
$\begingroup$

I was reading CRYSTALS-Kyber design. They have used compress_q(x,d) to scale an element of $\mathbb{Z}_q$ to $[ 0,1,...,2^d-1 ]$. The definitions of compress_q(x,d) and decompress_q(x,d) are as follows: $$ Compress_q(x,d) = \left\lfloor (2^d/q)\cdot x\right\rceil mod^{+}2^d $$ $$ Decompress_q(x,d) = \left\lfloor (q/2^d)\cdot x\right\rceil $$

Further, they have stated that

The main reason for defining the Compress_q and Decompress_q functions is to be able to discard some low-order bits in the ciphertext which do not have much effect on the correctness probability of decryption

Question:

What does discarding low-order bits means ? Is it related to discarding the LSBs?

I have written a python code to check but LSBs of x are not getting discarded after applying compress_q function. However, MSBs does flips to 0. So can you help me in understanding the above doubts?

Python code

import math
def binary(a,l):
    return bin(a)[2:].zfill(l)
def rounding(x):
    return math.floor(x+0.5)
def compress(q,x,d):
    return rounding((pow(2,d)/q)*x) % (pow(2,d))
def decompress(q,x,d):
    return rounding((q/(pow(2,d)))*x)

q = 3329 
d = 10
bitlen = math.ceil(math.log(q,2))
x = 531
print("x,compress(x)\t\t\t",x,"\t", compress(q,x,d))
print("bin(x)\t\t\t\t",binary(x,bitlen))
print("bin(compress(x))\t\t",binary(compress(q,x,d),bitlen))
print("bin(decompress(compress(x)))\t",binary(decompress(q,compress(q,x,d),d),bitlen))
print("\n\n")

Output

x,compress(x)                    531     163
bin(x)                           001000010011
bin(compress(x))                 000010100011
bin(decompress(compress(x)))     001000010010
$\endgroup$
2
  • 1
    $\begingroup$ You should break this up into two questions, as the two things you ask about aren't related (except for both showing up in Kyber). $\endgroup$
    – Mark Schultz-Wu
    Commented Dec 31, 2023 at 4:34
  • $\begingroup$ @Mark I have removed the 2nd question, will ask in some other posts. $\endgroup$
    – ABCD
    Commented Dec 31, 2023 at 5:01

2 Answers 2

2
$\begingroup$

One way to interpret the "discarding low order bits" remark is to think of ciphertexts under various moduli as corresponding to binary floating point values in the range $[0,1)$. The correspondence being that we associate a ciphertext $c$ modulo $m$ with the floating point value $(c\mod^{\pm})/m$. Thus in your example x corresponds to 531/3329=0.0010100011010.... The compress function chooses the nearest binary flow that corresponds to a rational with denominator dividing $2^d$, which by the nature of binary representation is equivalent to rounding to the $d$th binary digit. In other words discarding the bits in positions $d+1$ onwards. In your example compress(x) corresponds to 163/1024=0.0010100011.

Decompression finds the nearest binary float with denominator dividing $q$ which in binary float correspondence overwrites the bits in positions after $d$ with a value appropriate to meet the denominator criterion.

Although decompress(compress(x)) is not necessarily the same as x, their binary float values do not differ by much (the worst cast is differing by about $2^{-d-1}$). The difference between the two values can be thought of as an additional contribution to the errors in learning with errors (some prefer the term "learning with rounding" for such deterministic methods of adding noise). Just as learning with errors systems can decrypt with high probability provided that the errors are small, learning-with-errors-and-rounding systems such as ML-KEM (Kyber) can decrypt with high probability provided that both the errors and rounding-loss are small.

$\endgroup$
0
$\begingroup$

Discarding the bits doesn't mean they're cleared to 0, it means they're left unspecified after Decompress.

Since the message was Decompress'd from the bit-string m into $\mu$, the polynomial $\mu$ consist of large values that corresponds to 0s and 1s from m. So when it's Compress'd during decryption in K-PKE.Decrypt, m can be correctly recovered. The inner-working of this trick is too clever to be explained by me.

$\endgroup$

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.