Cryptology ePrint Archive: Report 2019/1012

Simple and Efficient KDM-CCA Secure Public Key Encryption

Fuyuki Kitagawa and 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.

Category / Keywords: public-key cryptography / key dependent message security, chosen ciphertext security

Original Publication (with minor differences): IACR-ASIACRYPT-2019

Date: received 9 Sep 2019, last revised 10 Sep 2019

Contact author: fuyuki kitagawa yh at hco ntt co jp, fuyuki kitagawa at gmail com, t-matsuda at aist go jp

Available format(s): PDF | BibTeX Citation

Version: 20190910:130106 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]