From LWE to a Public-Key Scheme: Compression, Rounding, and a Secret Hidden in Noise

Abstract

ML-KEM is built on top of a small public-key encryption scheme derived directly from Module-LWE, and this piece constructs that underlying scheme in full. It shows how the public key is a Module-LWE instance, how encryption masks the message with fresh noise and encodes each bit as either zero or half the modulus, and how decryption uses the secret key to cancel the noise and round back to the bit. It makes the decoding margin explicit — the total noise must stay below a quarter of the modulus — which introduces the small but nonzero failure probability that a later article turns into an attack surface. It explains the compression and rounding that shrink ciphertexts at the cost of a little more noise, and closes by noting that this scheme is only passively secure, setting up the transform that hardens it. The theme: the message is a secret hidden in noise, recoverable only by the key that knows how to subtract it.

The key-encapsulation mechanism that will protect most post-quantum traffic is built in two stages, and this article covers the first: a plain public-key encryption scheme derived straight from Module-LWE. The idea is elegant and physical. Encode each message bit as one of two widely separated values — zero or half the modulus — then bury it under fresh random noise so that the ciphertext looks uniform to anyone without the secret. The holder of the secret key can subtract away almost all of the noise, leaving each value close enough to zero or half the modulus to round back to the original bit. Everything else in ML-KEM is machinery to make this passively secure scheme actively secure and efficient; the core is this trick of hiding a secret in noise.

The public key is an LWE instance

Key generation produces exactly the Module-LWE instance of the earlier articles. A public matrix of ring elements is derived from a small seed, so it need not be transmitted in full. The secret key is a short vector of ring elements, and a second short vector serves as error. The public key is the matrix applied to the secret plus the error — a Module-LWE sample. Recovering the secret from the public key is therefore the module learning-with-errors problem, and its hardness is what keeps the secret key secret.

This reuse of the Module-LWE structure is deliberate: the encryption scheme inherits the key-secrecy guarantee directly from the assumption studied in the lattice-foundations track, with its worst-case-to-average-case backing and conservative parameters. Nothing new is assumed here beyond what already secures the signature and the raw problem. The public key is simply an LWE sample, and everything downstream builds on the fact that it looks random without the secret.

Deriving the public matrix from a seed rather than transmitting it is a small but important efficiency: the seed is a handful of bytes, and both parties expand it identically with an extendable output function. The transmitted public key is thus the seed plus the single short vector that is the LWE value, keeping public keys compact. With the key in place, the interesting part is how a message gets encrypted into a ciphertext that only this key can open.

\[\text{public key: } \mathbf{t} = A\,\mathbf{s} + \mathbf{e}, \quad \mathbf{s}, \mathbf{e} \text{ short}, \ A \text{ from a seed}\]

\[\text{recovering } \mathbf{s} \text{ from } (A, \mathbf{t}) = \text{Module-LWE, believed hard}\]

Encryption: mask with noise, encode the message

To encrypt, the sender draws its own fresh short randomness — a random vector and two small error terms — and produces two pieces. The first is the transpose of the public matrix applied to the random vector plus an error, which acts as a fresh ephemeral Module-LWE sample the sender creates. The second combines the public key with the same random vector, adds a small error, and adds the encoded message: each message bit is scaled by half the modulus, so a one becomes a value near the midpoint of the modulus and a zero stays near the bottom. The ciphertext is these two pieces together.

The structure is symmetric and purposeful. The first piece lets the receiver reconstruct the shared masking value using the secret key; the second carries the message offset by that same masking value plus the encoding. Because both pieces are Module-LWE-like — a public thing applied to fresh randomness plus small noise — the whole ciphertext is pseudorandom to an eavesdropper without the secret, which is where the passive security comes from. The message is present but hidden inside noise that looks like more LWE.

The encoding choice of zero versus half the modulus is what makes decoding robust. The two possible values per coordinate are as far apart as the modulus allows, so a fair amount of leftover noise can be tolerated before a zero could be mistaken for a one. That separation is the budget the next section spends.

Fresh randomness makes an ephemeral sample and masks the message, which is encoded as an offset of half the modulus and buried in small errors.

