Verifiable Random Functions

Silvio Micali, Michael Rabin, and Salil Vadhan

Abstract

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

Versions

In Proceedings of 40th Annual Symposium on Foundations of Computer Science, pp. 120-130, New York, NY, October 1999. IEEE. [ postscript ] [ compressed postscript ]

BibTeX entry

@InProceedings{MicaliRaVa99,
  author =       {Silvio Micali and Michael Rabin and Salil Vadhan},
  title =        {Verifiable Random Functions},
  booktitle =    {Proceedings of the 40th Annual Symposium on the Foundations of Computer Science},
  year =         {1999},
  organization = {IEEE},
  month =        {October},
  pages =     {120--130},
  address =    {New York, NY}
}

[ back to Salil Vadhan's research interests ]