International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Simple and Efficient KDM-CCA Secure Public Key Encryption

Authors:
Fuyuki Kitagawa
Takahiro Matsuda
Keisuke Tanaka
Download:
DOI: 10.1007/978-3-030-34618-8_4
Search ePrint
Search Google
Abstract: 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.
BibTeX
@article{asiacrypt-2019-30058,
  title={Simple and Efficient KDM-CCA Secure Public Key Encryption},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  publisher={Springer},
  volume={11923},
  pages={97-127},
  doi={10.1007/978-3-030-34618-8_4},
  author={Fuyuki Kitagawa and Takahiro Matsuda and Keisuke Tanaka},
  year=2019
}