Paper 2010/442

Algebraic Pseudorandom Functions with Improved Efficiency from the Augmented Cascade

Dan Boneh, Hart Montgomery, and Ananth Raghunathan

Abstract

We construct an algebraic pseudorandom function (PRF) that is more efficient than the classic Naor- Reingold algebraic PRF. Our PRF is the result of adapting the cascade construction, which is the basis of HMAC, to the algebraic settings. To do so we define an augmented cascade and prove it secure when the underlying PRF satisfies a property called parallel security. We then use the augmented cascade to build new algebraic PRFs. The algebraic structure of our PRF leads to an efficient large-domain Verifiable Random Function (VRF) and a large-domain simulatable VRF.

Note: This is the full version of the extended abstract titled "Algebraic Pseudorandom Functions with Improved Efficiency from the Augmented Cascade" that appears in ACM CCS 2010.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. MINOR revision.ACM CCS 2010
DOI
https://doi.org/10.1145/3257740
Keywords
pseudorandom functions
Contact author(s)
dabo @ cs stanford edu
History
2021-07-26: revised
2010-08-17: received
See all versions
Short URL
https://ia.cr/2010/442
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/442,
      author = {Dan Boneh and Hart Montgomery and Ananth Raghunathan},
      title = {Algebraic Pseudorandom Functions with Improved Efficiency from the Augmented Cascade},
      howpublished = {Cryptology ePrint Archive, Paper 2010/442},
      year = {2010},
      doi = {https://doi.org/10.1145/3257740},
      note = {\url{https://eprint.iacr.org/2010/442}},
      url = {https://eprint.iacr.org/2010/442}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.