Subject: [Cfrg] I-D Action: draft-irtf-cfrg-vrf-06.txt

From: [email-masked]
Date: Tue, 11 Feb 2020 09:13:58 -0800

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Crypto Forum RG of the IRTF.

        Title           : Verifiable Random Functions (VRFs)
        Authors         : Sharon Goldberg
                          Leonid Reyzin
                          Dimitrios Papadopoulos
                          Jan Vcelak
	Filename        : draft-irtf-cfrg-vrf-06.txt
	Pages           : 43
	Date            : 2020-02-11

Abstract:
   A Verifiable Random Function (VRF) is the public-key version of a
   keyed cryptographic hash.  Only the holder of the private key can
   compute the hash, but anyone with public key can verify the
   correctness of the hash.  VRFs are useful for preventing enumeration
   of hash-based data structures.  This document specifies several VRF
   constructions that are secure in the cryptographic random oracle
   model.  One VRF uses RSA and the other VRF uses Eliptic Curves (EC).

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/

There are also htmlized versions available at:
https://tools.ietf.org/html/draft-irtf-cfrg-vrf-06
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-06

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-vrf-06

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: Leonid Reyzin <[email-masked]>
Date: Tue, 11 Feb 2020 12:31:46 -0500

Dear CFRG,

This most recent update to the VRF draft consists of minor clarifications.
FYI, in case you are wondering why the VRF draft has not been moving
forward: hashing to elliptic curves is an important step in the design of
the elliptic curve VRF. In order to avoid having multiple versions of
hashing to elliptic curves, we are currently working with the authors of
the Hashing to Elliptic Curves draft (
https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve/,
https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve) to bring our two
drafts into alignment, with the eventual goal having the two drafts move
forward together.

Cheers,

 Leo, Sharon, Jan, Dimitris

On Tue, Feb 11, 2020 at 12:14 PM <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Manu Sporny <[email-masked]>
Date: Tue, 11 Feb 2020 16:50:15 -0500

> This most recent update to the VRF draft consists of minor clarifications.

Hi Leo, Sharon, Jan, and Dimitris,

I've been following this work for years now and I still don't know why
VRFs are useful. Every time you publish a new draft, I got out and scour
the Web for an easily readable description of a use case that is solved
by the use of a VRF and end up reading things like:

"It is a pseudo-random function that provides publicly verifiable proofs
of its outputs' correctness."

"VRFs are useful for preventing enumeration of hash-based data structures."

"VRFs ... useful for providing a 1:1 mapping of low entropy inputs (e.g.
names, email addresses, phone numbers) to some random values which can
be committed to in advance, e.g. through a timestamping service such as
a transparency log."

I say this as someone that spends quite a bit of time reading IETF
cryptography specs and writing specifications that directly utilize
IETF/CFRG cryptography specs (at IETF and W3C).

Can you please add a few real world use cases where one would use a VRF?
Are they useful for committing values on a public blockchain in a
privacy preserving manner? If so, what sorts of values? Are they useful
when voting? Are they useful for distributed gaming scenarios? Some
concrete uses would be more helpful than the overly general text in the
current spec.

-- manu

-- 
Manu Sporny (skype: msporny, twitter: manusporny)
Founder/CEO - Digital Bazaar, Inc.
blog: Veres One Decentralized Identifier Blockchain Launches
https://tinyurl.com/veres-one-launches

---

From: Jeff Burdges <[email-masked]>
Date: Wed, 26 Feb 2020 12:31:32 +0100

Almost all proof-of-staake blockchain protocols require VRFs for various purposes, including driving random beacons, leading block production or BFT agreement processes, or selecting validation assignments in sharding situations.

Identity schemes come in many flavours, but they should be built on ring or group VRFs, or maybe similar constructions like linkable ring signatures, whenever they must (1) prevent Sibel attacks, and (2) be useable for a wide variety of purposes, and (3) do not trust some issuer with user privacy.

In essence, Sibel protections require some uniqueness per key holder, but being general purpose means that uniqueness must differ across domains to whom the key holder identifies themselves, so that unique amounts to a VRF output, and you need ring or group to hide what key generates it.

There are SNARK constructions that drop (3) and maybe avoid key pairs, making them not "VRF signatures” like described in this draft, but they still possess roughly the same sort of uniqueness, etc. definitions from section 3 of this craft.

Jeff

> On 11 Feb 2020, at 22:50, Manu Sporny <[email-masked]> wrote:
>

---

From: Jeff Burdges <[email-masked]>
Date: Wed, 26 Feb 2020 14:54:03 +0100

We’ve had an internal discussion about whether VRF proving should be called VRF signing.  I think existing literature is rather evenly divided on this point, well depending upon how far back you go.  ;)

I think “prove” gets used when authors from the theory side want to stress the similarity with hash functions.  Implementors write “sign” to stress that their VRF either works like a signature scheme, or even was made miss-use resistant similarly to signature schemes, ala https://www.signal.org/docs/specifications/xeddsa/

I personally use dleq_prove for Schnorr DLEQ proofs because the absence of a key pair makes them tricky to use correctly, but use vrf_sign for Schnorr VRFs because done well they wind up as missuse resistant as a Schnorr signature.  I write VRF signature and VRF output in protocol descriptions.

There is another question about the relationship between the various VRF properties and the signature scheme security assumptions, although not sure if this draft is the place to make the distinctions and prove any equivalences.  Intuitively, you do want a scheme that is both a VRF and a signature more often than this draft lets on.

Also, VRFs based on Schnorr DLEQ proofs should include an extra message field because applications need to authenticate the message that carries the VRF output, like a block in Ouroboros Praos.  We needed this extra message field in the ring VRF in our new Sassafras SSLE protocol, either that or make annoying usage of FO.  You can do this with delinearization, but that’s less efficient.

Jeff

> On 11 Feb 2020, at 18:13, [email-masked] wrote:
> 
>