Paper 2023/1058

Universal Amplification of KDM Security: From 1-Key Circular to Multi-Key KDM

Brent Waters, The University of Texas at Austin, NTT Research
Daniel Wichs, Northeastern University, NTT Research

An encryption scheme is Key Dependent Message (KDM) secure if it is safe to encrypt messages that can arbitrarily depend on the secret keys themselves. In this work, we show how to upgrade essentially the weakest form of KDM security into the strongest one. In particular, we assume the existence of a symmetric-key bit-encryption that is circular-secure in the $1$-key setting, meaning that it maintains security even if one can encrypt individual bits of a single secret key under itself. We also rely on a standard CPA-secure public-key encryption. We construct a public-key encryption scheme that is KDM secure for general functions (of a-priori bounded circuit size) in the multi-key setting, meaning that it maintains security even if one can encrypt arbitrary functions of arbitrarily many secret keys under each of the public keys. As a special case, the latter guarantees security in the presence of arbitrary length key cycles. Prior work already showed how to amplify $n$-key circular to $n$-key KDM security for general functions. Therefore, the main novelty of our work is to upgrade from $1$-key to $n$-key security for arbitrary $n$. As an independently interesting feature of our result, our construction does not need to know the actual specification of the underlying 1-key circular secure scheme, and we only rely on the existence of some such scheme in the proof of security. In particular, we present a universal construction of a multi-key KDM-secure encryption that is secure as long as some 1-key circular-secure scheme exists. While this feature is similar in spirit to Levin's universal construction of one-way functions, the way we achieve it is quite different technically, and does not come with the same ``galactic inefficiency''.

Available format(s)
Publication info
Published by the IACR in CRYPTO 2023
KDM SecurityCircular Security
Contact author(s)
bwaters @ cs utexas edu
wichs @ ccs neu edu
2023-07-11: approved
2023-07-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Brent Waters and Daniel Wichs},
      title = {Universal Amplification of KDM Security: From 1-Key Circular to Multi-Key KDM},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1058},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.