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.
Category / Keywords: foundations / Key-dependent message, cyclic-security, randomized encoding Publication Info: longer version of a paper to appear in Eurocrypt 2011. Date: received 7 Oct 2010, last revised 26 Apr 2011 Contact author: benny applebaum at gmail com Available formats: PDF | BibTeX Citation Note: Fixed some typos. Version: 20110426:163236 (All versions of this report) Discussion forum: Show discussion | Start new discussion