Paper 2010/513

Key-Dependent Message Security: Generic Amplification and Completeness

Benny Applebaum


Key-dependent message (KDM) secure encryption schemes provide secrecy even when the attacker sees encryptions of messages related to the secret-key $\sk$. Namely, the scheme should remain secure even when messages of the form $f(\sk)$ are encrypted, where $f$ is taken from some function class $F$. A KDM \emph{amplification} procedure takes an encryption scheme which satisfies $\F$-KDM security and boost it into a $G$-KDM secure scheme, where the function class $G$ should be richer than $F$. It was recently shown by Brakerski et al.~(TCC 2011) and Barak et al.~(EUROCRYPT 2010), that a strong form of amplification is possible, provided that the underlying encryption scheme satisfies some special additional properties. In this work, we prove the first \emph{generic} KDM amplification theorem which relies solely on the KDM security of the underlying scheme without making any other assumptions. Specifically, we show that an elementary form of KDM security against functions in which each output bit either copies or flips a single bit of the key (aka \emph{projections}) can be amplified into KDM security with respect to any function family that can be computed in arbitrary fixed polynomial-time. Furthermore, our amplification theorem and its proof are insensitive to the exact setting of KDM security, and they hold in the presence of multiple-keys and in the symmetric-key/public-key and the CPA/CCA cases. As a result, we can amplify the security of all known KDM constructions, including ones that could not be amplified before. Finally, we study the minimal conditions under which full-KDM security (with respect to all functions) can be achieved. We show that under strong notion of KDM security, the existence of cyclic-secure fully-homomorphic encryption is not only sufficient for full-KDM security, as shown by Barak et al., but also necessary. On the other hand, we observe that for standard KDM security, this condition can be relaxed by adopting Gentry's bootstrapping technique (STOC 2009) to the KDM setting.

Note: Fixed some typos.

Available format(s)
Publication info
Published elsewhere. longer version of a paper to appear in Eurocrypt 2011.
Key-dependent messagecyclic-securityrandomized encoding
Contact author(s)
benny applebaum @ gmail com
2011-04-26: last of 6 revisions
2010-10-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benny Applebaum},
      title = {Key-Dependent Message Security: Generic Amplification and Completeness},
      howpublished = {Cryptology ePrint Archive, Paper 2010/513},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.