Fujisaki–Okamoto transformation

Short description: Method for strengthening public-key encryption against chosen-ciphertext attacks

Fujisaki–Okamoto transformation

General
Designers	Eiichiro Fujisaki, Tatsuaki Okamoto (ja)
First published	1999
Related to	Optimal asymmetric encryption padding

In cryptography, the Fujisaki–Okamoto transformation (FO transformation or FO transform) is a generic method for strengthening a public-key encryption scheme against adaptive chosen-ciphertext attacks. Security analyses of FO model the hash functions added by the transformation as random oracles. Eiichiro Fujisaki and Tatsuaki Okamoto (ja) of NTT Laboratories introduced the transformation in 1999. Their construction is a hybrid cryptosystem: the public-key component need only be one-way, while the symmetric component requires only a weak, one-time form of indistinguishability.

FO has found widespread use in post-quantum cryptography key encapsulation mechanisms (KEMs). Alexander W. Dent recast the transformation in KEM form in 2003. In 2017, Hofheinz, Hövelmanns and Kiltz reorganized its security analysis into modular steps. Nearly every KEM submitted to the NIST Post-Quantum Cryptography Standardization process incorporated some form of FO. ML-KEM is derived from CRYSTALS-Kyber and was standardized by the United States National Institute of Standards and Technology in 2024. It uses an FO variant to convert its component encryption scheme, K-PKE, into a KEM. The standard attributes ML-KEM's IND-CCA2 security to this conversion.

Concept

The Fujisaki–Okamoto transformation strengthens a public-key encryption scheme against chosen-ciphertext attacks. An IND-CPA-secure scheme is secure against an attacker who is allowed to choose messages and obtain their encryptions, but is not allowed to ask for arbitrary ciphertexts to be decrypted. IND-CCA2 security considers a stronger attacker, who is also allowed to submit ciphertexts of their choice for decryption, except for the particular challenge ciphertext they are trying to learn about. In simplified terms, the Fujisaki–Okamoto transform helps achieve this stronger security by having the recipient decrypt a ciphertext, derive the randomness that should have been used to create it, re-encrypt the recovered message, and check that the result matches the received ciphertext. If the check fails, an explicit-rejection variant returns a failure code. An implicit-rejection variant instead returns a pseudorandom "fallback" key. The decapsulation oracle therefore still answers the query, but does not directly reveal whether the ciphertext passed the validity check.

History

Fujisaki and Okamoto described two constructions in two papers published in 1999. They presented the first, "How to Enhance the Security of Public-Key Encryption at Minimum Cost", at PKC '99. It assumed that the underlying public-key scheme was already secure against chosen-plaintext attacks (IND-CPA). Later that year, they presented "Secure Integration of Asymmetric and Symmetric Encryption Schemes" at CRYPTO '99. The CRYPTO construction required only a one-way public-key scheme and used symmetric encryption to carry the message. This hybrid construction became known as the Fujisaki–Okamoto transformation. A revised version of the CRYPTO paper appeared in the Journal of Cryptology in 2013.

At the time, an earlier generic tool for strengthening public-key encryption was Optimal asymmetric encryption padding (OAEP). Bellare and Rogaway had designed OAEP for one-way trapdoor permutations such as RSA. Probabilistic schemes (including ElGamal, Blum–Goldwasser and Okamoto–Uchiyama) therefore fell outside its scope. Fujisaki and Okamoto stated that they knew of no previous generic, efficient conversion of an arbitrary public-key scheme to IND-CCA security. Their CRYPTO paper gives instantiations for ElGamal and Okamoto–Uchiyama. It points to PSEC and EPOC, two encryption schemes that the authors and their colleagues had submitted to IEEE P1363a—for further details.

Two later transformations require less machinery than FO: REACT, by Okamoto and Pointcheval, and GEM, by Coron and coauthors. Both rely on the stronger assumption of one-wayness under plaintext-checking attacks. In 2005, Galindo, Martín, Morillo and Villar identified ambiguities in the CRYPTO '99 security proof and proposed a repair. The proposed repair, however, applies only to a narrower class of public-key primitives.

FO attracted renewed attention during the NIST post-quantum cryptography project. Lattice- and code-based encryption basic schemes usually have only IND-CPA security, leaving KEM designers in need of a generic route to chosen-ciphertext security. Dent's 2003 paper "A Designer's Guide to KEMs" had already recast FO as a key-encapsulation construction. Dent's construction became a standard method for building secure KEMs. In 2017, Hofheinz, Hövelmanns and Kiltz decomposed the transformation into separate steps. They derived a tight reduction from IND-CPA security and proved variants that allow a small probability of decryption failure. Decryption failures and reduction tightness had received little attention in 1999, but both became important in the analysis of lattice-based candidates.

Construction

Original transformation

Let $E_{pk}^{\text{asym}}(x;r)$ denote asymmetric encryption of $x$ under public key $pk$ with random coins $r$, and let $E_a^{\text{sym}}(m)$ denote symmetric encryption of $m$ under key $a$. In a "hybrid" FO scheme with two hash functions, $G$ and $H$, a message $m$ is encrypted as

