International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Algebraic Pseudorandom Functions with Improved Efficiency from the Augmented Cascade

Authors:
Dan Boneh
Hart Montgomery
Ananth Raghunathan
Download:
URL: http://eprint.iacr.org/2010/442
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2010-23343,
  title={Algebraic Pseudorandom Functions with Improved Efficiency from the Augmented Cascade},
  booktitle={IACR Eprint archive},
  keywords={foundations / pseudorandom functions},
  url={http://eprint.iacr.org/2010/442},
  note={ACM CCS 2010 dabo@cs.stanford.edu 14834 received 13 Aug 2010},
  author={Dan Boneh and Hart Montgomery and Ananth Raghunathan},
  year=2010
}