Simple and Efficient KDM-CCA Secure Public Key Encryption
Simple and Efficient KDM-CCA Secure Public Key Encryption
复制标题
DOI：
10.1007/978-3-030-34618-8_4
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Fuyuki Kitagawa;Takahiro Matsuda;Keisuke Tanaka
中科院分区：
文献类型：
--
作者：
Fuyuki Kitagawa;Takahiro Matsuda;Keisuke Tanaka
我们提出了两种有效的公钥加密（PKE）方案，满足针对选择密文攻击的依赖密钥消息安全（KDM-CCA安全）。第一个是关于仿射函数的KDM-CCA安全。另一个是关于多项式函数的KDM-CCA安全。我们的两个方案都基于Malkin， Teranishi和Yung （EUROCRYPT 2011）提出的KDM-CPA安全PKE方案。虽然我们的方案满足KDM-CCA安全性，但与Malkin等人的方案相比，它们的效率开销非常小。因此，与现有的KDM-CCA安全方案相比，我们的方案的效率大大提高。我们通过扩展Kitagawa和Tanaka的施工技术（ASIACRYPT 2018）实现了我们的成果。我们的方案是通过使用IND-CCA安全PKE方案作为构建块的半泛型构造获得的。基于决策复合残差（DCR）假设和构造块PKE方案的IND-CCA安全性，证明了我们方案的KDM-CCA安全性。此外，我们的安全性证明是严格的，如果构建块PKE方案的IND-CCA安全性严格简化为其底层计算假设。通过使用现有的紧密IND-CCA安全PKE方案实例化我们的方案，我们获得了第一个密文仅由常数组元素组成的紧密KDM-CCA安全PKE方案。
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 aretightif 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.