You are looking at a specific version 20190319:145704 of this paper. See the latest version.

Paper 2019/291

CCA Security and Trapdoor Functions via Key-Dependent-Message Security

Fuyuki Kitagawa and Takahiro Matsuda and Keisuke Tanaka

Abstract

We study the relationship among public-key encryption (PKE) satisfying indistinguishability against chosen plaintext attacks (IND-CPA security), that against chosen ciphertext attacks (IND-CCA security), and trapdoor functions (TDF). Specifically, we aim at finding a unified approach and some additional requirement to realize IND-CCA secure PKE and TDF based on IND-CPA secure PKE, and show the following two main results. As the first main result, we show how to achieve IND-CCA security via a weak form of key-dependent-message (KDM) security. More specifically, we construct an IND-CCA secure PKE scheme 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 (projection-KDM security). Projection functions are very simple functions with respect to which KDM security has been widely studied. Since the existence of projection-KDM secure PKE implies that of the above two building blocks, as a corollary of this result, we see that the existence of IND-CCA secure PKE is implied by that of projection-KDM secure PKE. As the second main result, we extend the above construction of IND-CCA secure PKE into that of TDF by additionally requiring a mild requirement for each building block. Our TDF satisfies adaptive one-wayness. We can instantiate our TDF based on a wide variety of computational assumptions. Especially, we obtain the first TDF (with adaptive one-wayness) based on the sub-exponential hardness of constant-noise learning-parity-with-noise (LPN) problem.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
chosen ciphertext securitytrapdoor functionskey dependent message security
Contact author(s)
kitagaw1 @ is titech ac jp,fuyuki kitagawa @ gmail com,t-matsuda @ aist go jp,keisuke @ is titech ac jp
History
2021-06-04: last of 2 revisions
2019-03-19: received
See all versions
Short URL
https://ia.cr/2019/291
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.