Paper 2015/180
KeyHomomorphic Constrained Pseudorandom Functions
Abhishek Banerjee, Georg Fuchsbauer, Chris Peikert, Krzysztof Pietrzak, and Sophie Stevens
Abstract
A pseudorandom function (PRF) is a keyed function $F \colon {\cal K}\times{\cal X}\rightarrow {\cal Y}$ where, for a random key $k\in{\cal K}$, the function $F(k,\cdot)$ is indistinguishable from a uniformly random function, given blackbox access. A \emph{keyhomomorphic} PRF has the additional feature that for any keys $k,k'$ and any input $x$, we have $F(k + k', x)= F(k,x) \oplus F(k',x)$ for some group operations $+, \oplus$ on $\cal{K}$ and $\cal{Y}$, respectively. A \emph{constrained} PRF for a family of sets ${\cal S} \subseteq \cal{P}({\cal X})$ has the property that, given any key $k$ and set $S \in \cal{S}$, one can efficiently compute a ``constrained'' key $k_S$ that enables evaluation of $F(k,x)$ on all inputs $x\in S$, while the values $F(k,x)$ for $x \notin S$ remain pseudorandom even given $k_{S}$. In this paper we construct PRFs that are simultaneously constrained \emph{and} key homomorphic, where the homomorphic property holds even for constrained keys. We first show that the multilinear mapbased bitfixing and circuitconstrained PRFs of Boneh and Waters (Asiacrypt 2013) can be modified to also be \emph{keyhomomorphic}. We then show that the LWEbased keyhomomorphic PRFs of Banerjee and Peikert (Crypto 2014) are essentially already \emph{prefixconstrained} PRFs, using a (nonobvious) definition of constrained keys and associated group operation. Moreover, the constrained keys themselves are pseudorandom, and the constraining and evaluation functions can all be computed in low depth. As an application of keyhomomorphic constrained PRFs, we construct a proxy reencryption scheme with finegrained access control. This scheme allows storing encrypted data on an untrusted server, where each file can be encrypted relative to some attributes, so that only parties whose constrained keys match the attributes can decrypt. Moreover, the server can rekey (arbitrary subsets of) the ciphertexts without learning anything about the plaintexts, thus permitting efficient and finegrained revocation.
Metadata
 Available format(s)
 Publication info
 Published by the IACR in Tcc 2015
 Contact author(s)
 krzpie @ gmail com
 History
 20150304: received
 Short URL
 https://ia.cr/2015/180
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/180, author = {Abhishek Banerjee and Georg Fuchsbauer and Chris Peikert and Krzysztof Pietrzak and Sophie Stevens}, title = {KeyHomomorphic Constrained Pseudorandom Functions}, howpublished = {Cryptology ePrint Archive, Paper 2015/180}, year = {2015}, note = {\url{https://eprint.iacr.org/2015/180}}, url = {https://eprint.iacr.org/2015/180} }