Paper 2011/337

Functional Re-encryption and Collusion-Resistant Obfuscation

Nishanth Chandran, Melissa Chase, and Vinod Vaikuntanathan

Abstract

We introduce a natural cryptographic functionality called \emph{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 \emph{collusion-resistant obfuscation} and define this notion with respect to average-case secure obfuscation (Hohenberger \emph{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 {\em et al.} (CRYPTO 2001), indicating that this task is impossible for arbitrary (polynomial-time computable) functions $F$.