Team for Research in
Ubiquitous Secure Technology

Citation
Kevin Lewi. "Key Homomorphic PRFs and Their Applications". Talk or presentation, 9, October, 2013.

Abstract
A pseudorandom function F : K ⨯ 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. We also give a construction based on the decision linear assumption in groups with an linear map. We leave as an open problem the question of constructing standard model key homomorphic PRFs from more general assumptions.

Electronic downloads

• Lewi_2013_TRUST.pdf · application/pdf · 543 kbytes

• HTML

  Kevin Lewi. <a
  href="http://www.truststc.org/pubs/914.html"
  ><i>Key Homomorphic PRFs and Their
  Applications</i></a>, Talk or presentation,  9,
  October, 2013.

• Plain text

  Kevin Lewi. "Key Homomorphic PRFs and Their
  Applications". Talk or presentation,  9, October, 2013.

• BibTeX

  @presentation{Lewi13_KeyHomomorphicPRFsTheirApplications,
      author = {Kevin Lewi},
      title = {Key Homomorphic PRFs and Their Applications},
      day = {9},
      month = {October},
      year = {2013},
      abstract = {A pseudorandom function F : K ⨯ 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. We also give a construction based
                on the decision linear assumption in groups with
                an linear map. We leave as an open problem the
                question of constructing standard model key
                homomorphic PRFs from more general assumptions.},
      URL = {http://www.truststc.org/pubs/914.html}
  }
  

Posted by Carolyn Winter on 13 Nov 2013.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.