Cryptology ePrint Archive: Report 2017/604

A Modular Analysis of the Fujisaki-Okamoto Transformation

Dennis Hofheinz and 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.

Category / Keywords: public-key cryptography / public-key encryption, Fujisaki-Okamoto transformation, tight reductions, quantum random oracle model

Date: received 21 Jun 2017, last revised 26 Sep 2017

Contact author: eike kiltz at rub de

Available format(s): PDF | BibTeX Citation

Note: Major revision with many bug fixes and new transformations.

Version: 20170926:122730 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]