The Fujisaki-Okamoto Transform: From Passive to Active Security by Re-Encryption

Abstract

The Fujisaki-Okamoto transform is the single construction that turns the passively secure encryption of the first article into the actively secure key-encapsulation mechanism the second article demanded, and this piece explains exactly how. Its two moves are derandomization — deriving the encryption randomness deterministically from the message by hashing, so a ciphertext becomes a fixed function of what it encrypts — and a re-encryption check at decapsulation that recomputes the ciphertext from the recovered message and rejects any mismatch. Together with implicit rejection, this makes every dishonestly formed ciphertext useless to a decapsulation oracle, closing the chosen-ciphertext attack. The piece sketches the security proof in the random oracle model and its quantum counterpart, shows where the decryption-failure probability enters the security bound, and situates the specific variant the standard uses. The theme: determinism plus a re-encryption equality check converts malleable passive encryption into a non-malleable active mechanism, and the whole security argument lives in the random oracle model.

One construction bridges the gap between the two previous articles: the passively secure encryption scheme on one side, the actively secure key-encapsulation mechanism demanded on the other. The Fujisaki-Okamoto transform closes that gap with a strikingly simple idea. Make encryption deterministic by deriving its random coins from the message itself, so that each message has exactly one valid ciphertext; then, at decapsulation, recompute that ciphertext from the recovered message and accept only if it matches what arrived. Any ciphertext an attacker cooks up that was not produced by the honest deterministic procedure fails the recomputation and is rejected, which strips the decapsulation oracle of all usefulness. This article develops that mechanism and the proof that it works.

Derandomization: coins from the message

The first move removes the randomness from encryption in a controlled way. The passively secure scheme needs random coins to mask the message, and normally those coins are drawn freshly and independently. The transform instead derives them deterministically by hashing the message through a function modeled as a random oracle: the coins are a hash of the message. Encryption thus becomes a deterministic function of the message alone — a given message always encrypts to exactly one ciphertext under a given public key.

Encapsulation then works as follows. Rather than encrypting a chosen message, it picks a fresh random value to play the role of the message, encrypts it with the deterministically derived coins, and derives the shared secret by hashing that value together with the ciphertext through a second random oracle. The ciphertext travels; the shared secret is kept. Because the value was random and the coins came from it, the whole encapsulation is reproducible from that one value, which is the property the decapsulation check will exploit.

The significance of determinism is that it forges a rigid link between message and ciphertext. Under the plain randomized scheme, one message had many valid ciphertexts, and an attacker could maul one into another; under derandomization, each message has a single canonical ciphertext, and any deviation is detectable. That detectability is the lever the next section pulls.

A random value yields the encryption coins by hashing, so its ciphertext is canonical, and the shared secret is a hash of the value and ciphertext.

\[\text{Encaps}(pk): \ m \leftarrow \text{random}; \ c = \mathsf{Enc}(pk, m; G(m)); \ K = H(m, c)\]

\[\text{encryption is now a deterministic function of } m\]

The re-encryption check

Decapsulation is where the transform earns its security. The receiver first decrypts the incoming ciphertext with the secret key to recover a candidate message. It then does the decisive step: it re-encrypts that candidate, deriving the coins by hashing it exactly as encapsulation would, and checks whether the resulting ciphertext equals the one that actually arrived. If they match, the ciphertext was honestly formed and the shared secret is computed as the hash of the candidate and the ciphertext. If they differ in any way, the ciphertext was not honestly formed, and it is rejected.

Rejection is handled by implicit rejection rather than a visible error. The secret key contains a stored random seed, and on a failed check the mechanism returns a pseudorandom key derived from that seed and the ciphertext — a value indistinguishable from a normal shared secret. An attacker submitting a malformed ciphertext therefore cannot tell rejection from acceptance; it simply receives an unpredictable key that reveals nothing. The same path handles the rare decryption failure, where the recovered message is wrong and re-encryption naturally will not match.

