Algebraic Pseudorandom Functions With Improved Efficiency From the Augmented Cascade

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