A note on Failing gracefully: Completing the picture for explicitly rejecting Fujisaki-Okamoto transforms using worst-case correctness

Kathrin Hövelmanns; Christian Majenz

Paper 2023/1811

A note on Failing gracefully: Completing the picture for explicitly rejecting Fujisaki-Okamoto transforms using worst-case correctness

Kathrin Hövelmanns

, Eindhoven University of Technology

Christian Majenz

, Technical University of Denmark

Abstract

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. Recently, [HHM22] made a particular improvement by giving a security proof that is agnostic towards how invalid ciphertexts are being treated: in contrast to previous proofs, it works regardless whether invalid ciphertexts are rejected by reporting decryption failure explicitly or implicitly (by returning pseudorandom values). The proof in [HHM22] involves a new correctness notion for the encryption scheme that is used to encapsulate the keys. This allows in principle for a smaller additive security related to decryption failures, but requires to analyze this new notion for the encryption scheme on which a concrete KEM at hand is based. This note offers a trade-off between [HHM22] and its predecessors: it offers a bound for both rejection variants, being mostly based on [HHM22], but uses a more established correctness notion.

Note: Added publication information and reordered sections for better reading flow.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. PQCrypto 2024
Keywords: Post-quantum QROM Fujisaki-Okamoto decryption failures NIST
Contact author(s): kathrin @ hoevelmanns net
chmaj @ dtu dk
History: 2024-06-10: revised; 2023-11-23: received; See all versions
Short URL: https://ia.cr/2023/1811
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1811,
      author = {Kathrin Hövelmanns and Christian Majenz},
      title = {A note on Failing gracefully: Completing the picture for explicitly rejecting Fujisaki-Okamoto transforms using worst-case correctness},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1811},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1811}
}