Paper 2019/1012

Simple and Efficient KDM-CCA Secure Public Key Encryption

Fuyuki Kitagawa, Takahiro Matsuda, and Keisuke Tanaka


We propose two efficient public key encryption (PKE) schemes satisfying key dependent message security against chosen ciphertext attacks (KDM-CCA security). The first one is KDM-CCA secure with respect to affine functions. The other one is KDM-CCA secure with respect to polynomial functions. Both of our schemes are based on the KDM-CPA secure PKE schemes proposed by Malkin, Teranishi, and Yung (EUROCRYPT 2011). Although our schemes satisfy KDM-CCA security, their efficiency overheads compared to Malkin et al.'s schemes are very small. Thus, efficiency of our schemes is drastically improved compared to the existing KDM-CCA secure schemes. We achieve our results by extending the construction technique by Kitagawa and Tanaka (ASIACRYPT 2018). Our schemes are obtained via semi-generic constructions using an IND-CCA secure PKE scheme as a building block. We prove the KDM-CCA security of our schemes based on the decisional composite residuosity (DCR) assumption and the IND-CCA security of the building block PKE scheme. Moreover, our security proofs are tight if the IND-CCA security of the building block PKE scheme is tightly reduced to its underlying computational assumption. By instantiating our schemes using existing tightly IND-CCA secure PKE schemes, we obtain the first tightly KDM-CCA secure PKE schemes whose ciphertext consists only of a constant number of group elements.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in Asiacrypt 2019
key dependent message securitychosen ciphertext security
Contact author(s)
fuyuki kitagawa yh @ hco ntt co jp
fuyuki kitagawa @ gmail com
t-matsuda @ aist go jp
2019-09-10: received
Short URL
Creative Commons Attribution


      author = {Fuyuki Kitagawa and Takahiro Matsuda and Keisuke Tanaka},
      title = {Simple and Efficient KDM-CCA Secure Public Key Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1012},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.