Paper 2011/337

Functional Re-encryption and Collusion-Resistant Obfuscation

Nishanth Chandran, Melissa Chase, and Vinod Vaikuntanathan


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$.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Full version of paper published at TCC 2012
Contact author(s)
melissac @ microsoft com
2012-04-17: revised
2011-06-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nishanth Chandran and Melissa Chase and Vinod Vaikuntanathan},
      title = {Functional Re-encryption and Collusion-Resistant Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2011/337},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.