Subject: [Cfrg] new version of draft-irtf-cfrg-vrf

From: Leonid Reyzin <[email-masked]>
Date: Fri, 14 Sep 2018 14:32:46 -0400

Dear CFRG,

The new version of Verifiable Random Functions draft (draft-irtf-cfrg-vrf)
incorporates feedback received following our presentation at IETF 102. It
resolves all outstanding issues of which we are aware. It is available
here: https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/

We have built a reference implementation and have included test vectors
(appendix A) produced by this implementation for all Elliptic Curve VRF
ciphersuites.

Additional feedback would be most welcome. In particular, we'd like
opinions on whether to keep all four ECVRF ciphersuites (two curves with
two options each for hash-to-curve). So far, we have received one vote for
keeping all four and one vote for not keeping try-and-increment version of
hash-to-curve.

More details on the changes are below.

Substantive changes:

- Clarified Elligator (Section 5.4.1.2) hash-to-curve algorithm, and
slightly changed it to match draft-irtf-cfrg-hash-to-curve

- Added a hash-to-curve algorithm called "Simple SWU" (Section 5.4.1.3) for
curve P256, which matches draft-irtf-cfrg-hash-to-curve

- Switched from big-endian to little-endian encoding for scalars for curve
Ed25519 (to match RFC 8032, EdDSA); replaced 4-byte counter with 1-byte
counter in try-and-increment (Section 5.4.1.1) to avoid endian issues

- Separated field element length from elliptic curve scalar length, because
these could differ by a byte; also separated output length.

- ECVRF_validate_key (Section 5.6.1) now has an alternative faster
implementation for Ed25519

- RSA-based VRF (Section 4) now has a similar domain separation to EC-based
VRF

Editorial changes:

- Switched to additive notation (including "scalar multiplication" instead
of exponentiation) for elliptic curves.

- Clarified a lot of notation and fixed a bunch of typos

- Explained why ECVRF_validate_key (Section 5.6.1) works and why additional
validation is not necessary

- Clarified the random-oracle property of the ECVRF (Section 3.4)

- Clarified that proof_to_hash should not be called on unverified proofs

Below we respond to the few remaining questions and comments are not
addressed directly in the new draft:

- Tony Arcieri suggested considering Ristretto as a cofactorless variant of
the curve Ed25519 for the future. We agree that it is worth considering in
the future. However, at the current stage, the Ristretto project is not
mature enough. The websites describing various aspects of Ristretto have
lots of statements like "XXX write up details" and "This section should
have explicit formulas for Ristretto"; there are no clear formulas or pros
and cons listed.  We believe that if Ristretto matures and its advantages
become clear, it can be added as a ciphersuite.

- Stanislav Smyshlyaev and Liliya Akhmetzyanova suggested changing nonce
generation for Ed25519 ciphersuites to use SHA-256 and/or HMAC_DRBG.
However, SHA-512 is commonly used with EdDSA and is necessary for
generating the secret scalar in our ECVRF. We did not want to add SHA-256
to the set of required primitives for the Ed25519 ciphersuites, this
increasing the required codebase. The nonce generation we have is provably
secure in the random oracle model and is used for the exact same purpose
(and with the same proof) in EdDSA. We have seen no evidence that any other
nonce generation procedure will improve security.

- We decided not to add "context" as a signature option (something RFC 8032
EdDSA has). There was only suggestion that we should, and no use case for
when it's needed. So we don't know who would want or need it, and it would
complicate the draft. If needed, it can be easily added as a ciphersuite
(our domain separation makes it easy to securely add new ciphersuites).

-  Marek Jankowski asks "Can it be that the prover or verifier (or both)
need to verify that the points they are dealing with are indeed of order
q?" The answer is "no". The VRF was deliberately designed to be secure even
if no one does this verification, and the security proof carefully handles
this case (Signal's VXEdDSA has a similar design with the same goal). We
clarified this in section 5.6.1.

Thanks to everyone who provided feedback and suggestions, including Sergey
Gorbunov, Derek Ting-Haye Leung, Adam Suhl, Chris Wood, Sam Scott,  Nick
Sullivan, Annie Yousar, Stanislav Smyshlyaev,  Liliya Akhmetzyanova, Tony
Arcieri, and Marek Jankowski.

Sincerely,

Leo, Sharon, Jan, Dimitris