### Simple and Efficient KDM-CCA Secure Public Key Encryption

Fuyuki Kitagawa, Takahiro Matsuda, and Keisuke Tanaka

##### 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.

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2019
Keywords
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
History
Short URL
https://ia.cr/2019/1012

CC BY

BibTeX

@misc{cryptoeprint:2019/1012,
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{https://eprint.iacr.org/2019/1012}},
url = {https://eprint.iacr.org/2019/1012}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.