Decryption Failures in Lattice KEMs
Decryption failure is the surprising fact that ML-KEM, a standardized cryptographic algorithm, can occasionally return the wrong answer. When two parties use ML-KEM to agree on a shared secret, there is a tiny but genuinely nonzero probability that the receiver decapsulates to a different secret than the sender encapsulated, so the key agreement silently fails. This is not a bug. It is a direct consequence of the small random noise that makes Learning With Errors hard in the first place, and the designers accept it because pushing the probability to exactly zero would cost too much in performance. What matters is that the failure probability is a security parameter, kept astronomically small on purpose, because an attacker who could provoke failures could learn the private key.
The short version:
- Lattice KEMs can occasionally decapsulate to the wrong shared secret. The noise that hides the secret in LWE can, very rarely, push a value across a rounding boundary and produce a mismatch, so correctness is not perfect.
- The failure probability is a designed parameter, not an accident. ML-KEM’s parameters set it at levels like roughly 2^-139 for the smallest set, far too rare to ever see in practice but not zero.
- The Fujisaki-Okamoto transform is what makes this safe. It handles malformed ciphertexts by re-encrypting and checking, which is why a failure or an attack attempt does not leak a usable secret.
- Failures are a security parameter because of failure-boosting attacks. D’Anvers and colleagues showed an attacker can hunt for and amplify failure-prone ciphertexts to attack a scheme whose failure rate is too high, so the probability must stay tiny.
- This is why the standard is intolerant of sloppy parameters. A scheme with a comfortable failure rate is not merely inconvenient, it is potentially insecure, which is why NIST pins the probability so low.
Picture a lock that reads a magnetic keycard, and the reader has a whisker of tolerance built in so a slightly worn card still works. That tolerance is what lets the system function in the real world, but it also means that once in a very great while a card lands right at the edge of the tolerance and the reader guesses wrong. A designer can shrink that tolerance to make wrong guesses rarer, at the cost of rejecting more worn cards, or widen it for convenience at the cost of more mistakes. Lattice decryption has exactly this kind of tolerance built into its rounding, and the failure probability is the dial that sets how close to the edge the system is allowed to run.
What is a decryption failure in a lattice KEM?
A decryption failure is the event where the legitimate holder of the private key runs decapsulation correctly and still recovers a shared secret different from the one the sender encapsulated. In a lattice key-encapsulation mechanism like ML-KEM, the sender hides a secret inside a noisy equation and the receiver uses the private key to cancel the noise and read it back. The final step of reading it back involves rounding a noisy number to the nearest clean value. Almost always the noise is small enough that the rounding lands on the right value. Very rarely, the accumulated noise is large enough to tip the number over a rounding boundary, and the receiver rounds to the wrong value, producing a shared secret that does not match the sender’s.
Source: NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard, August 13, 2024, csrc.nist.gov.
The important reframing is that this noise is the same noise that provides the security. Learning With Errors is hard precisely because every equation is blurred by a small random error, and that same blur is what occasionally pushes a decryption over the edge. So there is a fundamental tension baked into every lattice KEM: more noise means a harder problem for the attacker and also a higher chance of a legitimate decryption error, while less noise means cleaner decryption and a weaker security margin. The parameters are tuned to a sweet spot where the problem is hard enough and the failures are rare enough, and “rare enough” turns out to be a security requirement in its own right.
How rare are the failures, and why keep them possible at all?
The failures are made so rare that they are effectively never observed in the lifetime of any real deployment, but the probability is deliberately kept nonzero because driving it to exactly zero would force wasteful parameter choices. ML-KEM’s three parameter sets carry decryption failure probabilities on the order of 2^-139, 2^-164, and 2^-174 for ML-KEM-512, ML-KEM-768, and ML-KEM-1024 respectively. To put the smallest of those in perspective, 2^-139 is a chance so small that you could run key exchanges continuously for longer than the age of the universe and expect to never see one.
| Parameter set | NIST security category | Decryption failure probability |
|---|---|---|
| ML-KEM-512 | 1 | about 2^-139 |
| ML-KEM-768 | 3 | about 2^-164 |
| ML-KEM-1024 | 5 | about 2^-174 |
Source: NIST FIPS 203, August 13, 2024, csrc.nist.gov; decryption-failure probability figures per the CRYSTALS-Kyber round-3 specification, pq-crystals.org.
The reason for stopping at “astronomically rare” instead of “impossible” is economics. A perfectly error-free lattice scheme would need either much larger, slower parameters (more room between the rounding boundaries) or much smaller noise (a weaker security margin), and neither is a good trade. Accepting a vanishingly small failure probability lets the designers keep keys and ciphertexts compact and the noise generous, which is what makes ML-KEM efficient enough to drop into TLS and everyday protocols. The engineering judgment is that a probability like 2^-139 is close enough to zero for every practical purpose while buying real performance, so the standard treats correctness as overwhelming rather than absolute.
How does the Fujisaki-Okamoto transform handle failures and attacks?
The Fujisaki-Okamoto transform is the construction that lets a lattice scheme tolerate imperfect decryption and hostile inputs without leaking its secret, and it is why ML-KEM is safe against an attacker who submits carefully chosen ciphertexts. The underlying encryption piece of ML-KEM is only weakly secure on its own, safe against a passive eavesdropper but not against an active attacker who mails in doctored ciphertexts to see how the receiver reacts. The FO transform upgrades it to the strong IND-CCA2 security that resists exactly that kind of active, chosen-ciphertext attack.
Source: E. Fujisaki, T. Okamoto, “Secure Integration of Asymmetric and Symmetric Encryption Schemes,” CRYPTO ‘99, IACR; modular analysis and correctness-error treatment per D. Hofheinz, K. Hövelmanns, E. Kiltz, “A Modular Analysis of the Fujisaki-Okamoto Transformation,” TCC 2017, IACR ePrint 2017/604.
The mechanism is a re-encryption check. During decapsulation, after the receiver recovers what the message should have been, the FO transform re-runs the encryption on that recovered message using the same randomness and confirms it reproduces the ciphertext that arrived. A tampered or malformed ciphertext will not reproduce itself under re-encryption, so the check catches it, and decapsulation returns a pseudorandom “implicit rejection” value that reveals nothing about the private key.
This is where correctness and security meet. The same re-encryption check that catches an attacker’s doctored ciphertext also governs how the rare genuine failure is handled, and the modular security proofs for the FO transform explicitly fold the decryption-failure probability into the security bound, so the tiny failure rate is accounted for rather than ignored.
Why is the failure probability a security parameter?
The failure probability is a security parameter because an attacker who can find and provoke decryption failures can use them to claw back information about the private key, an attack strategy called failure boosting. Jan-Pieter D’Anvers, Frederik Vercauteren, and Ingrid Verbauwhede showed in 2018 that decryption failures are an exploitable channel rather than a mere correctness nuisance. Every failing ciphertext an attacker can produce leaks a little geometric information about where the secret sits, and enough of that information adds up to a key-recovery attack against a scheme whose failure rate is high enough to make failures findable.
Source: J.-P. D’Anvers, F. Vercauteren, I. Verbauwhede, “On the impact of decryption failures on the security of LWE/LWR based schemes,” IACR ePrint 2018/1089.
The “boosting” part is what makes this sharp. Rather than wait for a random failure, which even at a moderate rate would take too long, an attacker searches for ciphertexts that are unusually likely to fail (ones whose built-in noise leans in a helpful direction) and submits those, amplifying the effective failure rate they see. This turns the decryption failure probability directly into a security budget: if failures are too common, an attacker can boost their way to enough of them to recover the key.
NIST’s parameters keep the probability so low that even an aggressively boosting attacker cannot gather enough failures within any feasible number of queries, which is precisely why the figures sit down around 2^-139 and lower rather than at some merely-convenient level. The consequence is that a lattice KEM’s correctness and its security are the same dial viewed from two sides, and a scheme with a sloppy failure rate carries a real security hole.
Common misconceptions
- “A standardized cipher never returns the wrong answer.” Lattice KEMs are an exception by design. The noise that makes LWE hard can rarely tip a decryption over a rounding boundary, so ML-KEM carries a tiny, deliberate probability of decapsulating to the wrong shared secret.
- “Decryption failures are a bug that should be fixed to zero.” Driving the probability to exactly zero would demand larger, slower parameters or weaker noise, both bad trades. The engineering choice is a probability so small (around 2^-139) it is never seen in practice, which keeps the scheme fast while staying safe.
- “A failure just means retry, so it does not matter.” It matters because failures leak information. Failure-boosting attacks can exploit a scheme whose failures are common enough to find, so the probability is a genuine security parameter, not merely a reliability figure.
- “The Fujisaki-Okamoto transform only concerns active attackers and has nothing to do with failures.” The same re-encryption check that rejects an attacker’s doctored ciphertext also frames how the rare genuine failure is handled, and the FO security proofs fold the failure probability directly into the security bound.
- “If I ever see an ML-KEM decapsulation mismatch, the algorithm is broken.” At a probability around 2^-139, a genuine mismatch will not occur in any real deployment’s lifetime, so an observed mismatch points to an implementation bug, corrupted data, or a fault, rather than the algorithm itself.
Questions people ask
Can ML-KEM decryption actually fail? Yes, with a tiny nonzero probability. The noise that secures LWE can rarely push a decrypted value across a rounding boundary and produce the wrong shared secret. The probability is set around 2^-139 for the smallest parameter set, so rare that it is never expected to occur in any real system’s lifetime.
Why keep any failure possibility instead of designing the scheme to never fail? Because a perfectly error-free lattice KEM would need larger and slower parameters or a weaker noise margin, and both hurt. Accepting a vanishingly small failure probability keeps ML-KEM compact and fast enough for TLS and everyday protocols, which is the trade the standard makes.
How does the Fujisaki-Okamoto transform relate to decryption failures? The FO transform upgrades the weakly secure core encryption to strong IND-CCA2 security using a re-encryption check during decapsulation. That check rejects an attacker’s malformed ciphertexts with a pseudorandom value that leaks nothing, and the FO security proofs explicitly account for the decryption-failure probability in the bound.
What is a failure-boosting attack? A technique, shown by D’Anvers, Vercauteren, and Verbauwhede in 2018, where an attacker searches for ciphertexts especially likely to fail and submits those, amplifying the failure rate they observe. Because each failure leaks information about the private key, a high enough failure rate becomes a key-recovery path, which is why the probability must stay astronomically low.
Does a decryption failure leak my key? A single rare, genuine failure in normal operation does not hand over your key, and the FO transform ensures rejections reveal nothing usable. The danger is systemic: a scheme whose failures are common enough for an attacker to provoke in bulk can be attacked, which is exactly why NIST pins the probability so low that bulk provocation is infeasible.
Is the failure probability the same for every ML-KEM size? No, it varies by parameter set, sitting on the order of 2^-139 for ML-KEM-512, 2^-164 for ML-KEM-768, and 2^-174 for ML-KEM-1024. All three are far below any level a failure-boosting attacker could exploit, so each size is safe against this class of attack.
Everything here is the map, given freely. When your team needs the correctness and security properties of its post-quantum choices understood and defended to an auditor, that’s what an alignment briefing is for.
Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.