Paper 2020/1060

Circular Security Is Complete for KDM Security

Fuyuki Kitagawa and Takahiro Matsuda


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.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2020
key-dependent message securitycircular securitychosen ciphertext security
Contact author(s)
fuyuki kitagawa yh @ hco ntt co jp
t-matsuda @ aist go jp
2020-09-14: revised
2020-09-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fuyuki Kitagawa and Takahiro Matsuda},
      title = {Circular Security Is Complete for KDM Security},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1060},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.