CPA-to-CCA Transformation for KDM Security
CPA-to-CCA Transformation for KDM Security
复制标题
DOI：
10.1007/978-3-030-36033-7_5
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Fuyuki Kitagawa;Takahiro Matsuda
中科院分区：
文献类型：
--
作者：
Fuyuki Kitagawa;Takahiro Matsuda
我们展示了选择明文攻击（CPA）安全等同于选择密文攻击（CCA）安全的密钥依赖消息（KDM）安全。具体地说，我们展示了如何构建一个公钥加密（PKE）方案，该方案对于所有由先验有界大小的电路可计算的函数都是KDM-CCA安全的，仅基于一个PKE方案对于投影函数是KDM-CPA安全的。我们的结构适用于单用户设置中的KDM安全性。我们的主要结果是通过结合以下两个步骤实现的。首先，我们观察到，通过结合Lombardi等人（CRYPTO 2019）和Kitagawa等人（CRYPTO 2019）最近工作的结果和技术，我们可以构建一个可重用的指定验证者非交互式零知识（DV-NIZK）参数系统，该系统基于IND-CPA安全PKE方案和满足一次性KDM安全性的秘钥加密（SKE）方案。这一观察结果导致了在噪声奇偶性（LPN）假设下的第一个可重用的DV-NIZK参数系统。然后，作为第二步和主要的技术步骤，我们展示了使用IND-CPA安全PKE方案，可重用的DV-NIZK参数系统和满足关于投影函数的一次性KDM安全性的SKE方案的KDM- cca安全PKE方案的一般构造。由于带有DV-NIZK论证系统的经典Naor-Yung范式（STOC 1990）不能用于证明KDM的安全性，我们提出了一种新的构造方法来实现这种通用构造。此外，我们还展示了如何扩展我们的通用构造并在多用户设置中实现KDM- cca安全性，方法是在我们的通用构造中额外要求底层SKE方案来满足针对相关密钥攻击（RKA-KDM安全性）的弱形式的KDM安全性，而不是一次性的KDM安全性。在此基础上，我们得到了CDH或LPN假设下多用户环境下的第一个KDM-CCA安全PKE方案。
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.