2015 | OriginalPaper | Chapter
Key-Homomorphic Constrained Pseudorandom Functions
Authors : Abhishek Banerjee, Georg Fuchsbauer, Chris Peikert, Krzysztof Pietrzak, Sophie Stevens
Published in: Theory of Cryptography
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A pseudorandom function (PRF) is a keyed function
$F : {\mathcal K}\times{\mathcal X}\rightarrow{\mathcal Y}$
where, for a random key
$k\in{\mathcal K}$
, the function
F
(
k
,·) is indistinguishable from a uniformly random function, given black-box access. A
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
) ⊕
F
(
k
′,
x
) for some group operations + , ⊕ on
$\mathcal{K}$
and
$\mathcal{Y}$
, respectively. A
constrained
PRF for a family of sets
${\mathcal S} \subseteq \mathcal{P}({\mathcal X})$
has the property that, given any key
k
and set
$S \in \mathcal{S}$
, one can efficiently compute a “constrained” key
k
S
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
k
S
.
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 map-based bit-fixing and circuit-constrained PRFs of Boneh and Waters (Asiacrypt 2013) can be modified to also be
key-homomorphic
. We then show that the LWE-based key-homomorphic PRFs of Banerjee and Peikert (Crypto 2014) are essentially already
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.