Welcome to the resource topic for
**2002/133**

**Title:**

Efficient Construction of (Distributed) Verifiable Random Functions

**Authors:**
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.

**ePrint:**
https://eprint.iacr.org/2002/133

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .