Date Added: Oct 2009
The authors construct the first public-key encryption scheme that is proven secure (in the standard model, under standard assumptions) even when the attacker gets access to encryptions of arbitrary efficient functions of the secret key. Specifically, under either the DDH or LWE assumption, for every polynomials L and N they obtain a public-key encryption scheme that resists Key-Dependent Message (KDM) attacks for up to N(k) public keys and functions of circuit size up to L(k), where k denotes the size of the secret key. They call such a scheme bounded KDM secure. Moreover, they show that the scheme suffices for one of the important applications of KDM security: ability to securely instantiate symbolic protocols with axiomatic proofs of security.