Paper 2015/220

Key Homomorphic PRFs and Their Applications

Dan Boneh, Kevin Lewi, Hart Montgomery, and Ananth Raghunathan


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.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in CRYPTO 2013
pseudorandom functionskey homomorphismnon-uniform learning with errors
Contact author(s)
klewi @ cs stanford edu
2015-03-09: received
Short URL
Creative Commons Attribution


      author = {Dan Boneh and Kevin Lewi and Hart Montgomery and Ananth Raghunathan},
      title = {Key Homomorphic PRFs and Their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2015/220},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.