Cryptology ePrint Archive: Report 2015/220

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