Verifiable Random Functions (VRFs)

Abstract:     A Verifiable Random Function (VRF) is the public-key version of keyed cryptographic hash. Only the holder of the VRF secret key can compute the hash, but anyone with the public key can verify the correctness of the hash. VRFs can be used to prevent dictionary attacks on hash-based data structures, and have applications to key transparency (CONIKS), DNSSEC (NSEC5), and cryptocurrencies (Algorand). The project specifies and implements fast and practical VRFs. One of our VRFs is based on elliptic curves (under the DDH assumption) and another VRF is based on RSA. Our VRFs come with formal concrete cryptographic security proofs (in the random oracle model) with careful analysis, including fixing bugs in prior work.

Overview:   slides        IETF Internet Draft (draft-goldbe-vrf)
Security proofs:   ePrint Report 2017/099 (see Figures 1-2 and Appendix B-C).
Implementation:   GitHub

Slides:
  CFRG at IETF'99 (Sharon Goldberg, 7/2017)
  EUROCRYPT'17 rump session (Leonid Reyzin, 5/2017)
  SAAG at IETF'98 (Sharon Goldberg, 3/2017)

Papers:

  1. Making NSEC5 Practical for DNSSEC
    Dimitrios Papadopoulos, Duane Wessels, Shumon Huque, Jan Včelák, Moni Naor, Leonid Reyzin, Sharon Goldberg,
    ePrint (Cryptology) Report (2017/099).     (February, 2017.)

  2. draft-goldbe-vrf: Verifiable Random Functions (VRFs)
    Sharon Goldberg, Dimitrios Papadopoulos, Jan Včelák, .
    IETF Internet Draft. First version March 2017, last updated July 2017.
    IETF draft.     work-in-progress version (GitHub).    

Implementations:

Below is a collection of links to open-source projects that use a VRF. Not all of these implementations are compatible with our specification, although they are all very similar. Please contact us if you want your implementation to be added here.

  1. Our implementation GitHub
  2. Google Key Transparency GitHub
  3. CONIKS GitHub
  4. Yahoo! coname GitHub
  5. Open Whisper GitHub     VxEDDSA spec

Team: (in alphabetical order)

This material is based upon work supported by the US National Science Foundation under Grants 017907, 1347525, 1012798, and 1012910, a gift from Verisign Labs, the Israel Science Foundation , BSF and IMOS, and from the I-CORE Program of the Planning and Budgeting Committee and the Israel Science Foundation. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors.

Last updated July 11, 2017.