Implementation Realities: The NTT, Constant-Time Decapsulation, and the Parameter Sets

The mathematics of the previous four articles guarantees security against an adversary who sees only inputs and outputs. A real implementation runs on real hardware, and hardware leaks — through the time a comparison takes, the power a multiplication draws, the electromagnetic signature of a memory access. A perfectly correct ML-KEM can be broken by a single secret-dependent branch in its decapsulation, so the standard's security depends as much on disciplined engineering as on the proofs. This article covers the two realities that dominate a deployment: the number-theoretic transform that makes the arithmetic fast, and the constant-time implementation that keeps the secret from leaking through the physical side channels the proofs do not model.

The number-theoretic transform

The core operation is multiplying polynomials in the ring, and doing it naively is quadratic in the dimension. The number-theoretic transform makes it near-linear. It is the finite-field analogue of the fast Fourier transform: it maps a polynomial to its evaluations at special points, where multiplication becomes cheap pointwise multiplication, then maps back. The modulus and dimension of ML-KEM were chosen precisely to make this transform available — the prime modulus satisfies the congruence condition that provides the roots of unity the transform needs over the field of that modulus.

In practice this means polynomials are transformed once and then multiplied coordinate-by-coordinate, and much of the scheme's data is kept directly in the transformed domain to avoid repeated conversions — public keys and parts of ciphertexts are stored and transmitted already transformed. Multiplication of two ring elements becomes: transform each, multiply pointwise, and transform the result back, all in near-linear time. This is the single most important reason the scheme is fast enough to run on essentially every connection.

The efficiency has a correctness corollary an implementer must respect: the transform and its inverse must be applied consistently, and mixing transformed and untransformed values is a classic bug. Because so much data lives in the transformed domain, keeping careful track of which representation each value is in is part of getting the implementation right, quite apart from the security concerns of the next sections.

Constant-time decapsulation

Decapsulation touches the secret key, so every step of it must run in time and with a memory-access pattern that is independent of secret values. The moment the duration of an operation, or which cache line it touches, depends on a secret, an attacker measuring that timing learns something about the secret — the classic timing side channel. For ML-KEM the most delicate spot is the Fujisaki-Okamoto machinery: the re-encryption comparison and the implicit rejection both handle secret-dependent data and must be implemented without any secret-dependent branch.

The re-encryption check compares the recomputed ciphertext to the received one, and a naive comparison that returns as soon as it finds a mismatching byte takes a secret-dependent amount of time, leaking whether and where the ciphertexts differ. It must instead be a constant-time comparison that examines every byte regardless. The implicit rejection then selects between the real key and the rejection key based on the comparison result, and this selection must be a constant-time conditional move — computing both and choosing without a branch — rather than an if-statement that a timing or branch-prediction attacker could observe.

The same discipline extends throughout: no secret-dependent array indices, since which memory address is accessed leaks through the cache; no early exits from loops over secret data; and careful zeroization of secret intermediate values after use. These are not micro-optimizations to skip but correctness requirements for security, and they are why one uses a reviewed, constant-time library rather than a direct transcription of the specification's pseudocode, which is written for clarity, not for constant-time execution.

Beyond timing: power and electromagnetic channels

Timing is the most accessible side channel but not the only one. On devices an attacker can physically access — smart cards, embedded modules, edge hardware — the power consumption and electromagnetic emanations during decapsulation also correlate with the secret, and analyzing many traces can extract key material even from a constant-time implementation. Defending these requires additional countermeasures such as masking, where secret values are split into random shares processed separately so that no single measured quantity depends on the secret directly.

These physical countermeasures are costly and are applied where the threat model warrants — hardware security modules, secure elements, and any device an adversary can hold. For a server in a data center the dominant concern is timing and microarchitectural leakage rather than power analysis, so a well-reviewed constant-time software implementation is usually the appropriate bar. Matching the countermeasures to the deployment's actual exposure is part of choosing an implementation.

The general principle is that the security proofs assume an idealized black box, and every way the real device deviates from that box is a potential leak. Constant-time execution closes the timing deviation; masking and shielding close the power and electromagnetic deviations; and which of these a deployment needs depends on who can get close to the hardware. Naming the physical threat model explicitly is the first step to implementing against it.

The parameter sets

