Fujisaki-Okamoto transform

The Fujisaki-Okamoto transform (FO transform) is a generic construction that upgrades a public-key encryption scheme with weak security (one-way or IND-CPA) into a key encapsulation mechanism with strong IND-CCA2 security. It works by making encryption deterministic: the sender derives the encryption randomness by hashing the message, and the receiver, after decrypting, re-encrypts and checks that the ciphertext matches. Any tampered ciphertext fails this re-encryption check, which defeats chosen-ciphertext attacks. The security proof holds in the random oracle model.

#Role in post-quantum KEMs

Modern lattice KEMs are only IND-CPA secure at their core and rely on an FO variant to reach the IND-CCA2 level needed for reusing a public key across many encapsulations. ML-KEM (FIPS 203) applies such a transform with implicit rejection: a decapsulation failure returns a pseudorandom secret instead of an error, which removes an error-path timing signal. The modular analysis by Hofheinz, Hövelmanns, and Kiltz (2017) formalized the FO variants used across the NIST standardization candidates. The re-encryption step handles the hashed message, and any branch that depends on decrypted values has produced side-channel attacks on FO implementations.