Key-Dependent Message Security: Generic Amplification and Completenes
AbatractKey-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 ampliﬁcation procedure takes an encryption scheme which satisﬁes 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 ampliﬁcation is possible, provided that the underlying encryption scheme satisﬁes some special additional properties.
In this work, we prove the ﬁrst generic KDM ampliﬁcation theorem which relies solely on the KDM security of the underlying scheme without making any other assumptions. Speciﬁcally, we show that an elementary form of KDM security against functions in which each output bit either copies or ﬂips a single bit of the key (aka projections ) can be ampliﬁed into KDM security with respect to any function family that can be computed in arbitrary ﬁxed polynomial-time. Furthermore, our ampliﬁcation 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 ampliﬁed 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 fullyhomomorphic encryption is not only suﬃcient 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.