\[\mathbf{u} = A^{\top}\mathbf{r} + \mathbf{e}_1, \qquad v = \mathbf{t}^{\top}\mathbf{r} + e_2 + \lceil q/2 \rceil\, m\]

\[\mathbf{r}, \mathbf{e}_1, e_2 \text{ fresh and short}; \ m \in \{0,1\}^n\]

Decryption: subtract the noise, round to the bit

Decryption uses the secret key to remove the mask. The receiver computes the second ciphertext piece minus the secret applied to the first. Algebraically the large masking terms cancel, because both were built from the same public matrix and randomness, and what remains is the encoded message plus a small leftover noise: the message bit scaled by half the modulus, nudged by the accumulated errors from encryption and key generation. The masking value that made the ciphertext look random is exactly what the secret key knows how to subtract.

The leftover is then rounded. For each coordinate, if the value sits closer to half the modulus the bit was a one; if it sits closer to zero the bit was a zero. This succeeds precisely when the leftover noise is smaller than a quarter of the modulus, because that keeps every coordinate on the correct side of the midpoint between the two encoded values. The quarter-modulus decoding margin is the central quantitative fact of the scheme, and staying inside it is what correctness means.

Crucially, the margin is not always met. The noise is random, and there is a small probability that on some coordinate it exceeds a quarter of the modulus and flips a bit — a decryption failure. Parameters are chosen to make this probability astronomically small, but it is nonzero, and that nonzero tail is not a mere nuisance: a later article shows how an attacker who can provoke and detect failures turns them into a real threat. For now the point is that decryption is correct with overwhelming, but not certain, probability.

Each recovered coordinate decodes to zero or one by nearness to zero or half the modulus; correctness holds only while leftover noise stays under a quarter of the modulus.

\[v - \mathbf{s}^{\top}\mathbf{u} = \lceil q/2 \rceil\, m + \underbrace{(\mathbf{e}^{\top}\mathbf{r} - \mathbf{s}^{\top}\mathbf{e}_1 + e_2)}_{\text{small}}\]

\[\text{decode correctly} \iff |\text{noise}| < q/4; \quad \Pr[\text{failure}] > 0 \text{ but tiny}\]

Compression and rounding shrink the ciphertext

A raw ciphertext of two full vectors of ring elements is larger than it needs to be, so ML-KEM compresses it. Compression drops the low-order bits of each coordinate — rounding each value to a coarser grid with fewer bits — which shrinks the transmitted ciphertext substantially. This is a lossy operation and therefore adds a further, controlled rounding noise on top of the encryption noise, a flavor of the learning-with-rounding idea where deterministic rounding stands in for added error.

The compression is calibrated so that the extra rounding noise still fits within the decoding margin. The parameters account for encryption noise, key noise, and compression noise together, keeping their sum below a quarter of the modulus with overwhelming probability. In other words, compression spends part of the same noise budget the decoding margin provides, trading a little of the correctness cushion for a meaningful reduction in ciphertext size — a worthwhile exchange given how often ciphertexts are transmitted.

This is why ML-KEM ciphertexts are compact despite the underlying vectors being large: the second piece is compressed hard because it only needs to convey enough to decode a bit per coordinate, while the first piece is compressed less. The result is a scheme whose wire footprint is modest, which matters greatly for a mechanism that runs on essentially every connection.

\[\mathrm{Compress}(x, d) = \left\lceil (2^{d}/q)\, x \right\rfloor \bmod 2^{d}; \quad \text{drops low bits, adds rounding noise}\]

\[\text{parameters keep } |\text{enc noise} + \text{key noise} + \text{compression noise}| < q/4\]

Passively secure, and only that

The scheme just built is secure against a passive eavesdropper — an attacker who sees ciphertexts but cannot interact — under the Module-LWE assumption. This property, indistinguishability under chosen-plaintext attack, means an adversary cannot tell which of two chosen messages a ciphertext encrypts, because the ciphertext is pseudorandom. That is genuinely useful but genuinely limited: it says nothing about an attacker who can submit ciphertexts of its own and observe how the receiver reacts.

