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 .