up:: The New Standards MOC

Fujisaki-Okamoto (FO) Transform

The Fujisaki-Okamoto (FO) transform is a general construction that upgrades a public-key encryption scheme from “safe against a passive eavesdropper” to “safe against an active attacker who can submit chosen ciphertexts.” It does this by having the recipient re-encrypt the message it just decrypted and check that the result matches the ciphertext that arrived. If they match, the recipient releases the real shared secret; if they differ, it returns a random-looking value instead of an error.

That re-encrypt-and-compare step is the mechanism that gives ML-KEM its chosen-ciphertext security, which is why every serious post-quantum KEM is a weakly-secure encryption core wrapped in an FO transform. It is not an algorithm and not a standard on its own; it is the construction pattern that sits between a KEM’s internal encryption engine and the hardened KEM the world actually deploys.

Source: NIST, “Module-Lattice-Based Key-Encapsulation Mechanism Standard,” FIPS 203, August 13, 2024, csrc.nist.gov/pubs/fips/203/final.

The short version:

• The FO transform turns an IND-CPA-secure encryption scheme (safe only against a passive eavesdropper) into an IND-CCA2-secure one (safe against an active attacker who submits chosen ciphertexts). It is the standard way to reach that stronger security.
• The problem it solves is a decryption-failure oracle: raw lattice and code-based encryption leaks secret information from whether a deliberately malformed ciphertext decrypts successfully. The transform closes that leak.
• Its defining move is at decapsulation: decrypt the ciphertext, re-encrypt the recovered message, and compare the recomputed ciphertext against the one that arrived. A match means the ciphertext was honest.
• ML-KEM wraps its IND-CPA-secure core (called K-PKE) in a variant of the FO transform, which is exactly how ML-KEM reaches IND-CCA2 security. The K-PKE core is not approved for standalone use.
• ML-KEM uses “implicit rejection”: on a mismatch it returns a pseudorandom value derived from the ciphertext and a stored secret seed, so success and failure look identical from the outside and give an attacker no accept/reject hint.
• The transform is inherited by the migration, not retired by it. Its security is proven in the random oracle model and holds up in the quantum version of that model (the QROM), which is why it survives into the post-quantum era.

Picture a bank teller who receives a written withdrawal slip. A naive teller just reads the slip and pays out, and an attacker learns things by watching which malformed slips get honored and which get rejected. An FO teller does something stricter: after reading your slip, they rewrite a fresh copy of exactly what a valid slip for that request should look like, then hold it up against the slip you handed in. If the two copies match to the letter, the request was genuine and gets paid. If they differ in any way, the teller hands back a sealed envelope of nonsense that looks just like a real payout, so a fraudster watching the window cannot tell an accepted slip from a rejected one. That silent rewrite-and-match is the whole idea.

What is the Fujisaki-Okamoto transform?

The FO transform is a generic construction, introduced by Fujisaki and Okamoto in 1999 and refined in modern variants, that converts an IND-CPA-secure public-key encryption scheme into an IND-CCA2-secure one, and in the post-quantum standards a KEM. “Generic” means it is a wrapper: it takes a weakly-secure encryption primitive and produces a strongly-secure one, without caring about the internal math of the primitive it wraps.

The two security levels it bridges are worth naming precisely, because the whole point of the transform lives in the gap between them:

1. IND-CPA security protects against a passive attacker who can encrypt messages of their choosing but cannot ask anyone to decrypt for them. This is the “safe against an eavesdropper” level.
2. IND-CCA2 security protects against an active attacker who can also submit ciphertexts of their choosing and observe how the system responds. This is the “safe against a real network adversary” level, and it is what deployed cryptography needs.

The problem the transform solves is a specific and dangerous leak. Raw lattice-based and code-based public-key encryption schemes, the cores of the post-quantum KEMs, are only IND-CPA-secure. Exposed directly, they hand an attacker a decryption-failure oracle: the attacker submits deliberately malformed ciphertexts, watches whether each one decrypts cleanly or fails, and gradually learns secret information from the pattern of successes and failures, enough to recover the private key. The FO transform closes that oracle, which is why it sits between the encryption core and the KEM in every one of these standards.

Source: NIST, “Module-Lattice-Based Key-Encapsulation Mechanism Standard,” FIPS 203, August 13, 2024, csrc.nist.gov/pubs/fips/203/final.