ML-KEM is standardized in three parameter sets, differing only in the module rank as the earlier lattice articles described. The table lists them with their public-key and ciphertext sizes and the security categories they target; the shared secret is thirty-two bytes in every case. The sizes are modest — around one to one-and-a-half kilobytes — which is what makes the mechanism practical to run on every connection despite being larger than the elliptic-curve exchange it augments.

The recommended general-purpose default is the middle set, targeting the third security category, which is the one deployed in the widely used hybrid key exchange that pairs it with a classical elliptic-curve exchange. That hybrid is the payload now protecting a great deal of model-API and agent-to-service traffic, chosen so that the session remains secure as long as either the classical or the post-quantum component holds. The lowest set suits constrained or lower-assurance contexts, and the highest is reserved for the most sensitive, long-lived secrets.

The choice among sets follows the same logic as everywhere in this track: match the security category to the data's sensitivity and lifetime, take the standardized parameters unchanged, and prefer the higher category for anything that must remain confidential for decades against a future quantum adversary harvesting today's traffic.

Pitfalls, and the deployment posture

The recurring implementation pitfalls are worth naming so they can be avoided. A non-constant-time comparison in the re-encryption check is the classic mistake and directly reintroduces a chosen-ciphertext attack through timing. A weak or misused random-number generator undermines the freshness that encapsulation and key generation depend on. Confusing transformed and untransformed representations produces subtle correctness bugs. And failing to zeroize secret intermediates leaves key material in memory to be recovered later. Each is easy to make and each is serious.

The disciplined posture that avoids all of them is to use a validated, reviewed implementation rather than writing one from the specification. The specification's pseudocode is written to be understood, not to be constant-time or side-channel-resistant, and a faithful transcription of it is very likely to leak. Conformance-tested libraries, ideally validated under the relevant cryptographic-module standards, have had these concerns addressed and reviewed, which is exactly why one prefers them over a hand-rolled port.

For autonomous AI systems the guidance closes the series cleanly. Do not implement ML-KEM; call a validated library. Use the recommended hybrid parameter set for agent and model-API traffic, so that a break in either the classical or the post-quantum component does not compromise the session. Ensure ephemeral key exchange, as the previous article urged, and confirm the library is constant-time. The whole edifice built across this series — the LWE encryption, the KEM abstraction, the Fujisaki-Okamoto transform, the failure defenses — delivers its guarantees only through an implementation that respects these physical realities, and treating that implementation as a validated component rather than an in-house project is the final discipline.

Practitioner Toolkit

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

ml_kem_implementation:
  source: validated_conformance_tested_library
  decapsulation: constant_time
  reencrypt_compare: all_bytes
  implicit_rejection: branchless_conditional_move
  rng: strong_and_correct
  secrets: zeroized_after_use
deployment:
  parameter_set: ml_kem_768_hybrid
  key_mode: ephemeral
  physical_countermeasures: match_threat_model

Glossary

Number-theoretic transform (NTT)

A finite-field analogue of the fast Fourier transform giving near-linear polynomial multiplication; the modulus is chosen to make it exist.

Transformed domain

The evaluation representation in which multiplication is pointwise; ML-KEM stores much data here to avoid repeated conversions.

Constant-time execution

Running with timing and memory-access patterns independent of secret values, so no secret leaks through timing or cache behavior.

Constant-time comparison / conditional move

A comparison examining all bytes regardless, and a branchless selection, used in the re-encryption check and implicit rejection.

Masking

Splitting secret values into random shares processed separately, so no single measured quantity depends on the secret — a defense against power and electromagnetic analysis.

Validated implementation

A reviewed, conformance-tested (ideally module-validated) library, preferred over a transcription of the specification's clarity-oriented pseudocode.

References

1. NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024)
2. Bos et al., CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM (IEEE EuroS&P, 2018)
3. Hofheinz, Hovelmanns & Kiltz, A Modular Analysis of the Fujisaki-Okamoto Transformation (TCC, 2017)
4. D'Anvers et al., On the Impact of Decryption Failures on the Security of LWE/LWR-Based Schemes (IACR ePrint 2018/1089)
5. Lyubashevsky, Peikert & Regev, On Ideal Lattices and Learning with Errors over Rings (EUROCRYPT, 2010)