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
-
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},
url = {https://eprint.iacr.org/2010/442}
}