How does the re-encryption check work?

The transform’s defining move is to make decapsulation prove to itself that the ciphertext is well-formed, without ever telling the outside world whether it was. On the sending side, the sender derives the ciphertext and a candidate shared secret deterministically from a chosen message and the public key, using hash functions, and transmits the ciphertext. The work that matters happens on the receiving side. Following the shape ML-KEM specifies for decapsulation:

1. Decrypt the received ciphertext c with the private key to recover a candidate message m'.
2. Derive a candidate shared secret K' from m' and a hash of the public key.
3. Prepare a fallback secret from a stored secret seed z and the ciphertext c, ready in case the check fails.
4. Re-encrypt m' under the public key to produce a fresh ciphertext c'.
5. Compare c against c'. If they are equal, return K', the real shared secret. If they differ, return the fallback secret instead.

The input is a ciphertext and the private key; the output is a shared secret that is always the same length and always secret-looking, whether the ciphertext was honest or malformed. That uniformity is the security property. Because a malformed ciphertext yields a pseudorandom fallback rather than an error, an active attacker who submits chosen ciphertexts gains no accept/reject hint from the output, so the decryption-failure oracle that would have leaked the private key is gone. The re-encryption step has no purpose you can see from outside the algorithm, which is exactly why it confuses people who read ML-KEM as a single black box: it is doing security work, not wasted work.

Source: NIST, “Module-Lattice-Based Key-Encapsulation Mechanism Standard,” FIPS 203, August 13, 2024, csrc.nist.gov/pubs/fips/203/final.

What is implicit rejection, and why does ML-KEM use it?

Implicit rejection is the choice to answer a bad ciphertext with a pseudorandom secret instead of an explicit error, so that from the outside a rejected ciphertext is indistinguishable from an accepted one. There are two ways an FO-transformed scheme can handle the moment the comparison fails, and the difference is a real security decision:

Variant	What it returns on a bad ciphertext	The tradeoff
Explicit rejection	An explicit failure symbol	Simpler to reason about, but the failure symbol is itself a hint an attacker can observe and must be handled carefully
Implicit rejection (the ML-KEM choice)	A pseudorandom secret derived from the ciphertext and a stored secret seed z	Success and failure are output-indistinguishable, so the response leaks nothing

ML-KEM uses implicit rejection. On a mismatch it derives the returned value from the ciphertext and the secret seed z that was generated with the key pair, so an attacker sees a normal-looking shared secret whether or not their ciphertext was valid. FIPS 203 also treats the internal accept/reject decision as secret data: the flag produced by comparing c and c' is intermediate information that has to be destroyed before decapsulation finishes and must never be returned in any form. The design goal is that nothing about whether the ciphertext was well-formed ever escapes, because any leak of that single accept/reject fact re-opens the oracle the transform exists to close.

Source: NIST, “Module-Lattice-Based Key-Encapsulation Mechanism Standard,” FIPS 203, August 13, 2024, §6.3, csrc.nist.gov/pubs/fips/203/final.

Where does the FO transform show up in the post-quantum standards?

If a system establishes keys with a post-quantum KEM, it is running an FO transform on every decapsulation, whether or not anyone using the system knows the term. The transform is the reusable pattern underneath the KEMs, not a separate product to procure:

1. ML-KEM (and its predecessor CRYSTALS-Kyber). The internal encryption core, called K-PKE, is IND-CPA-secure and explicitly not approved for standalone use. The ML-KEM KEM wraps it in a variant of the FO transform with implicit rejection. This is the highest-volume instance in current deployment.
2. HQC and Classic McEliece. These code-based KEMs likewise rely on FO-style transforms to reach chosen-ciphertext security from an IND-CPA-secure core, on entirely different underlying math from ML-KEM.
3. Anywhere a KEM decapsulates. TLS handshakes carrying a post-quantum or hybrid key exchange, VPN key establishment, and the hardware modules that perform KEM decapsulation all run the FO re-encryption check on the KEM side of every exchange.

The transform earns its own note precisely because it is invisible in the algorithm names. A team can read “we deployed ML-KEM” and never register that decapsulation now re-encrypts and compares on every message, which is a genuinely new behavior that the classical key exchanges it replaces (ECDH, RSA key transport) never performed.

