Functional Re-encryption and Collusion-Resistant Obfuscation

We introduce a natural cryptographic functionality called functional re-encryption. Informally, this functionality, for a public-key encryption scheme and a function F with n possible outputs, transforms (“re-encrypts”) an encryption of a message m under an “input public key” pk into an encryption of the same message m under one of the n “output public keys”, namely the public key indexed by F(m).

In many settings, one might require that the program implementing the functional re-encryption functionality should reveal nothing about both the input secret key sk as well as the function F. As an example, consider a user Alice who wants her email server to share her incoming mail with one of a set of n recipients according to an access policy specified by her function F, but who wants to keep this access policy private from the server. Furthermore, in this setting, we would ideally obtain an even stronger guarantee: that this information remains hidden even when some of the n recipients may be corrupted.

To formalize these issues, we introduce the notion of collusion-resistant obfuscation and define this notion with respect to average-case secure obfuscation (Hohenberger et al. – TCC 2007). We then provide a construction of a functional re-encryption scheme for any function F with a polynomial-size domain and show that it satisfies this notion of collusion-resistant obfuscation. We note that collusion-resistant security can be viewed as a special case of dependent auxiliary input security (a setting where virtually no positive results are known), and this notion may be of independent interest.

Finally, we show that collusion-resistant obfuscation of functional re-encryption for a function F gives a way to obfuscate F in the sense of Barak et al. (CRYPTO 2001), indicating that this task is impossible for arbitrary (polynomial-time computable) functions F.