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.
Category / Keywords: foundations / verifiable random functions, pseudorandom functions, distributed pseudorandom functions, random oracle, DDH assumption, CDH/DDH separation, unique signatures Publication Info: PKC 2003 Date: received 28 Aug 2002, last revised 16 Oct 2002 Contact author: dodis at cs nyu edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20021016:212436 (All versions of this report) Short URL: ia.cr/2002/133 Discussion forum: Show discussion | Start new discussion