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
-
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},
url = {https://eprint.iacr.org/2010/102}
}
