All-or-Nothing Transforms and the Extra Tightness in ML-KEM

A KEM that is secure against chosen-plaintext attack is not secure in the world where attackers can submit decapsulation queries. The standard bridge from one to the other is the Fujisaki-Okamoto transform, and every standardised post-quantum KEM uses some form of it. The transform is not free: it converts a CPA-secure scheme into a CCA-secure one at the price of a security loss, and for lattice schemes the loss has a specific shape that parameter sets must account for. ML-KEM’s specification includes an all-or-nothing transform to absorb that cost, and understanding where the loss comes from explains why the decapsulation code hashes the ciphertext twice.

What the transform does to a plaintext-ciphertext pair

The starting point is a scheme where a public key $pk$ and a random message $m$ produce a ciphertext $c$, and the holder of the secret key recovers $m$ from $c$ up to some noise. The transform replaces the randomness with a hash of the message: $c = \mathrm{Enc}(pk, m; H(m))$, and the ciphertext is accompanied by a hash of $m$ and $c$. Decryption recovers $m’$, recomputes $c’ = \mathrm{Enc}(pk, m’; H(m’))$, and accepts only if $c’ = c$. The randomness now depends on the message, so an attacker who tampers with $c$ has to produce a message whose deterministic encryption matches the tampered ciphertext, which is the preimage problem for the hash.

Formally, the CPA-to-CCA reduction loses a factor proportional to the number of decapsulation queries $q_D$, because the attacker can try $q_D$ different ciphertexts and each is an independent attempt to produce a valid one. A scheme with a $2^{-64}$ cheating probability against one query has a $q_D \cdot 2^{-64}$ probability across $q_D$ queries. Modern KEM analyses distinguish this from the tighter bound obtained by explicitly tracking the one-shot success probability $P_{correct}$ of a valid ciphertext being rejected or an invalid one being accepted, and by using the fact that the hash is modelled as a random oracle so each forged ciphertext has an independent chance.

Two structural weaknesses of the plain transform matter for lattice schemes. The first is that the transform can reveal the decryption of a related ciphertext when the underlying scheme’s decryption is randomised with a distribution that the attacker can distinguish from fresh randomness. The second is that the scheme’s decryption function can fail, and the attacker can potentially distinguish a failure from a successful decryption by observing whether the recomputed ciphertext matches. Both are avoided in the ML-KEM design by the construction called the FO$^{\not\perp}$ variant: on failure, decapsulation returns a pseudorandom key that is a function of the secret and the ciphertext, so the caller never learns whether the ciphertext was valid.

Where a lattice twist enters the reduction

Lattice KEMs have a property that RSA and finite-field KEMs do not: decryption can fail for legitimate ciphertexts with a small but nonzero probability. The plaintext-recovery step for ML-KEM has an error probability that the FIPS 203 parameter analysis bounds near $2^{-164}$ for the highest-parameterised set. In a reduction, that failure probability enters as a term that the attacker can exploit: after submitting a valid ciphertext and receiving a key, the attacker may learn whether the plaintext recovery failed, because the key returned in the implicit-rejection branch differs from the key returned in the success branch. If the attacker can raise the failure probability artificially by choosing ciphertexts that are close to the boundary, the security bound degrades by roughly $q_D \cdot P_{fail}$, which is the term the parameter analysis pays for.

The concern is sharpened by the fact that the randomness used inside encapsulation must be derived from the message, including its noise. In ML-KEM the pseudorandom matrix is derived from the public key seed, and the encapsulation randomness is expanded from a 32-byte message by an XOF; a change in the derivation would change the distribution of noise vectors and hence the failure probability. Implementations must use the exact KDF chain specified in the standard, because a different truncation of the same hash output changes the sampled noise, and the failure bound is computed for the specified one.

The FH-ANF construction addresses the tightness issue from a different angle. When a scheme has a non-negligible correctness error, the classic FO proof loses a factor that is hard to bound because the failure event is not independent of the attacker’s chosen ciphertext. In the pre-standardisation versions of Kyber, and in the round-two submission documents, the designers analysed an all-or-nothing transform over the hash inputs so that a successful attack had to invert a full-length hash. The transform builds the message seed from a chain involving the public key hash, the message, and the ciphertext, so no component can be varied independently without changing the others.

The chain of hashes in the decapsulation path

FIPS 203 specifies the flow in terms of three functions, and the order matters. Encapsulation hashes the public key with an XOF, derives the matrix from the seed and the row index, samples the noise from a PRF keyed by the message, and computes the ciphertext. The message-carrying component is reduced to a polynomial with coefficients at $0$ and $\lceil q/2 \rceil$, which is the part that is recovered at decapsulation, and the final “key” output is not the message but a separate hash of the ciphertext and the message-carrying polynomial. Decapsulation recovers the ciphertext, the message polynomial, and then hashes to reproduce the key. A recomputation of the whole encapsulation path is then compared against the received ciphertext.

The all-or-nothing behaviour comes from the fact that the KDF input includes the hash of the ciphertext in addition to the recovered message. An attacker who manipulates the ciphertext to bias the message recovery cannot separate the two, because the hash binds them. The pre-standard Kyber design used a variant where the ciphertext hash was folded in one level earlier, and the change was motivated by a specific multi-target attack that exploited the separation. The lesson is that the reduction’s tightness depends on the exact wiring, not just on the presence of a hash.

Encaps(pk, m):
  seed   = H(pk)                        // expand A deterministically
  A      = XOF(seed, 0..k-1)
  r, e1, e2 = PRF(m)                   // noise vectors, seeded by message
  u = A^T r + e1
  v = t^T r + e2 + Encode(m)
  c = Compress(u) || Compress(v)
  K = Hash(Hash(c) || Hash(m))          // key derived from message and ciphertext
  return (c, K)

Decaps(sk, c):
  m' = Decode(Decompress(c))
  c' = Encaps(pk, m').c                // deterministic re-encryption
  K  = (c == c') ? Hash(Hash(c) || Hash(m'))
                 : Hash(z || Hash(c))  // implicit rejection, z from sk
  return K

The two branches return values of the same length and the comparison is performed without early exit, so the timing of decapsulation is independent of validity. The implicit-rejection branch uses $z$, a value expanded from the secret key at key generation, so an adversary without the secret cannot predict the rejection key.

Two failure modes deserve attention. If $z$ is stored with insufficient entropy or is derived from the same seed as the matrix, an attack that recovers one value may recover both; the standard separates them through distinct domain separators. If the comparison of $c$ and $c’$ is implemented with a library function that short-circuits on the first differing byte, the timing reveals how many bytes of the re-encryption matched, which is a partial-validity oracle and sufficient to mount a Bleichenbacher-style attack. Constant-time comparison is the mechanism that keeps the implicit rejection implicit. The arithmetic side of the same problem appears in constant-time lattice arithmetic, where the same discipline applies to the noise sampling and NTT.

The bandwidth cost of implicit rejection

The rejection branch is cheap in computation and free in ciphertext size, since no extra value is transmitted. Its cost is in key material: an extra 32-byte secret value per key, expanded from the seed in a way that does not reuse the matrix seed. The alternative explicit-rejection design sends an error indicator, which costs a bit in the ciphertext and leaks the validity of any ciphertext the attacker can probe. The design choice in the standard favours the implicit form because the bandwidth is already dominated by the compressed $u$ vector, and adding a flag would change the length of every ciphertext, which interacts badly with the fixed-size record layer of the protocol carrying it.