Paper 2002/133

Efficient Construction of (Distributed) Verifiable Random Functions

Yevgeniy Dodis


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.

Available format(s)
Publication info
Published elsewhere. PKC 2003
verifiable random functionspseudorandom functionsdistributed pseudorandom functionsrandom oracleDDH assumptionCDHDDH separationunique signatures
Contact author(s)
dodis @ cs nyu edu
2002-10-16: last of 2 revisions
2002-08-29: received
See all versions
Short URL
Creative Commons Attribution


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