Re: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions

[Dan Brown <[e-mail]>]

Answering myself below: VRFs have been around since 1999, so are not so new.  ‎Still don't like the name, and still have trouble seeing the value.

From: Dan Brown
Sent: Tuesday, July 18, 2017 2:29 PM
To: Sharon Goldberg; [e-mail]
Cc: [e-mail]; Leonid Reyzin; Dimitrios Papadopoulos
Subject: Re: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions


Hi Sharon and CFRG,

On VRFs, my uncertain comments to consider at your leisure:

Is it fair to say VRFs are relatively new?  If so, then maybe a little more caution is needed about their use.  It seems a tad hasty that it is being used already.

To me, it seems that VRFs are basically signatures, with an extra feature.  My concern is that this extra feature might get overused, before it is thoroughly reviewed.

It is unsurprising to me that random oracle model proof can prove the output of a hash to be random.  My intuitive concern is that at least informally, this is kind of circular.  Hashes often have some non-random-ish properties that might affect the extra security (over signatures) that VRFs are aiming for.  I guess I would much prefer a proof saying if the hash has (well-studied) properties XYZ, then your construction are VRFs.  (Maybe you have this already?  If so, then tell me so.)

Since, VRFs require sending the “proofs” on the wire, I find it hard to see how it could be used to prevent dictionary attacks.  I assume that you are saying the proofs must be encrypted when one needs to avoid dictionary models?  I suppose all the details are there in I-D and papers, but for now, I am confused about the threat model (which parties have keys, etc., if they require a secure channel and mutual trust, why just use plain old hash,…). To resist dictionary attacks, were already have PAKEs and PBHashing.  Now this?

Finally, on a bikeshed-coloring note, I object to the name “verifiable random function”, on several grounds.


  1.  It is not a function.  It is at least four functions, keygen, sign, verify, and hashify.
  2.  If you make it into a keyed function F_sk(m), as in prooftohash(sign_sk(m)), it is not verifiable.
  3.  Verification requires the intermediate proof, which is certainly not even pseudorandom (it is easy to distinguish valid signatures from random).
  4.  It is pseudorandom, not random.  (The keys are random, but many crypto has keys, without having “random” in its name: encryption, MAC, signatures, key exchange, …, they also don’t verifiable or random in their names either.)
  5.  The similar phrase “verifiably random”, albeit as a misnomer, has past precedents, see NIST P-256 and Brainpool, etc.  When I see VRF, I think a function, that aims to VR in that sense, and great, now we can improve on Brainpool, etc.
  6.  “Random function” should be reserved for the ideal random mapping concept, for example, as studied by Flajolet-Odlyzko (ok they only studied the case of equal size domain and range).  The random oracle model, is the idea of approximating this ideal, etc.  An actual approximation should not be name as the ideal (sorry, I’m kind of repeating my point 4).

Please forgive the fact that my comments above are not very constructive (or if the tone is wrong).  This is a new topic for me, so I am reluctant too many suggestions.  Nonetheless, I suggest (0) waiting a little, (1) a non-random-oracle security proof (if you don’t have it yet), (2) re-naming the scheme to something like re-hashable (or digestible) signatures (and re-name the various parts, i.e. proof -> signature, etc.).

Best regards,

Dan


From: Cfrg [mailto:[e-mail]] On Behalf Of Sharon Goldberg
Sent: Wednesday, July 12, 2017 5:42 AM
To: [e-mail]
Cc: [e-mail]; Dimitrios Papadopoulos <[e-mail]>; Leonid Reyzin <[e-mail]>
Subject: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions

Dear CFRG,

I'm presenting at next week's meeting on Verifiable Random Functions. A 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 it.  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).

In advance of the meeting, please see:

1) Our substantially updated -01 draft:
https://datatracker.ietf.org/doc/draft-goldbe-vrf/

2) Our project page, with links to various VRF implementations:
https://www.cs.bu.edu/~goldbe/projects/vrf

Comments welcome.  Thanks,

Sharon

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