Compression and Ciphertext Size

Ciphertexts travel on the wire, so their size is a real cost paid on every connection. ML-KEM throws away low-order bits deliberately, and the error budget from Why Decryption Works is what says how many it can afford.

01.The operation

$$\text{Compress}_q(x, d) \;=\; \left\lceil \frac{2^d}{q} \cdot x \right\rfloor \bmod 2^d, \qquad \text{Decompress}_q(y, d) \;=\; \left\lceil \frac{q}{2^d} \cdot y \right\rfloor .$$

The half-square brackets denote rounding to the nearest integer.

Read it plainly. Compression rescales a value from the range $[0, q)$ down to $[0, 2^d)$ and rounds. Decompression rescales back. The round trip does not return the original, because information was discarded, but it returns something close.

Concretely with $q = 3329$ and $d = 4$, the whole range of $3329$ possible coefficient values is squeezed into $16$ buckets, each about $208$ wide. Decompressing returns the centre of the bucket, so the error is at most about $104$.

02.Where the widths come from

The two parts of the ciphertext are compressed differently: $d_u = 10$ bits per coefficient for $\mathbf{u}$, and $d_v = 4$ for $v$. That is a factor of sixty-four difference in how much is thrown away, and the reason is in the error equation.

Recall the two extra terms compression added:

$$\delta' \;=\; \cdots \;-\; \mathbf{s}^\top \mathbf{c}_u \;+\; c_v .$$

The noise on $\mathbf{u}$ arrives multiplied by the secret $\mathbf{s}$. That multiplication is a full ring product, summing $n$ terms, so even though $\mathbf{s}$ is small the product accumulates. Compression noise on $\mathbf{u}$ is therefore amplified before it reaches the budget, and $\mathbf{u}$ has to be treated carefully.

The noise on $v$ arrives alone. It is added once, at whatever size it is, and nothing multiplies it. So $v$ can be compressed far harder for the same cost to the budget.

Hence $d_u = 10$ and $d_v = 4$. It is a nice illustration of how a scheme's constants are not arbitrary: each one is the answer to an inequality.

03.The saving

Uncompressed, every coefficient needs 12 bits, since $q = 3329$ needs 12. For ML-KEM-768, an uncompressed ciphertext would be

$$\frac{3 \cdot 256 \cdot 12}{8} \;+\; \frac{256 \cdot 12}{8} \;=\; 1152 + 384 \;=\; 1536 \text{ bytes}.$$

Compressed, it is

$$\frac{3 \cdot 256 \cdot 10}{8} \;+\; \frac{256 \cdot 4}{8} \;=\; 960 + 128 \;=\; 1088 \text{ bytes}.$$

A saving of $448$ bytes, just under thirty percent, on every ciphertext ever sent.

Across all three parameter sets:

ML-KEM-1024 saves less proportionally because it uses gentler compression, $d_u = 11$ and $d_v = 5$. At the highest security level the error budget is tighter relative to the noise, so less can be discarded.

04.Why the public key is not compressed

The public key is $1184$ bytes for ML-KEM-768 and is sent uncompressed. Given that ciphertexts save thirty percent, the obvious question is why keys do not.

Two reasons, and the second is the real one.

The public key is stored in NTT domain, as Key Generation explained. Transformed coefficients are uniform across the full range with no structure to exploit, and compressing them would discard bits that the arithmetic genuinely needs.

More fundamentally, compressing the public key would inject rounding error into $\mathbf{t}$, which appears in the correctness equation on the key generation side. Bob's secret cannot compensate for it, because Bob does not know which way each coefficient was rounded and cannot recover that from $sk$. Ciphertext compression works precisely because its error lands in $\delta'$ where the budget absorbs it. Public key compression has no such landing place.

There is also an asymmetry of usage that makes the trade less attractive anyway. A public key is fetched once and cached, often inside a certificate that is itself several kilobytes. A ciphertext is sent on every single connection. Optimising the thing that travels constantly is worth more than optimising the thing that travels once.

05.The encoding, briefly

One implementation detail that causes trouble in practice. Compressed coefficients are $d$ bits wide and $d$ is not a multiple of $8$, so the serialised ciphertext is a densely packed bitstream rather than a byte array. Ten-bit values pack four to every five bytes.

FIPS 203 specifies the packing exactly, down to bit order, because two implementations that pack differently produce different ciphertexts from identical inputs and fail to interoperate. This is the kind of detail that has no mathematical content and consumes real engineering time, and it is worth knowing it is there before meeting it in a test vector mismatch.