Verifiable Random Functions

Silvio Micali, Michael Rabin, and Salil Vadhan


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.


BibTeX entry

  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 ]