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

Sharon Goldberg <> Wed, 26 July 2017 11:42 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id F10CE131FFB for <>; Wed, 26 Jul 2017 04:42:56 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id VYshFKKrnkPa for <>; Wed, 26 Jul 2017 04:42:53 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4001:c06::235]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 454BC132006 for <>; Wed, 26 Jul 2017 04:42:53 -0700 (PDT)
Received: by with SMTP id m88so57929194iod.2 for <>; Wed, 26 Jul 2017 04:42:53 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=wKuos3xs8sP15YWadbD1gSVAX6cwcMDB6a99GeWlMfA=; b=J5hXqGNTSjDzkUY7ZwCUByAHZKHhqvkXeBSWN2fN3jEUe/NnuPzH6AWrQFhWNQCBRn XfRcx+vBG6lsRtEWXHxTJtbMFoor3giiOZc2ScTuGDbwlGUumg/uSk1KRjI2Ljhkw4bt TdLW4MsI90E2QAF1E/hJ85dcXQpUhLxYnCdTMafI9fX1yaCAHZBoaPbIaDROhRiRbk1I WdS+q2U1kZEhEz2b+tO/QhQTTXIxlnVBPkFcOibY1wZgHK4RPdeNxbOeQQPOac8BQ6U2 bd+9Dt1/JDiBh7OnM9ME7finzH8liWdNfk6i3Mp12gq/16YK/t0HZOIiC+H/CltPOrph HqeA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=wKuos3xs8sP15YWadbD1gSVAX6cwcMDB6a99GeWlMfA=; b=tJ3g6+ubPznAtWI0gPZ6FTwPMWAKbGYL+twXIFSXVTdQvvCnXvKg4qfWEv2WXrdo8V /ML3xpegsW8bvmW3uwfwbKdS2Tz+mD68RgdzmWndVy7lm9oBQ2nCgOjNLZEp/RTAPwQO 8ILiqKny9Sa+JenMNYfultq/P4HnL8GS7drhJFHhFvFdvENGeA3BHHS6hSAWDZHgzmv2 SBqZ+DzLDiMAjDFGduzo+Z7A0BQQXNBNMRaQkoHNUnW1BjO1gyAh0aJJKXQrqk4mfB9M 0Zhcv7gtGSmQl/5KrPXtYvhloQA7qzAtdhqK7k5wBdu9QZ9yAe8kEaHrXDCwTfp6RBAz 3/bQ==
X-Gm-Message-State: AIVw110krVIq23jBGmGCORlCHXv83plkmEaLIhR3c+Yi067anJ7DFFv+ 4ARNN0T5gp2T/LPB3yrMQBIVbCOhZA==
X-Received: by with SMTP id f78mr622260iod.141.1501069372517; Wed, 26 Jul 2017 04:42:52 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Wed, 26 Jul 2017 04:42:11 -0700 (PDT)
In-Reply-To: <>
References: <> <> <> <> <>
From: Sharon Goldberg <>
Date: Wed, 26 Jul 2017 14:42:11 +0300
Message-ID: <>
To: Thomas Garcia <>
Cc: Dan Brown <>, "" <>, "" <>, Dimitrios Papadopoulos <>, Leonid Reyzin <>
Content-Type: multipart/alternative; boundary="001a113ecb70bb7422055536f20c"
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: Wed, 26 Jul 2017 11:42:57 -0000

Hi Thomas,

1. It seems that one of the properties that you are interested that the VRF
> will have is determinism. On the other hand, the EC-VRF value is dependent
> on the choice of some random number k. How are these two facts compatible?
> Am I missing something?

We require determinism from the VRF hash output, which is obtained from the
VRF proof via the "proof2hash" function.

The EC-VRF proof has 3 values: gamma, c, s
Values c and s depends on the choice of random number k
But value gamma does not depend on k.

We get determinism because the VRF hash output (derived using "proof2hash")
depends only on gamma, but not on c and s.

Slide 28 from my CFRG presentations gives a pictorial explanation of this:

2. The value c calculated in EC-VRF is only 128 bits long for Ed25519. In
> normal usage of Ed25519 the signature uses the full length of the hash
> output. Doesn't this expose the signature to collision attacks?
> No. We worked this out in our proofs of security.  Section B.2.1 of this
paper explains why this works.


> Thank you for your comments. Indeed, VRFs have been around since 1999.
>> They are really "verifiable PRFs" but the name is by now standard in the
>> crypto literature, and changing it will cause more confusion than keeping
>> it.
>> In terms of the VRF's security properties, there are three:  uniqueness,
>> collision resistance, and pseudorandomness. These are defined in our draft (
>> How VRFs prevent dictionary attacks: a public hash is subject to a
>> dictionary attack because, given the output, an adversary can evaluate the
>> hash on different inputs and see what hits the outputs. In a VRF, the
>> adversary can't evaluate the hash on different inputs.
>> You say it's not surprising that "random oracle model proof can prove the
>> output of a hash to be random". But actually, the output of a hash is NOT
>> random if the input and the hash function are known. This is because the
>> output of a hash is deterministic (every input maps to a unique output).
>> That's exactly what enables dictionary attacks. This is in contrast to a
>> VRF, where the output is (pseudo)random even given knowledge of the input.
>> Only once the VRF proof is given, does the VRF output stop looking random.
>> Note that random oracles are not essential for VRFs, and non-random-oracles
>> constructions exist (but are less efficient than what we propose to
>> standardize).
>> As far as use cases, here are a few:
>> In the NSEC5 use case for DNSSEC, you have sensitive data (domain names)
>> and you sign consecutive pairs of hashes of domain names in order to be
>> able to prove absence of a name. If you just use standard hashing, whenever
>> signed hash values are disclosed, your sensitive data is subject to
>> dictionary attacks. VRFs solve that problem, and sensitive names don't have
>> to be disclosed at all. More details are in
>> 7/099.pdf
>> In CONIKS (also Google Key Transparency, Signal secure messaging, Yahoo!
>> Coname) you also have some sensitive data (user names) that are put into a
>> Merkle-like authenticated data structure. If you just use standard hashing,
>> whenever hash values are disclosed, sensitive data is subject to dictionary
>> attacks. If you use VRFs, sensitive data again can be disclosed only on an
>> as-needed basis. More details are in
>> 1004.pdf.
>> In a cryptocurrency use case, you wish perform a coin flip that is
>> deterministic and provably correct, but cannot be done by just anyone.
>> More details are in
>> u/nickolai/papers/gilad-algorand-eprint.pdf and possibly other
>> cryptocurrency papers.
>> Bryan Ford mentioned an additional usecase at the mic on Tuesday:
>> distributed password protection protocols
>> Many of these use case are already putting VRFs into production use (esp.
>> the CONIKS one).  You can see a list of the various implementations we have
>> found in the "implementation status" section of our draft.  One of the
>> reasons we think this spec is so important is that we found flaws in
>> several of the implementations that can be used to trivially break
>> uniqueness.  (See eg:
>> keytransparency/issues/567)
>> Thanks,
>> Sharon
>> On Fri, Jul 21, 2017 at 7:32 PM, Dan Brown <>
>> wrote:
>>> 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;
>>> *Cc: *; 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 [] *On Behalf Of *Sharon
>>> Goldberg
>>> *Sent:* Wednesday, July 12, 2017 5:42 AM
>>> *To:*
>>> *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
>>> --
>>> Sharon Goldberg
>>> Computer Science, Boston University
>> --
>> ---
>> Sharon Goldberg
>> Computer Science, Boston University
>> _______________________________________________
>> Cfrg mailing list

Sharon Goldberg
Computer Science, Boston University