Paper 2010/102

Constructing Verifiable Random Functions with Large Input Spaces

Susan Hohenberger and Brent Waters


We present a family of verifiable random functions which are provably secure for exponentially-large input spaces under a non-interactive complexity assumption. Prior constructions required either an interactive complexity assumption or one that could tolerate a factor 2^n security loss for n-bit inputs. Our construction is practical and inspired by the pseudorandom functions of Naor and Reingold and the verifiable random functions of Lysyanskaya. Set in a bilinear group, where the Decisional Diffie-Hellman problem is easy to solve, we require the Decisional Diffie-Hellman Exponent assumption in the standard model, without a common reference string. Our core idea is to apply a simulation technique where the large space of VRF inputs is collapsed into a small (polynomial-size) input in the view of the reduction algorithm. This view, however, is information-theoretically hidden from the attacker. Since the input space is exponentially large, we can first apply a collision-resistant hash function to handle arbitrarily-large inputs.

Note: An earlier draft did not properly handle input zero. This is now addressed.

Available format(s)
Publication info
Published elsewhere. To appear in Eurocrypt 2010. This is the full version.
VRFPRFlarge inputsstandard model
Contact author(s)
susan @ cs jhu edu
2010-05-24: last of 4 revisions
2010-03-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Susan Hohenberger and Brent Waters},
      title = {Constructing Verifiable Random Functions with Large Input Spaces},
      howpublished = {Cryptology ePrint Archive, Paper 2010/102},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.