Such an active attacker is exactly the realistic threat for a key-encapsulation mechanism used in a protocol, where an adversary can send malformed ciphertexts and learn from acceptance, rejection, timing, or decryption failures. Against that attacker the plain scheme is not safe, and the small decryption-failure probability and the malleability of the ciphertext become exploitable. Turning this passively secure encryption into an actively secure key-encapsulation mechanism is the job of the Fujisaki-Okamoto transform, the subject of the third article, and understanding why the transform is necessary requires first defining precisely what active security demands, which the next article does.

For autonomous AI systems the relevance is immediate even at this foundational layer. The compact, LWE-based encryption here is the payload inside the hybrid key exchange now protecting model-API and agent-to-service traffic, where a classical elliptic-curve exchange is combined with ML-KEM so that the session stays secure if either component holds. Appreciating that the message is a secret hidden in noise, recoverable only within a quarter-modulus margin, is the foundation for understanding both why the scheme works and where, mishandled, it can fail.

📌

Passive security is not enough. The bare LWE encryption is only IND-CPA: safe against eavesdroppers, not against an attacker who submits ciphertexts and watches the receiver. The decryption-failure tail and ciphertext malleability are why the Fujisaki-Okamoto transform is needed.

Key takeaways

ML-KEM's underlying public-key encryption uses a Module-LWE instance as the public key, so key secrecy is the module learning-with-errors problem.
Encryption draws fresh short randomness to form an ephemeral sample and masks the message, encoding each bit as zero or half the modulus and burying it in small noise, so the ciphertext is pseudorandom.
Decryption subtracts the secret applied to the first ciphertext piece, canceling the mask and leaving the encoded bit plus small noise, then rounds by nearness to zero or half the modulus.
Correctness holds only while total leftover noise stays under a quarter of the modulus; the failure probability is astronomically small but nonzero — a tail a later attack exploits.
Compression drops low-order ciphertext bits to shrink the wire size, adding rounding noise that the parameters keep within the same decoding margin.
The scheme is only IND-CPA (passively secure); making it safe against active attackers who submit ciphertexts requires the Fujisaki-Okamoto transform, and it is the payload inside today's hybrid agent-traffic key exchange.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

✅Tracing the LWE encryptionchecklist

Follow a ciphertext from message to recovery.

Is the public key a Module-LWE sample (matrix times secret plus error)?
Does encryption add fresh short randomness and encode bits at zero or half the modulus?
Does decryption cancel the mask via the secret and round by nearness?
Is the total noise (encryption, key, compression) kept under a quarter of the modulus?
Is the residual decryption-failure probability documented as nonzero?

🚀Situate ML-KEM's corequickstart

Place the underlying encryption before adding the transform.

Confirm the scheme is only IND-CPA at this stage.
Identify the decoding margin and the failure probability.
Note where compression spends part of the noise budget.
Recognize the FO transform as the next step toward active security.

🔒KEM-core assurance notepolicy

A stub recording the underlying encryption's properties.

kem_underlying_pke:
  public_key: module_lwe_sample
  encoding: bit_times_half_modulus
  decoding_margin: quarter_modulus
  failure_probability: nonzero_tiny
  compression: drops_low_bits
security_stage:
  level: IND-CPA_only
  needs: fo_transform_for_cca

Illustrative documentation template, not a product config.

Glossary

Module-LWE public key: The public key t = A s + e, a Module-LWE sample whose secret s is hard to recover, providing key secrecy.
Message encoding: Scaling each message bit by half the modulus so a one sits near the midpoint and a zero near the bottom, maximizing decode separation.
Decoding margin: The requirement that total leftover noise stay below a quarter of the modulus, so each coordinate rounds to the correct bit.
Decryption failure: The small-probability event that noise exceeds the margin and flips a decoded bit; nonzero and later exploitable.
Compression / rounding: Dropping low-order ciphertext bits to shrink size, adding controlled rounding noise kept within the decoding margin (a learning-with-rounding flavor).
IND-CPA: Indistinguishability under chosen-plaintext attack: security against a passive eavesdropper, insufficient against active attackers.