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

.