**Functional Re-encryption and Collusion-Resistant Obfuscation**

*Nishanth Chandran and 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$.

**Category / Keywords: **public-key cryptography / re-encryption, obfuscation

**Publication Info: **Full version of paper published at TCC 2012

**Date: **received 22 Jun 2011, last revised 17 Apr 2012

**Contact author: **melissac at microsoft com

**Available format(s): **PDF | BibTeX Citation

**Version: **20120417:162657 (All versions of this report)

**Short URL: **ia.cr/2011/337

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]