You are looking at a specific version 20100817:100737 of this paper. See the latest version.

Paper 2010/442

Algebraic Pseudorandom Functions with Improved Efficiency from the Augmented Cascade

Dan Boneh and 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. ACM CCS 2010
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.