Paper 2002/133

Efficient Construction of (Distributed) Verifiable Random Functions

Yevgeniy Dodis

Abstract

We give the first simple and efficient construction of {\em verifiable random functions} (VRFs). VRFs, introduced by Micali et al. [MRV99], combine the properties of regular pseudorandom functions (PRFs) [GGM86] (i.e., indistinguishability from a random function) and digital signatures [GMR88] (i.e., one can provide an unforgeable proof that the VRF\ value is correctly computed). The efficiency of our VRF construction is only slightly worse than that of a regular PRF construction of Naor and Reingold [NR97]. In contrast to ours, the previous VRF constructions [MRV99,Lys02] all involved an expensive generic transformation from verifiable unpredictable functions (VUFs), while our construction is simple and direct. We also provide the first construction of {\em distributed} VRFs. Our construction is more efficient than the only known construction of distributed (non-verifiable) PRFs [Nie02], but has more applications than the latter. For example, it can be used to distributively implement the random oracle model in a {\em publicly verifiable} manner, which by itself has many applications (e.g., constructing threshold signature schemes). Our main construction is based on a new variant of decisional Diffie-Hellman (DDH) assumption on certain groups where the regular DDH assumption does {\em not} hold. We do not make any claims about the validity of our assumption (which we call {\em sum-free} DDH, or sf-DDH). However, this assumption seems to be plausible based on our {\em current} understanding of certain candidate elliptic and hyper-elliptic groups which were recently proposed for use in cryptography [JN01,Jou00]. We hope that the demonstrated power of our sf-DDH assumption will serve as a motivation for its closer study.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. PKC 2003
Keywords
verifiable random functionspseudorandom functionsdistributed pseudorandom functionsrandom oracleDDH assumptionCDHDDH separationunique signatures
Contact author(s)
dodis @ cs nyu edu
History
2002-10-16: last of 2 revisions
2002-08-29: received
See all versions
Short URL
https://ia.cr/2002/133
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/133,
      author = {Yevgeniy Dodis},
      title = {Efficient Construction of (Distributed) Verifiable Random Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2002/133},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/133}},
      url = {https://eprint.iacr.org/2002/133}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.