Key Homomorphic PRFs and Their Applications
Authors: D. Boneh, K. Lewi, H. Montgomery, and A. Raghunathan
Abstract:
A pseudorandom function F: K x X → Y is said to
be key homomorphic if given F(k1,x) and F(k2,x) there is an
efficient algorithm to compute F(k1 ⊕ k2, x), where ⊕
denotes a group operation on k1 and k2 such as xor.
Key homomorphic PRFs are natural objects to study and have a number of
interesting applications: they can simplify the process of rotating
encryption keys for encrypted data stored in the cloud, they give one
round distributed PRFs, and they can be the basis of a symmetric-key
proxy re-encryption scheme. Until now all known constructions for key
homomorphic PRFs were only proven secure in the random oracle model.
We construct the first provably secure key homomorphic PRFs in the
standard model. Our main construction is based on the learning with
errors (LWE) problem. In the proof of security we need a variant of
LWE where query points are non-uniform and we show that this variant
is as hard as the standard LWE. We also construct key homomorphic
PRFs based on the decision linear assumption in groups with an
l-linear map. We leave as an open problem the question of
constructing standard model key homomorphic PRFs from more general
assumptions.
Reference:
In Proceedings of Crypto 2013, pp. 410-428.
[BIBTEX]
Full paper: pdf