The re-encryption equality check is the whole trick. Because a valid ciphertext is the unique deterministic image of its message, the only ciphertexts that survive the check are ones the attacker could have produced itself by running encapsulation honestly — and for those, it already knows the shared secret. The oracle therefore hands the attacker nothing it did not already have, which is precisely what defeats the chosen-ciphertext attack.

Recover the message, re-encrypt it, and compare; a match yields the real key, a mismatch triggers implicit rejection with a pseudorandom key.

\[\text{Decaps}(sk, c): \ m' = \mathsf{Dec}(sk, c); \ \text{if } \mathsf{Enc}(pk, m'; G(m')) = c \ \text{then } K = H(m', c)\]

\[\text{else } K = H(z, c) \ (\text{implicit rejection with stored seed } z)\]

Why this yields non-malleability

The transform delivers non-malleability, the property whose absence broke the plain scheme. Under the plain randomized encryption, an attacker could take a valid ciphertext, perturb it, and obtain a related ciphertext whose decapsulation leaked information. Under the transform, that perturbed ciphertext is no longer the canonical deterministic image of any message the attacker controls, so when the receiver re-encrypts the recovered message the result will not match the perturbed ciphertext, and it is rejected. Mauling is detected and neutralized.

Concretely, the decapsulation oracle becomes worthless to an attacker. For any ciphertext the attacker submits, one of two things happens: either it is a genuine honest encapsulation, in which case the attacker knew the underlying random value and hence the shared secret already, or it is anything else, in which case implicit rejection returns an unpredictable key that carries no information about the secret key. There is no third option that leaks — the re-encryption check partitions all ciphertexts into these two harmless cases.

This is the exact remedy the second article's definition called for. The chosen-ciphertext attack drew its power from an oracle that behaved informatively on attacker-crafted ciphertexts; the transform makes the oracle behave uninformatively on precisely those, while remaining correct on honest ones. Passive encryption plus a deterministic re-encryption check equals an actively secure mechanism.

The proof in the random oracle model

The security guarantee is a theorem, proved by reduction in the random oracle model. The claim is that any efficient adversary breaking the mechanism's chosen-ciphertext security can be turned into an efficient adversary breaking the passive security of the underlying encryption. The reduction works because the hash functions are modeled as random oracles the reduction controls: it can watch the adversary's hash queries and, from them, answer decapsulation queries consistently without the secret key, simulating the oracle the chosen-ciphertext adversary expects. The attacker's own queries reveal the values it would need, letting the reduction stay consistent.

For post-quantum security this argument must hold against quantum adversaries, which can query the hash functions in superposition. The modular analysis of the transform by Hofheinz, Hovelmanns and Kiltz recasts it as a sequence of smaller steps, each provable in the quantum random oracle model, at the cost of a quantified security loss relative to the classical proof. The standardized mechanism is designed so that its parameters absorb this loss and the quantum reduction still yields the target security level. That the proof survives quantum queries is an essential, non-obvious part of the mechanism's post-quantum assurance.

The reduction also makes explicit where correctness enters. If the underlying encryption can fail to decrypt correctly, the proof must account for the possibility that an honest ciphertext decapsulates wrongly, and this appears in the security bound as a term proportional to the failure probability and the number of adversary queries. The bound is only meaningful when that term is negligible, which ties the whole argument to keeping the decryption-failure probability astronomically small — the subject of the next article.

An attacker breaking the KEM's active security is converted, by simulating the random oracles, into one breaking the underlying passive encryption.

Where failures enter, and the standard's variant

The appearance of the failure probability in the security bound is the reason the previous article's small decoding-margin tail cannot be ignored. The proof charges an adversary for its ability to provoke and observe decryption failures, and the mechanism is only as secure as that term is small. This is not a loose end but a precise design requirement: the parameters must drive the failure probability far below the target security level, and an attacker who could inflate it would erode the proof — exactly the threat the next article examines under failure-boosting attacks.

