On the Instantiability of the Fujisaki–Okamoto Transform for Trapdoor Functions

What it is

This is a theoretical cryptanalysis paper by Carter Luck, Xinyu Mao, and Adam O'Neill, targeting the $G$ hash function step (key-derivation) of the Fujisaki-Okamoto transform — distinct from prior work, which focused on the $H$ (derandomization) step.

How it works

The impossibility result is a counterexample construction: assuming standard LWE plus subexponentially secure indistinguishability obfuscation (iO) and puncturable PRFs, the authors show that for any efficient hash family $G$ with superlogarithmic output length, there exists a one-way, perfectly correct, injective trapdoor function for which the resulting $\UmIR$ KEM fails IND-CCA2. This is an existence proof against all possible instantiations of $G$, not an attack on a specific deployed hash function — ML-KEM's actual $G$ (SHA3-based) is not shown broken.

For the positive result, they restrict scope from KEM to hybrid-encryption formulation of FO, and define a new property, distributional injective extractability (DINJEXT), relative to a "wrapping function." Combined with Bellare-Hoang-Keelveedhi's universal computational extractor security, DINJEXT yields standard-model IND-CCA2 for hybrid encryption. They show DINJEXT is satisfied by a random oracle (for any partially injective wrapping function) and by a quantum random oracle (for the specific FO wrapping function) — but give no standard-model construction satisfying it.

Preconditions / Affected

The uninstantiability result requires the iO/PRF assumptions above; it applies specifically to the $\UmIR$ (message-only implicit-rejection) KEM variant that ML-KEM's design follows. It does not apply to the hybrid-encryption formulation, where the authors' positive conditions instead hold.

Caveats

• The impossibility result is existential/theoretical: it relies on iO, a heavyweight assumption, and constructs an artificial injective TDF — it does not demonstrate a break in ML-KEM itself or identify any flaw in its concrete hash function.
• The positive DINJEXT result is only shown achievable via random oracle or quantum random oracle instantiations; the authors explicitly leave a standard-model construction as an open problem, so no concrete, implementable hash function satisfying DINJEXT currently exists.
• The two results address different formulations (KEM vs. hybrid encryption), so the paper does not resolve instantiability for the KEM formulation ML-KEM actually uses.