Verifiable random functions

Abstract

We efficiently combine unpredictability and verifiability by extending the Goldreich-Goldwasser-Micali (1986) construction of pseudorandom functions f/sub s/ from a secret seed s, so that knowledge of s not only enables one to evaluate f/sub s/ at any point x, but also to provide an NP-proof that the value f/sub s/(x) is indeed correct without compromising the unpredictability of f/sub s/ at any other point for which no such a proof was provided.