Team for Research in
Ubiquitous Secure Technology

Key Homomorphic PRFs and Their Applications
Kevin Lewi

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

Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.