Abstract: 
A pseudorandom function (PRF) is a keyed function F : K × X → Y where, for a random key k ∈ K, the function F(k, ·) is indistinguishable from a uniformly random function, given blackbox access. A 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)⊕F(k', x) for some group operations +,⊕ on K and Y, respectively. A constrained PRF for a family of setsS ⊆ P(X) has the property that, given any key k and set S ∈ S, one can efficiently compute a “constrained” key kS that enables evaluation of F(k, x) on all inputs x ∈ S, while the values F(k, x) for x /∈ S remain pseudorandom even given kS. In this paper we construct PRFs that are simultaneously constrained 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 keyhomomorphic. We then show that the LWEbased keyhomomorphic PRFs of Banerjee and Peikert (Crypto 2014) are essentially already 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 schemewith 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.

Notes: 
Research supported by ERC starting grant (259668
PSPC).
This material is based upon work supported by the National Science Foundation under CA
REER Award CCF1054495, by DARPA under agreement number FA875011C0096, and
by the Alfred P. Sloan Foundation. Any opinions, findings, and conclusions or recommenda
tions expressed in this material are those of the author(s) and do not necessarily reflect the
views of the National Science Foundation, DARPA or the U.S. Government, or the Sloan
Foundation. The U.S. Government is authorized to reproduce and distribute reprints for
Governmental purposes notwithstanding any copyright notation thereon.
Research supported by ERC starting grant (259668
PSPC).
