International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Verifiable Random Function With Short Proofs and Keys

Authors:
Yevgeniy Dodis
Aleksandr Yampolskiy
Download:
URL: http://eprint.iacr.org/2004/310
Search ePrint
Search Google
Abstract: We give a simple and efficient construction of a verifiable random function (VRF) on bilinear groups. Our construction is direct. In contrast to prior VRF constructions [MRV99, Lys02], it avoids using an inefficient Goldreich-Levin transformation, thereby saving several factors in security. Our proofs of security are based on a decisional bilinear Diffie-Hellman inversion assumption, which seems reasonable given current state of knowledge. For small message spaces, our VRF's proofs and keys have constant size. By utilizing a collision-resistant hash function, our VRF can also be used with arbitrary message spaces. We show that our scheme can be instantiated with an elliptic group of very reasonable size. Furthermore, it can be made distributed and proactive.
BibTeX
@misc{eprint-2004-12276,
  title={A Verifiable Random Function With Short Proofs and Keys},
  booktitle={IACR Eprint archive},
  keywords={Verifiable random functions, Unique signatures, Short keys and proofs, Decisional bilinear Diffie-Hellman assumption, Bilinear groups.},
  url={http://eprint.iacr.org/2004/310},
  note={To appear in PKC 2005. aleksandr.yampolskiy@yale.edu 12850 received 16 Nov 2004, last revised 7 Mar 2005},
  author={Yevgeniy Dodis and Aleksandr Yampolskiy},
  year=2004
}