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

[Christopher Peikert <[e-mail]>]

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.)

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.

Sincerely yours in cryptography,
Chris