CPA-to-CCA Transformation for KDM Security

Fuyuki Kitagawa; Takahiro Matsuda

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2019/609

CPA-to-CCA Transformation for KDM Security

Fuyuki Kitagawa and Takahiro Matsuda

Abstract

We show that chosen plaintext attacks (CPA) security is equivalent to chosen ciphertext attacks (CCA) security for key-dependent message (KDM) security. Concretely, we show how to construct a public-key encryption (PKE) scheme that is KDM-CCA secure with respect to all functions computable by circuits of a-priori bounded size, based only on a PKE scheme that is KDM-CPA secure with respect to projection functions. Our construction works for KDM security in the single user setting. Our main result is achieved by combining the following two steps. First, we observe that by combining the results and techniques from the recent works by Lombardi et al. (CRYPTO 2019), and by Kitagawa et al. (CRYPTO 2019), we can construct a reusable designated-verifier non-interactive zero-knowledge (DV-NIZK) argument system based on an IND-CPA secure PKE scheme and a secret-key encryption (SKE) scheme satisfying one-time KDM security with respect to projection functions. This observation leads to the first reusable DV-NIZK argument system under the learning-parity-with-noise (LPN) assumption. Then, as the second and main technical step, we show a generic construction of a KDM-CCA secure PKE scheme using an IND-CPA secure PKE scheme, a reusable DV-NIZK argument system, and an SKE scheme satisfying one-time KDM security with respect to projection functions. Since the classical Naor-Yung paradigm (STOC 1990) with a DV-NIZK argument system does not work for proving KDM security, we propose a new construction methodology to achieve this generic construction. Moreover, we show how to extend our generic construction and achieve KDM-CCA security in the multi-user setting, by additionally requiring the underlying SKE scheme in our generic construction to satisfy a weak form of KDM security against related-key attacks (RKA-KDM security) instead of one-time KDM security. From this extension, we obtain the first KDM-CCA secure PKE schemes in the multi-user setting under the CDH or LPN assumption.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in TCC 2019
Keywords: public-key encryption key-dependent message security chosen ciphertext security
Contact author(s): fuyuki kitagawa yh @ hco ntt co jp
fuyuki kitagawa @ gmail com
t-matsuda @ aist go jp
History: 2019-09-25: last of 2 revisions; 2019-06-02: received; See all versions
Short URL: https://ia.cr/2019/609
License: CC BY

BibTeX

@misc{cryptoeprint:2019/609,
      author = {Fuyuki Kitagawa and Takahiro Matsuda},
      title = {CPA-to-CCA Transformation for KDM Security},
      howpublished = {Cryptology ePrint Archive, Paper 2019/609},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/609}},
      url = {https://eprint.iacr.org/2019/609}
}