A Modular Analysis of the Fujisaki-Okamoto Transformation

Dennis Hofheinz; Kathrin Hövelmanns; Eike Kiltz

Paper 2017/604

A Modular Analysis of the Fujisaki-Okamoto Transformation

Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz

Abstract

The Fujisaki-Okamoto (FO) transformation (CRYPTO 1999 and Journal of Cryptology 2013) turns any weakly secure public-key encryption scheme into a strongly (i.e., IND-CCA) secure one in the random oracle model. Unfortunately, the FO analysis suffers from several drawbacks, such as a non-tight security reduction, and the need for a perfectly correct scheme. While several alternatives to the FO transformation have been proposed, they have stronger requirements, or do not obtain all desired properties. In this work, we provide a fine-grained and modular toolkit of transformations for turning weakly secure into strongly secure public-key encryption schemes. All of our transformations are robust against schemes with correctness errors, and their combination leads to several tradeoffs among tightness of the reduction, efficiency, and the required security level of the used encryption scheme. For instance, one variant of the FO transformation constructs an IND-CCA secure scheme from an IND-CPA secure one with a tight reduction and very small efficiency overhead. Another variant assumes only an OW-CPA secure scheme, but leads to an IND-CCA secure scheme with larger ciphertexts. We note that we also analyze our transformations in the quantum random oracle model, which yields security guarantees in a post-quantum setting.

Note: Added errata.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in TCC 2017
Keywords: public-key encryption Fujisaki-Okamoto transformation tight reductions quantum random oracle model
Contact author(s): eike kiltz @ rub de
History: 2021-11-02: last of 3 revisions; 2017-06-23: received; See all versions
Short URL: https://ia.cr/2017/604
License: CC BY

BibTeX

@misc{cryptoeprint:2017/604,
      author = {Dennis Hofheinz and Kathrin Hövelmanns and Eike Kiltz},
      title = {A Modular Analysis of the Fujisaki-Okamoto Transformation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/604},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/604}},
      url = {https://eprint.iacr.org/2017/604}
}