Paper 2009/511

Bounded Key-Dependent Message Security

Boaz Barak, Iftach Haitner, Dennis Hofheinz, and Yuval Ishai

Abstract

We 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 we 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. We call such a scheme *bounded KDM secure*. Moreover, we show that our scheme suffices for one of the important applications of KDM security: ability to securely instantiate symbolic protocols with axiomatic proofs of security. We also observe that any fully homomorphic encryption scheme which additionally enjoys circular security and circuit privacy is *fully KDM secure* in the sense that the encryption and decryption algorithms can be independent of the polynomials L and N as above. Thus, the recent fully homomorphic encryption scheme of Gentry (STOC 2009) is fully KDM secure under certain non-standard hardness assumptions. Previous works obtained either full KDM security in the random oracle model Black et al (SAC 2002), or security with respect to a very restricted class of functions (e.g., clique/circular security and affine functions, Boneh et al, CRYPTO 2008, and Applebaum et al, CRYPTO 2009). Our main result is based on a combination of the circular-secure encryption scheme of either Boneh et al or Applebaum et al with Yao's garbled circuit construction. Finally, we extend the impossibility result of Haitner and Holenstein (TCC 2009), showing that it is impossible to prove KDM security against a family of query functions that contains exponentially hard pseudorandom functions, using only *black-box* access to the query function and the adversary attacking the scheme. This proves that the non-black-box usage of the query function in our proof of security makes to the KDM query function is *inherent*.