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

[Sharon Goldberg <[e-mail]>]

It is "verifiable pseudorandomness". (Not true randomness.)
Think of a pseudorandom function (PRF) that comes with a public key that
allows anyone to check that the output of the PRF was computed correctly.

Sharon

On Sun, Jul 30, 2017 at 8:02 PM, Philip L <[e-mail]> wrote:

> Please excuse the spam. I thought for just a moment somehow that the
> function was verifiably random... like one of those hard problems (for
> decidability?).
>
> Just a random thought...
>
> On Thu, Jul 27, 2017 at 4:51 AM, Thomas Garcia <[e-mail]>
> wrote:
>
>>
>> Thanks for helping me clear those things up!
>>
>> Thomas G.
>>
>> On Wed, Jul 26, 2017 at 12:42 PM, Sharon Goldberg <
>> [e-mail]> wrote:
>>
>>> 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:
>>> http://www.cs.bu.edu/~goldbe/papers/VRF_ietf99_print.pdf
>>>
>>> 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.
>>>
>>> https://eprint.iacr.org/2017/099.pdf
>>>
>>> Thanks,
>>> Sharon
>>>
>>>
>>>
>>>> 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 (https://tools.ietf.org/html/d
>>>>> raft-goldbe-vrf-01#section-3).
>>>>>
>>>>> 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
>>>>> https://eprint.iacr.org/2017/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
>>>>> https://eprint.iacr.org/2014/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 https://people.csail.mit.ed
>>>>> 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: https://github.com/google/
>>>>> keytransparency/issues/567)
>>>>>
>>>>> Thanks,
>>>>> Sharon
>>>>>
>>>>> On Fri, Jul 21, 2017 at 7:32 PM, Dan Brown <[e-mail]>
>>>>> 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; [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
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> ---
>>>>> Sharon Goldberg
>>>>> Computer Science, Boston University
>>>>> http://www.cs.bu.edu/~goldbe
>>>>>
>>>>> _______________________________________________
>>>>> Cfrg mailing list
>>>>> [e-mail]
>>>>> https://www.irtf.org/mailman/listinfo/cfrg
>>>>>
>>>>>
>>>>
>>>
>>>
>>> --
>>> ---
>>> Sharon Goldberg
>>> Computer Science, Boston University
>>> http://www.cs.bu.edu/~goldbe
>>>
>>
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>


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