Paper 2004/310

A Verifiable Random Function With Short Proofs and Keys

Yevgeniy Dodis and Aleksandr Yampolskiy

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.

Note: 1. referenced "compact e-cash" paper by Camenisch, Hohenberger, Lysyanskaya 2. pointed out that the VRF output can trivially be viewed as a PRF, which doesn't process inputs bit-by-bit

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. To appear in PKC 2005.
Keywords
Verifiable random functionsUnique signaturesShort keys and proofsBilinear groups.
Contact author(s)
aleksandr yampolskiy @ yale edu
History
2005-03-08: revised
2004-11-16: received
See all versions
Short URL
https://ia.cr/2004/310
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/310,
      author = {Yevgeniy Dodis and Aleksandr Yampolskiy},
      title = {A Verifiable Random Function With Short Proofs and Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2004/310},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/310}},
      url = {https://eprint.iacr.org/2004/310}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.