Paper 2016/243

On the Key Dependent Message Security of the Fujisaki-Okamoto Constructions

Fuyuki Kitagawa, Takahiro Matsuda, Goichiro Hanaoka, and Keisuke Tanaka

Abstract

In PKC 1999, Fujisaki and Okamoto showed how to convert any public key encryption (PKE) scheme secure against chosen plaintext attacks (CPA) to a PKE scheme which is secure against chosen ciphertext attacks (CCA) in the random oracle model. Surprisingly, the resulting CCA secure scheme has almost the same efficiency as the underlying CPA secure scheme. Moreover, in J. Cryptology 2013, they proposed the more efficient conversion by using the hybrid encryption framework. In this work, we clarify whether these two constructions are also secure in the sense of key dependent message security against chosen ciphertext attacks (KDM-CCA security), under exactly the same assumptions on the building blocks as those used by Fujisaki and Okamoto. Specifically, we show two results: Firstly, we show that the construction proposed in PKC 1999 does not satisfy KDM-CCA security generally. Secondly, on the other hand, we show that the construction proposed in J. Cryptology 2013 satisfies KDM-CCA security.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2016
Keywords
public key encryptionkey dependent message securitychosen ciphertext security.
Contact author(s)
kitagaw1 @ is titech ac jp
History
2016-03-05: received
Short URL
https://ia.cr/2016/243
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/243,
      author = {Fuyuki Kitagawa and Takahiro Matsuda and Goichiro Hanaoka and Keisuke Tanaka},
      title = {On the Key Dependent Message Security of the Fujisaki-Okamoto Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2016/243},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/243}},
      url = {https://eprint.iacr.org/2016/243}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.