Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / key-dependent message security, circular security, chosen ciphertext security

Original Publication (with minor differences): IACR-ASIACRYPT-2020

Date: received 1 Sep 2020, last revised 13 Sep 2020

Contact author: fuyuki kitagawa yh at hco ntt co jp,t-matsuda@aist go jp

Available format(s): PDF | BibTeX Citation

Version: 20200914:054135 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]