Subject: [Cfrg] new draft specifying VRFs (verifiable random functions)

From: Sharon Goldberg <[email-masked]>
Date: Mon, 13 Mar 2017 10:27:11 -0400

Several of us have been working a draft specification for Verifiable Random
Functions (VRFs). A VRF is the public-key version of a keyed cryptographic
hash function.  Only the holder of the private VRF key can compute the
hash, but anyone with the corresponding public key can verify the
correctness of the hash.   This draft has one VRF based on RSA, and another
based on elliptic curves.

 https://datatracker.ietf.org/doc/draft-goldbe-vrf/

Our team is using a VRF to prevent zone enumeration with NSEC5 for DNSSEC
[1,2]. The Google Key Transparency project is using a similar VRF to
prevent key enumeration [3,4]. Open Whisper systems has also specified a
similar VRF [5].   We think VRFs will be useful for other applications as
well, so we think it would be helpful to have a standard way to implement
them.

We've requested an agenda slot at SAAG to talk about VRFs.  The chairs have
requested that we send out a note to CFRG ahead of time, so here it is.
Hope to chat in person at IETF and/or on this list.

Thanks,

Sharon
(with Dimitris Papadopoulos, Jan Vcelak, Leonid Reyzin, Shumon Huque, David
C Lawrence)

[1] https://datatracker.ietf.org/doc/draft-vcelak-nsec5/
[2] https://gitlab.labs.nic.cz/knot/nsec5-crypto
[3]
https://security.googleblog.com/2017/01/security-through-transparency.html
[4] https://github.com/google/keytransparency/blob/master/core/vrf/vrf.go
[5] https://whispersystems.org/docs/specifications/xeddsa/

---
Sharon Goldberg
Associate Professor, Computer Science, Boston University
Sloan Research Fellow
http://www.cs.bu.edu/~goldbe

---

From: Richard Barnes <[email-masked]>
Date: Tue, 14 Mar 2017 17:11:28 -0400

Hey Sharon,

Thanks for writing this up.  One quick, probably trivial question: How do
these VRFs differ from signature schemes?  From the API point of view, they
seem very similar, if you view the proof as the signature value.

Thanks,
--Richard

On Mon, Mar 13, 2017 at 10:27 AM, Sharon Goldberg <[email-masked]>
wrote:

> Several of us have been working a draft specification for Verifiable
> Random Functions (VRFs). A VRF is the public-key version of a keyed
> cryptographic hash function.  Only the holder of the private VRF key can
> compute the hash, but anyone with the corresponding public key can verify
> the correctness of the hash.   This draft has one VRF based on RSA, and
> another based on elliptic curves.
>
> We've requested an agenda slot at SAAG to talk about VRFs.  The chairs
> have requested that we send out a note to CFRG ahead of time, so here it
> is. Hope to chat in person at IETF and/or on this list.
>
> Thanks,
>
> Sharon
> (with Dimitris Papadopoulos, Jan Vcelak, Leonid Reyzin, Shumon Huque,
> David C Lawrence)
>
> [3] https://security.googleblog.com/2017/01/security-through-
> transparency.html
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 14 Mar 2017 14:15:36 -0700

> seem very similar, if you view the proof as the signature value.

They are similar, however VRFs are not malleable in the same way as
signatures (VRFs guarantee a unique mapping of input to random output), and
specifically designed so the proof can be delivered separately from the
output (so the output can e.g. be recorded in a Merkle tree for
timestamping/transparency purposes). The latter prevents low-entropy inputs
from being preimaged, even if the public key and output are known to the
attacker (but not the proof).

-- 
Tony Arcieri

---

From: Sharon Goldberg <[email-masked]>
Date: Tue, 14 Mar 2017 18:29:26 -0400

Yes that's true. See the "uniqueness"security property defined in the
draft.

It's also very important that VRF hash outputs look pseudorandom even given
knowledge of the public key. (But not given knowledge of the corresponding
proof or secret key.) That's why the RSA-FDH-VRF hash output is the Hash of
a deterministic RSA signature, not the signature itself. See the security
considerations section of the draft for more details.

Sharon

On Tuesday, March 14, 2017, Tony Arcieri <[email-masked]> wrote:

> On Tue, Mar 14, 2017 at 2:11 PM, Richard Barnes <[email-masked]
> <javascript:_e(%7B%7D,'cvml',[email-masked]');>> wrote:
>

-- 
Sharon Goldberg
Computer Science, Boston University
http://www.cs.bu.edu/~goldbe