$E_{pk}^{\text{hy}}(m;\sigma )=E_{pk}^{\text{asym}}(\sigma ;H(\sigma ,m))\Vert E_{G(\sigma )}^{\text{sym}}(m),$

where $\sigma$ is a random string. The asymmetric component encrypts only the seed; its coins are derived from both the seed and the message. The symmetric component encrypts the message under the key $G(\sigma )$.

To decrypt, one recovers a candidate seed $\hat{\sigma }$ from the first component, computes $G(\hat{\sigma })$, and decrypts the second component to obtain a candidate message $\hat{m}$. The ciphertext is accepted only if the re-encryption $E_{pk}^{\text{asym}}(\hat{\sigma };H(\hat{\sigma },\hat{m}))$ exactly reproduces the first component; otherwise, the entire ciphertext is rejected. In the security proof, this check serves as base of a knowledge extractor. By examining the adversary's hash queries, the proof recovers the plaintext of any valid ciphertext that the adversary produces.

The security theorem imposes three conditions. The asymmetric scheme must be one-way and γ-uniform, meaning that no single ciphertext value occurs with probability greater than $\gamma$ over the choice of encryption coins. The symmetric scheme must also satisfy a one-time indistinguishability notion that the authors call find-guess security. Under these conditions, the hybrid scheme is IND-CCA secure in the random oracle model, with concrete bounds relating the adversary's advantage to the corresponding advantages against the two components. The original paper's γ-uniformity probability is changed to γ-spreadness (in terms of bits) in later work.

With a one-time pad as the symmetric scheme, the ciphertext becomes $E_{pk}^{\text{asym}}(\sigma ;H(\sigma ,m))\Vert (G(\sigma )\oplus m)$, and no separate security condition on the symmetric component is required. Deterministic schemes pose a problem: textbook RSA with no randomness has γ = 1, so the conversion cannot be applied to it directly. Appending fresh randomness to the ciphertext makes the conversion applicable. With this modification, the use of a one-way trapdoor permutation and a one-time pad gives the encryption scheme published by Bellare and Rogaway in 1993.

Key encapsulation variants

Dent's KEM version differs because a KEM does not encrypt a message directly. Encapsulation samples a random $m$, deterministically computes the ciphertext $c=\mathsf{E}\mathsf{n}\mathsf{c}(pk,m;G(m))$, and outputs $K=H(m)$ as the session key. Some variants instead derive the session key as $K=H(c,m)$.

The 2017 analysis decomposes the transformation into two steps. The first, called T, derandomizes the encryption scheme: $G(m)$ replaces the random coins, and decryption gains the re-encryption check. The second is a family of transformations called U, which hashes the message (designated by a subscript $m$ below, in some variants together with the ciphertext, designated by no subscript) to derive the session key. The U transformations support either explicit or implicit rejection. Explicit rejection returns a failure symbol $\perp$ for an invalid ciphertext. Under implicit rejection ($\perp ̸$), decapsulation instead returns a pseudorandom key derived from the ciphertext and a secret seed stored in the private key. Combining the two rejection modes with the two key-derivation methods gives four variants: ${\mathsf{F}\mathsf{O}}^{\perp }$, ${\mathsf{F}\mathsf{O}}^{\perp ̸}$, ${\mathsf{F}\mathsf{O}}_m^{\perp }$, and ${\mathsf{F}\mathsf{O}}_m^{\perp ̸}$. Only the explicit-rejection variants require γ-spreadness, and ${\mathsf{F}\mathsf{O}}_m^{\perp }$ is essentially Dent's KEM version of the original transformation.

Security

The security reduction in the 1999 analysis is loose. It bounds the adversary's advantage against the hybrid scheme by approximately the product of the random-oracle query count and the advantage against the one-wayness of the asymmetric scheme. The scheme's security parameters must therefore be increased to offset this query-count loss. The analysis also assumes that decryption never fails, whereas many lattice-based schemes have a small probability of decryption failure. The 2017 analysis addresses both the reduction loss and decryption failures. The transformations tolerate a decryption error δ, provided that δ is at most $2^{-\kappa }$ for κ bits of security. When the starting assumption is IND-CPA security rather than one-wayness, the reduction is tight in the classical random oracle model.

A quantum attacker can evaluate hash functions on superpositions of inputs. Post-quantum proofs therefore use the quantum-accessible random oracle model, or QROM. Targhi and Unruh gave the QROM proof in 2016, using a modified transformation that adds another hash value to the ciphertext. The 2017 analysis covers a KEM variant with the same additional hash, but gives a very loose reduction. Subsequent work obtained substantially tighter QROM bounds, although these reductions require the implicit-rejection variants. As was shown in the previuous work, the security of the common variants is equivalent to, or implied by, that of ${\mathsf{F}\mathsf{O}}_m^{\perp }$. The available QROM bound for the explicit-rejection textbook variant is substantially weaker.

