International Association
for Cryptologic Research

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 black-box access. A

\\emph{key-homomorphic} 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 map-based

bit-fixing and circuit-constrained PRFs of Boneh and Waters (Asiacrypt

2013) can be modified to also be \\emph{key-homomorphic}. We then show

that the LWE-based key-homomorphic PRFs of Banerjee and Peikert

(Crypto 2014) are essentially already \\emph{prefix-constrained} PRFs,

using a (non-obvious) 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 key-homomorphic constrained PRFs, we construct a

proxy re-encryption scheme with fine-grained 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 re-key (arbitrary subsets of) the ciphertexts

without learning anything about the plaintexts, thus permitting

efficient and fine-grained revocation.