The standardized mechanism uses a specific, carefully chosen instantiation of the transform with implicit rejection, deriving the shared secret and the encryption coins through the standard's hash functions and storing the rejection seed inside the secret key. The details — which values are hashed, in what order, with which functions — are fixed by the specification precisely because small deviations can void the proof or open side channels. An implementer must follow the specified construction exactly rather than approximating it.

For autonomous AI systems the transform is invisible in normal use but critical in principle. When an agent or a model endpoint decapsulates, it is the re-encryption check and implicit rejection that protect it from an adversary flooding it with crafted ciphertexts; a shortcut that skips the re-encryption comparison, surfaces a distinct error on rejection, or reuses randomness would silently reintroduce the chosen-ciphertext attack. The correct posture, once again, is to use a conformant implementation of the standardized mechanism and treat its internal steps as inviolable, because the entire jump from passive to active security lives in those few deterministic lines.

⚠️

The re-encryption check is load-bearing. Skipping the re-encryption comparison, returning a distinct error on rejection, or reusing encryption randomness each voids the FO guarantee and reopens the chosen-ciphertext attack. Follow the standardized construction exactly.

Key takeaways

The Fujisaki-Okamoto transform converts the passively secure LWE encryption into an actively secure KEM via two moves: derandomization and a re-encryption check.
Derandomization derives the encryption coins by hashing the message, so each message has exactly one canonical ciphertext — encryption becomes deterministic.
At decapsulation the recovered message is re-encrypted and compared to the received ciphertext; a match yields the real shared secret, a mismatch triggers implicit rejection with a pseudorandom key.
This gives non-malleability: the decapsulation oracle returns a useful key only for ciphertexts the attacker could have formed itself, and an unpredictable key otherwise — defeating the chosen-ciphertext attack.
Security is proved by reduction in the random oracle model, and the quantum random oracle model via the modular FO analysis, with a quantified loss the parameters absorb.
The decryption-failure probability enters the security bound, so it must be kept negligible; the standard fixes a specific FO-with-implicit-rejection variant that implementers must follow exactly.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

✅Verifying an FO instantiationchecklist

Confirm the transform is applied correctly.

Are the encryption coins derived deterministically from the message by hashing?
Does decapsulation re-encrypt the recovered message and compare to the received ciphertext?
Is a stored seed used for implicit rejection on mismatch, with no distinct error path?
Are the hash functions and hashing order exactly as the standard specifies?
Is the decryption-failure probability documented as negligible?

🚀Reason about the security jumpquickstart

Trace passive-to-active security through the transform.

Confirm the underlying scheme is IND-CPA.
Apply derandomization so ciphertexts are canonical.
Add the re-encryption check with implicit rejection.
Rely on the standardized parameters to absorb the quantum reduction loss.

🔒FO-integrity policypolicy

A stub fixing the transform's inviolable steps.

fo_transform:
  derandomization: coins_from_message_hash
  decaps_reencrypt_check: required
  rejection: implicit_pseudorandom_key
  hash_order: exactly_as_standard
proof:
  model: quantum_random_oracle
  failure_term: kept_negligible
implementation:
  skip_reencrypt: forbidden
  distinct_error_on_reject: forbidden
  reuse_randomness: forbidden

Illustrative documentation template, not a product config.

Glossary

Fujisaki-Okamoto transform: A construction converting IND-CPA encryption into an IND-CCA KEM by derandomizing encryption and adding a re-encryption check with implicit rejection.
Derandomization: Deriving the encryption randomness deterministically by hashing the message, so each message has a single canonical ciphertext.
Re-encryption check: At decapsulation, recomputing the ciphertext from the recovered message and accepting only if it equals the received ciphertext.
Implicit rejection: Returning a pseudorandom key derived from a stored secret seed on a failed check, so rejection is indistinguishable from success.
Random oracle model: A proof framework treating hash functions as random functions the reduction controls; its quantum version allows superposition queries.
Failure term in the bound: A component of the security bound proportional to the decryption-failure probability and query count, requiring that probability to be negligible.