Key-Dependent Message Security: Generic Amplification and Completeness
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 \(\mathcal{F}\). A KDM amplification procedure takes an encryption scheme which satisfies \(\mathcal{F}\)-KDM security, and boosts it into a \(\mathcal{G}\)-KDM secure scheme, where the function class \(\mathcal{G}\) should be richer than \(\mathcal{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.
key-dependent message cyclic-security randomized encoding garbled circuits