Accounting for decryption failures complicates these proofs. Conventional reductions give the adversary the private key. They then bound the probability that the adversary finds a plaintext causing a decryption failure. This produces a Grover-type search bound in terms of the worst-case failure probability. Hövelmanns, Hülsing and Majenz argued in 2022 that giving the adversary the private key is unnatural. They instead based their reduction on failure-finding games in which the adversary never receives the key. The failure-finding-game reduction gives tighter bounds and also covers the explicit-rejection variant.

Applications

Nearly all of the KEM candidates in the NIST post-quantum project used the transformation. FIPS 203, published in August 2024, specifies ML-KEM on the basis of the third-round CRYSTALS-Kyber submission. K-PKE is an encryption scheme based on the module learning with errors problem. The FO transform converts it into a KEM, and the standard attributes ML-KEM's IND-CCA2 security to this conversion. ML-KEM uses implicit rejection. During decapsulation, it decrypts the ciphertext, re-encrypts with the rederived coins, and compares the re-encrypted ciphertext with the received one. If the ciphertexts differ, decapsulation returns a hash of the received ciphertext and a secret 32-byte value held in the decapsulation key, rather than an error. This transform variant differs from the one used in third-round Kyber because the hash of the ciphertext no longer enters the derivation of the shared secret. The decapsulation failure rates for the three parameter sets are between $2^{-174.8}$ and $2^{-138.8}$.

The re-encryption check also has drawbacks. Every decapsulation must run the encryption algorithm a second time (providing it with the decrypted secret), and implementations of the check can introduce side-channel weaknesses. These drawbacks have motivated research into alternatives to re-encryption.

See also

• Optimal asymmetric encryption padding
• Hybrid cryptosystem
• Key encapsulation mechanism

Sources

• Boneh, Dan; Shoup, Victor (2023). A Graduate Course in Applied Cryptography (Version 0.6). http://toc.cryptobook.us/. 
• Fujisaki, Eiichiro; Okamoto, Tatsuaki (1999a). "Secure integration of asymmetric and symmetric encryption schemes". in Wiener, Michael. Advances in Cryptology – CRYPTO '99. Lecture Notes in Computer Science. 1666. Berlin: Springer. pp. 537–554. doi:10.1007/3-540-48405-1_34. ISBN 978-3-540-66347-8. 
• Fujisaki, Eiichiro; Okamoto, Tatsuaki (1999b). "How to enhance the security of public-key encryption at minimum cost". in Imai, Hideki; Zheng, Yuliang. Public Key Cryptography (PKC '99). Lecture Notes in Computer Science. 1560. Berlin: Springer. pp. 53–68. doi:10.1007/3-540-49162-7_5. 
• Fujisaki, Eiichiro; Okamoto, Tatsuaki (2013). "Secure integration of asymmetric and symmetric encryption schemes". Journal of Cryptology 26 (1): 80–101. doi:10.1007/s00145-011-9114-1. 
• Galindo, David; Martín, Sebastià; Morillo, Paz; Villar, Jorge L. (2005). "Fujisaki–Okamoto hybrid encryption revisited". International Journal of Information Security 4 (4): 228–241. doi:10.1007/s10207-004-0042-z. 
• Hofheinz, Dennis; Hövelmanns, Kathrin; Kiltz, Eike (2017). "A modular analysis of the Fujisaki–Okamoto transformation". in Kalai, Yael; Reyzin, Leonid. Theory of Cryptography (TCC 2017), Part I. Lecture Notes in Computer Science. 10677. Cham: Springer. pp. 341–371. doi:10.1007/978-3-319-70500-2_12. 
• Hövelmanns, Kathrin; Hülsing, Andreas; Majenz, Christian (2022). "Failing gracefully: decryption failures and the Fujisaki–Okamoto transform". in Agrawal, Shweta; Lin, Dongdai. Advances in Cryptology – ASIACRYPT 2022. Lecture Notes in Computer Science. 13794. Cham: Springer. pp. 414–443. 
• Hövelmanns, Kathrin; Hülsing, Andreas; Majenz, Christian; Sisinni, Fabrizio (2025). "(Un)breakable curses – re-encryption in the Fujisaki-Okamoto transform". https://eprint.iacr.org/2025/299. 
• Longa, Patrick; Bos, Joppe W.; Ehlen, Stephan; Stebila, Douglas (22 June 2026). FrodoKEM: Key Encapsulation from Learning with Errors (Internet-Draft). Internet Engineering Task Force. https://datatracker.ietf.org/doc/draft-longa-cfrg-frodokem/. Retrieved 28 August 2026. 
• National Institute of Standards and Technology (2024). Module-Lattice-Based Key-Encapsulation Mechanism Standard (Report). Gaithersburg, MD: U.S. Department of Commerce. doi:10.6028/NIST.FIPS.203. FIPS 203. https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.203.pdf. Retrieved 27 August 2026. 
• NIST (5 August 2026). "Security (Evaluation Criteria)". Post-Quantum Cryptography. National Institute of Standards and Technology. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization/Evaluation-Criteria/Security-(Evaluation-Criteria).