## IACR paper details

Title | Constructing Veriﬁable Random Functions with Large Input Spaces |
---|

Booktitle | IACR Eprint archive |
---|

Pages | |
---|

Year | 2010 |
---|

URL | http://eprint.iacr.org/2010/102 |
---|

Author | Susan Hohenberger |
---|

Author | 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. |
---|

Search for the paper

@misc{eprint-2010-23003,
title={Constructing Veriﬁable Random Functions with Large Input Spaces},
booktitle={IACR Eprint archive},
keywords={foundations / VRF, PRF, large inputs, standard model},
url={http://eprint.iacr.org/2010/102},
note={To appear in Eurocrypt 2010. This is the full version. susan@cs.jhu.edu 14753 received 24 Feb 2010, last revised 23 May 2010},
author={Susan Hohenberger and Brent Waters},
year=2010
}

Download a complete BibTeX file.