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 encryptionFujisaki-Okamoto transformationtight reductionsquantum 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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2017/604}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.