Paper 2020/1060
Circular Security Is Complete for KDM Security
Fuyuki Kitagawa and Takahiro Matsuda
Abstract
Circular security is the most elementary form of key-dependent message (KDM) security, which allows us to securely encrypt only a copy of secret key bits. In this work, we show that circular security is complete for KDM security in the sense that an encryption scheme satisfying this security notion can be transformed into one satisfying KDM security with respect to all functions computable by a-priori bounded-size circuits (bounded-KDM security). This result holds in the presence of any number of keys and in any of secret-key/public-key and CPA/CCA settings. Such a completeness result was previously shown by Applebaum (EUROCRYPT 2011) for KDM security with respect to projection functions (projection-KDM security) that allows us to securely encrypt both a copy and a negation of secret key bits. Besides amplifying the strength of KDM security, our transformation in fact can start from an encryption scheme satisfying circular security against CPA attacks and results in one satisfying bounded-KDM security against CCA attacks. This result improves the recent result by Kitagawa and Matsuda (TCC 2019) showing a CPA-to-CCA transformation for KDM secure public-key encryption schemes.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2020
- Keywords
- key-dependent message securitycircular securitychosen ciphertext security
- Contact author(s)
-
fuyuki kitagawa yh @ hco ntt co jp
t-matsuda @ aist go jp - History
- 2020-09-14: revised
- 2020-09-03: received
- See all versions
- Short URL
- https://ia.cr/2020/1060
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1060,
author = {Fuyuki Kitagawa and Takahiro Matsuda},
title = {Circular Security Is Complete for {KDM} Security},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/1060},
year = {2020},
url = {https://eprint.iacr.org/2020/1060}
}
