[HW10] Constructing Verifiable Random Functions with Large Input Spaces
Authors: Susan Hohenberger, Brent Waters | Venue: EUROCRYPT 2010 | Source
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.
BibTeX
@Inproceedings{EC:HohWat10,
author = {Susan Hohenberger and Brent Waters},
title = {Constructing Verifiable Random Functions with Large Input Spaces},
pages = {656--672},
editor = {Henri Gilbert},
booktitle = {Advances in Cryptology -- {EUROCRYPT}~2010},
volume = {6110},
series = {Lecture Notes in Computer Science},
address = {French Riviera},
month = {may~30~--~jun~3},
publisher = {Springer Berlin Heidelberg, Germany},
year = {2010},
doi = {10.1007/978-3-642-13190-5_33},
}