Paper 2022/365

Failing gracefully: Decryption failures and the Fujisaki-Okamoto transform

Kathrin Hövelmanns, Andreas Hülsing, and Christian Majenz


In known security reductions for the Fujisaki-Okamoto transformation, decryption failures are handled via a reduction solving the rather unnatural task of finding failing plaintexts \emph{given the private key}, resulting in a Grover search bound. Moreover, they require an implicit rejection mechanism for invalid ciphertexts to achieve a reasonable security bound in the QROM. We present a reduction that has neither of these deficiencies: We introduce two security games related to finding decryption failures, one capturing the \emph{computationally hard} task of \emph{using the public key} to find a decryption failure, and one capturing the \emph{statistically hard} task of searching the random oracle for \emph{key-independent} failures like, e.g., large randomness. As a result, our security bounds in the QROM are tighter than previous ones with respect to the generic random oracle search attacks: The attacker can only partially compute the search predicate, namely for said key-independent failures. In addition, our entire reduction works for the explicit-reject variant of the transformation and improves significantly over all of its known reductions. Besides being the more natural variant of the transformation, security of the explicit reject mechanism is also relevant for side channel attack resilience of the implicit-rejection variant. Along the way, we prove several technical results characterizing preimage extraction and certain search tasks in the QROM that might be of independent interest.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Public-key encryptionpost-quantum securityQROMFujisaki-Okamoto transformationdecryption failuresNIST
Contact author(s)
authors-fo-failure @ huelsing net
2022-03-22: received
Short URL
Creative Commons Attribution


      author = {Kathrin Hövelmanns and Andreas Hülsing and Christian Majenz},
      title = {Failing gracefully: Decryption failures and the Fujisaki-Okamoto transform},
      howpublished = {Cryptology ePrint Archive, Paper 2022/365},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.