Abhishek Banerjee, Georg Fuchsbauer, Chris Peikert, Krzysztof Pietrzak, and Sophie Stevens
Abstract
A pseudorandom function (PRF) is a keyed function where, for a random key
, the function is indistinguishable from a
uniformly random function, given black-box access. A
\emph{key-homomorphic} PRF has the additional feature that for any
keys and any input , we have for some group operations on and
, respectively. A \emph{constrained} PRF for a family of
sets has the property that,
given any key and set , one can efficiently compute
a ``constrained'' key that enables evaluation of on all
inputs , while the values for remain
pseudorandom even given .
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.
@misc{cryptoeprint:2015/180,
author = {Abhishek Banerjee and Georg Fuchsbauer and Chris Peikert and Krzysztof Pietrzak and Sophie Stevens},
title = {Key-Homomorphic Constrained Pseudorandom Functions},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/180},
year = {2015},
url = {https://eprint.iacr.org/2015/180}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.