**Key Homomorphic PRFs and Their Applications**

*Dan Boneh and Kevin Lewi and Hart Montgomery and Ananth 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 xor k2, x), where xor 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.

**Category / Keywords: **secret-key cryptography / pseudorandom functions, key homomorphism, non-uniform learning with errors

**Original Publication**** (in the same form): **IACR-CRYPTO-2013

**Date: **received 8 Mar 2015

**Contact author: **klewi at cs stanford edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20150309:210400 (All versions of this report)

**Short URL: **ia.cr/2015/220

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]