Paper 2010/102

Constructing Verifiable Random Functions with Large Input Spaces

Susan Hohenberger and Brent Waters

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. To appear in Eurocrypt 2010. This is the full version.
Keywords
VRFPRFlarge inputsstandard model
Contact author(s)
susan @ cs jhu edu
History
2010-05-24: last of 4 revisions
2010-03-01: received
See all versions
Short URL
https://ia.cr/2010/102
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/102,
      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{https://eprint.iacr.org/2010/102}},
      url = {https://eprint.iacr.org/2010/102}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.