A Note on Failing Gracefully: Completing the Picture for Explicitly Rejecting Fujisaki-Okamoto Transforms Using Worst-Case Correctness

The Fujisaki-Okamoto (FO) transformation is used in most proposals for post-quantum secure key encapsulation mechanisms (KEMs) like, e.g., Kyber [BDK+18]. The security analysis of FO in the presence of quantum attackers has made huge progress over the last years, however, it had a particular quirk: unless incurring (even more) unreasonable security bounds, security was only shown for FO variants that react to invalid ciphertexts by returning a pseudorandom value (‘implicit’ reject) rather than ‘explicitly’ reporting decryption failure by returning a failure symbol. This part of the design has been subject to some debate, with the main question being whether explicitly rejecting variants could indeed be less secure than their implicitly rejecting counterparts.A recent work by Hövelmanns, Hülsing and Majenz [HHM22] gave a proof which, in contrast to previous ones, was agnostic to the choice of how invalid ciphertexts are being dealt with, thus indicating that the two variants might be similarly secure. It involved, however, a new correctness notion for the encryption scheme that is used to encapsulate the keys. While this new notion in principle might allow to improve the overall security bound, it places a new analysis burden on designers: when looking at a concrete KEM at hand, it becomes necessary to analyze this new notion for the encryption scheme on which the KEM is based.This note offers a trade-off between [HHM22] and its predecessors: it offers a bound for both rejection variants, but uses the established correctness notion that was used in all previous work.