Algebraic pseudorandom functions with improved efficiency from the augmented cascade
Authors: D. Boneh, H. Montgomery, and A. 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.
Reference:
In proceedings of the 17'th ACM conference on Computer and
Communications Security (CCS),
2010.
[BIBTEX]
Full paper: pdf