Source: NIST, “Module-Lattice-Based Key-Encapsulation Mechanism Standard,” FIPS 203, August 13, 2024, §5 (K-PKE) and §6 (ML-KEM), csrc.nist.gov/pubs/fips/203/final.

Does the FO transform itself survive the quantum transition?

Yes, and it is essential to the transition rather than threatened by it. The FO transform is a defensive construction, not a hard problem an attacker breaks, so a quantum computer does not target it the way Shor’s algorithm targets factoring. The quantum algorithms attack the hardness assumption of the encryption core underneath (the lattice math for ML-KEM), and the transform’s job is orthogonal: it provides chosen-ciphertext security given a passively-secure core.

The one subtlety is the security proof. FO security is proven in the random oracle model, which idealizes hash functions, so its post-quantum validity is studied in the quantum random oracle model (the QROM), where an adversary can query those hash functions in superposition. The modern FO variants behind the standardized KEMs, including the one in ML-KEM, carry QROM security analyses, which is the reason the construction was inherited into the post-quantum standards rather than replaced with something new. So the FO transform is the mechanism that makes post-quantum KEMs safe against an active attacker, it survives the transition intact, and it is the same idea whether the encryption core underneath is a classical scheme or a lattice one.

Source: NIST, “Module-Lattice-Based Key-Encapsulation Mechanism Standard,” FIPS 203, August 13, 2024, csrc.nist.gov/pubs/fips/203/final.

Common misconceptions

1. “The FO transform is an algorithm you pick.” It is a generic construction, a wrapper, that turns a passively-secure encryption scheme into an actively-secure KEM. You do not select it separately; it is built into ML-KEM and the other standardized KEMs.
2. “The re-encryption during decapsulation is wasted work.” The re-encrypt-and-compare step is the chosen-ciphertext-security mechanism. Removing it re-opens the decryption-failure oracle that leaks the private key.
3. “ML-KEM is secure because the lattice math is hard, so the transform does not matter.” The lattice hardness gives the core only IND-CPA security. The FO transform is what lifts that to the IND-CCA2 security a real network adversary demands.
4. “A quantum computer breaks the FO transform.” It does not. Quantum algorithms attack the encryption core’s hard problem, not the transform. The transform’s security is analyzed in the QROM and carries into the post-quantum era.
5. “Explicit and implicit rejection are interchangeable.” ML-KEM chose implicit rejection so success and failure look identical from the outside. Returning an explicit error, or leaking the accept/reject decision, gives an attacker the exact fact the transform is built to hide.
6. “The K-PKE core inside ML-KEM is fine to use on its own.” It is not approved for standalone use, because on its own it is only IND-CPA-secure. It is safe only wrapped in the FO transform that makes it ML-KEM.

Questions people ask

What does the Fujisaki-Okamoto transform actually do? It upgrades an encryption scheme from safe-against-an-eavesdropper (IND-CPA) to safe-against-an-active-attacker (IND-CCA2), by making the recipient re-encrypt what it decrypted and check that the result matches the ciphertext that arrived.

Why does ML-KEM re-encrypt during decapsulation? Because that re-encryption and comparison is the FO transform’s security check. It confirms the ciphertext was honestly formed and closes the decryption-failure oracle that would otherwise leak the private key. It has no visible purpose from outside the algorithm, which is why it looks redundant but is not.

What is implicit rejection? It is ML-KEM’s way of handling a bad ciphertext: instead of returning an error, it returns a pseudorandom secret derived from the ciphertext and a stored secret seed, so an attacker cannot tell an accepted ciphertext from a rejected one.

Is the FO transform quantum-safe? Yes. It is a defensive construction, not a hard problem a quantum computer solves. Its security is analyzed in the quantum random oracle model (QROM), and the variants behind the standardized KEMs carry that analysis, which is why they survive into the post-quantum standards.

Do other post-quantum KEMs use it? Yes. HQC and Classic McEliece also use FO-style transforms to reach chosen-ciphertext security from an IND-CPA-secure core, on different underlying math from ML-KEM.

Is this something I have to configure when I deploy ML-KEM? No. The FO transform is part of ML-KEM itself, so a correct ML-KEM implementation already performs it on every decapsulation. It is not a separate procurement item or a setting you turn on.

---

Everything here is the map, given freely. When your team needs its own cryptography sorted into what survives the quantum transition and what has to move, that’s what an alignment briefing is for.

Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.