Paper 2009/486

Efficient Pseudorandom Functions From the Decisional Linear Assumption and Weaker Variants

Allison Lewko and Brent Waters

Abstract

In this paper, we generalize Naor and Reingold's construction of pseudorandom functions under the DDH Assumption to yield a construction of pseudorandom functions under the decisional $k$-Linear Assumption, for each $k\geq 1$. The decisional Linear Assumption was first introduced by Boneh, Boyen, and Shacham as an alternative assumption for settings where the DDH problem is easy, such as bilinear groups. This assumption can be generalized to obtain the decisional $k$-Linear Assumptions. Shacham and Hofheinz and Kiltz showed that the decisional $(k+1)$-Linear problem is hard for generic groups even when the decisional $k$-Linear problem is easy. It is thus desirable to have constructions of cryptographic primitives based on the decisional $k$-Linear Assumption instead of DDH. Not surprisingly, one must pay a small price for added security: as $k$ increases, our constructed functions become slightly less efficient to compute and the key size increases (quadratically in $k$).

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. this is a full version of a paper that will appear in CCS 2009
Contact author(s)
alewko @ cs utexas edu
History
2009-10-16: last of 3 revisions
2009-10-05: received
See all versions
Short URL
https://ia.cr/2009/486
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/486,
      author = {Allison Lewko and Brent Waters},
      title = {Efficient Pseudorandom Functions From the Decisional Linear Assumption and Weaker Variants},
      howpublished = {Cryptology ePrint Archive, Paper 2009/486},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/486}},
      url = {https://eprint.iacr.org/2009/486}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.