The Fujisaki-Okamoto Wrapper

Everything so far builds an encryption scheme that resists eavesdroppers. The KEM Contract argued that is not enough, because real attackers send ciphertexts of their own and watch what happens. This note closes that gap.

The transform is due to Fujisaki and Okamoto, in the variant refined by Hofheinz, Hövelmanns and Kiltz in 2017 to have a tight proof in the quantum random oracle model. It contains no lattice mathematics at all.

01.The idea

Two changes to the scheme, and together they eliminate the reaction channel.

Make the encryption randomness a hash of the message. In the inner scheme, encryption took independent randomness $r$. In the wrapper, $r$ is derived by hashing $m$. So encryption becomes deterministic given $m$: anybody who knows the message can reproduce the exact ciphertext.

Verify by re-encrypting. On decapsulation, after recovering $m'$, Bob derives $r'$ from it the same way and re-runs the entire encryption. If the ciphertext he produces matches the one he received, it was honestly generated. If not, something was tampered with.

The second step is what removes the attacker's leverage. A modified ciphertext will not re-encrypt to itself, so it is detected regardless of whether its noise happened to stay within the decryption bound.

02.The algorithms

KeyGen. Run the inner key generation and additionally draw a 32-byte rejection seed $z$. Output

$$pk = (\rho, \hat{\mathbf{t}}), \qquad sk = (\hat{\mathbf{s}},\; pk,\; H(pk),\; z),$$

where $H$ is SHA3-256. Storing $pk$ inside $sk$ is what lets decapsulation re-encrypt without being handed the public key separately.

Encaps($pk$).

1. Sample a uniform 32-byte $m$.
2. Derive $(K', r) = G\bigl(m \,\|\, H(pk)\bigr)$, where $G$ is SHA3-512 and its 64 bytes split into two halves.
3. Compute $c = \textsf{Encrypt}(pk, m, r)$ using the inner scheme.
4. Compute $K = \textsf{KDF}\bigl(K' \,\|\, H(c)\bigr)$.

Output $(c, K)$.

Decaps($sk$, $c$).

1. $m' = \textsf{Decrypt}(\hat{\mathbf{s}}, c)$.
2. $(K'', r') = G\bigl(m' \,\|\, H(pk)\bigr)$.
3. $c' = \textsf{Encrypt}(pk, m', r')$, re-encrypting with the derived randomness.
4. If $c' = c$, return $K = \textsf{KDF}\bigl(K'' \,\|\, H(c)\bigr)$. Otherwise return $K = \textsf{KDF}\bigl(z \,\|\, H(c)\bigr)$.

03.Implicit rejection

Step 4 of decapsulation is the part worth dwelling on.

The obvious response to a bad ciphertext is to return an error. That is exactly what must not happen. An error is an observable event, and The KEM Contract described how observable events leak the secret one query at a time.

So instead, a mismatch returns a key derived from the rejection seed $z$. That value is pseudorandom, it is 32 bytes like any other key, and it is deterministic in $z$ and $c$, so the same bad ciphertext always yields the same wrong key.

From the attacker's side, both paths return 32 indistinguishable bytes. There is no error, no branch to time, and no difference to observe. This is implicit rejection, and it is what closes the family of oracle attacks.

The consequence for the honest protocol is that an attacker who tampers with a ciphertext causes the two parties to derive different keys, so the session simply fails to establish later, at the symmetric layer, with no information having leaked about $sk$.

04.What it costs

Decapsulation performs a decryption and then a full encryption. So it is roughly twice the ring arithmetic of the inner scheme, and it is strictly more expensive than encapsulation, which encrypts once.

That is the price of resistance to active attackers, and it is the reason the operation a server performs on every connection is also the most expensive one in the scheme. For hardware acceleration this is the number that matters.

It also forces a discipline on implementations. The comparison $c' = c$ in step 4 must be constant-time. A byte-by-byte comparison that returns early on the first mismatch leaks how many leading bytes matched, which reintroduces exactly the channel the whole construction exists to remove. The same applies to the selection between $K''$ and $z$, which must be a branchless conditional move rather than an if.

05.Where the randomness comes from

Encryption warned that reusing encryption randomness against one public key is a total break. The wrapper is what makes that impossible to get wrong.

Because $r$ is derived deterministically from $m$, and $m$ is freshly sampled uniformly at random each time, reuse can only happen if the same $m$ is drawn twice. With $m$ being 32 uniform bytes, that is a 256-bit collision and will not occur.

So the wrapper turns a requirement that implementations could violate, "use fresh randomness every time", into one they cannot, "sample a fresh 32-byte message". The randomness discipline is enforced by construction rather than by documentation.

06.One hash function underneath

The scheme calls several different primitives: SHAKE128 to expand $\rho$ into the matrix, SHAKE256 as the PRF for centred binomial sampling, SHA3-256 for $H$, SHA3-512 for $G$, and SHAKE256 again for the key derivation.

Every one of those is a different parameterisation of the same underlying permutation, Keccak-f[1600]. That is deliberate. A single hardware block implementing Keccak-f serves every hashing role the scheme has, so an accelerator needs one hash engine rather than five.

Chapter 7 builds that permutation.