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

Dan Brown <> Tue, 18 July 2017 18:29 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id ABEA1128CFF for <>; Tue, 18 Jul 2017 11:29:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.601
X-Spam-Status: No, score=-2.601 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id wiNbfm0V25tp for <>; Tue, 18 Jul 2017 11:29:05 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 5C8A6131BAD for <>; Tue, 18 Jul 2017 11:29:05 -0700 (PDT)
Received: from ([]) by with ESMTP/TLS/DHE-RSA-AES256-SHA; 18 Jul 2017 14:29:03 -0400
Received: from ( by ( with Microsoft SMTP Server (TLS) id 14.3.319.2; Tue, 18 Jul 2017 14:29:02 -0400
Received: from ([fe80::45d:f4fe:6277:5d1b]) by ([::1]) with mapi id 14.03.0319.002; Tue, 18 Jul 2017 14:29:02 -0400
From: Dan Brown <>
To: Sharon Goldberg <>, "" <>
CC: "" <>, Dimitrios Papadopoulos <>, Leonid Reyzin <>
Thread-Topic: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions
Thread-Index: AQHS+vM6+DG9anuMcU+xW6RwdHg7uaJZ5Flg
Date: Tue, 18 Jul 2017 18:29:02 +0000
Message-ID: <>
References: <>
In-Reply-To: <>
Accept-Language: en-US, en-CA
Content-Language: en-US
x-originating-ip: []
Content-Type: multipart/alternative; boundary="_000_810C31990B57ED40B2062BA10D43FBF501B63B22XMB116CNCrimnet_"
MIME-Version: 1.0
Archived-At: <>
Subject: Re: [Cfrg] draft-goldbe-vrf: Verifiable Random Functions
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 18 Jul 2017 18:29:09 -0000

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,


From: Cfrg [] On Behalf Of Sharon Goldberg
Sent: Wednesday, July 12, 2017 5:42 AM
Cc:; Dimitrios Papadopoulos <>; Leonid Reyzin <>
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:

2) Our project page, with links to various VRF implementations:

Comments welcome.  Thanks,


Sharon Goldberg
Computer Science, Boston University