Subject: Re: [CFRG] draft-irtf-cfrg-vrf-09 comments and clarifications

From: Leonid Reyzin <[email-masked]>
Date: Fri, 21 Jan 2022 23:06:20 -0500

Dear Chris and Jiayu and the rest of CFRG,

Thank you so much for the very thoughtful comments. They have now been
addressed. Details below.

I will respond to the remaining last call comments shortly.

 Leo

Hello, Jiayu Xu and I have two additional remarks about the current ECVRF
> draft, specifically Sections 5.4.1 and 5.6.
>
> Section 5.4.1: hash-to-curve should perhaps be generally described as
> outputting a *finite* (i.e., non-identity) EC point H in G. The three
> instantiations in Sections 5.4.1.1-3 are described this way, but the
> general operation is not.
>
> Non-identity H is used in the published proof of uniqueness (both trusted
> and full): if H is identity, then discrete logs with base H are not well
> defined and the proof doesn't make sense as written.
>
> However, it interestingly turns out that non-identity H is not a
> *necessary* requirement for uniqueness; the existing proof easily extends
> to deal with this case. Essentially, if a cheating prover attempts to
> provide some Gamma for which cofactor*Gamma is (incorrectly) not identity,
> then there is only one possible value of the hash-challenge c for which the
> prover can succeed. This is exactly the same situation as when a prover
> attempts to provide an incorrect Gamma when H is not identity.
>
> The published proofs of collision resistance (trusted and full) and
> pseudorandomness also do not require H to be non-identity.
>
> So, there is an option to drop this non-identity requirement, or at least
> provide further clarity about it. (Perhaps it will be needed for some
> future security property we have yet to contemplate.)
>
>
Indeed, this requirement is not needed, and I will at some point soon
update the proof on eprint. I have removed the word "finite" from the
descriptions in 5.4.1 because it is not relevant anymore. See [this commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/46d449caa0bbd8e0f73a0133e0cb8e91724bdb9d
)

> Section 5.6 says:
>
>    In order to obtain "full uniqueness" and "full collision resistance"
> (which provide protection against a malicious VRF public key), the Verifier
> MUST perform the following additional validation procedure upon receipt of
> the public VRF key. [The procedure simply rejects any public key that
> belongs to the small-order "torsion" subgroup.]
>
> This text is formally true but somewhat confusing. The validation is
> needed only for "full collision resistance," not "full uniqueness."
> (Details follow.) So, we suggest removing the mention of "full uniqueness"
> from the above.
>
> For collision resistance, there is an easy attack if the public key is
> invalid.
>
> However, full uniqueness holds as long as the public key is a valid
> elliptic curve point --- even if it is in the torsion subgroup, or is even
> the identity element. This is essentially because a valid proof ensures that
>
>    cofactor*Gamma = dlog_B(cofactor*pubkey) * H .
>
> (This holds even if the dlog on the right-hand side is zero.) So the LHS,
> and hence the function output, is uniquely defined.
>

This required a bit of additional careful rewording because full uniqueness
still requires that the public be a valid curve point. Done [in this
commit](
https://github.com/cfrg/draft-irtf-cfrg-vrf/commit/6bc6c2f09da101c878ad247fcda75815f6e0024e
)