elliptic-curve: VRF traits

[tarcieri]

This issue proposes to add traits for Verifiable Random Functions (VRFs) to the elliptic-curve crate.

RFC9831 describes various curve-specific VRF algorithms, including a generic implementation for all prime order curves, and e.g. Elligator2 for "Edwards25519", i.e. the twisted Edwards form of Curve25519.

We can add a generic implementation to the primeorder crate, and potentially add support to curve25519-dalek as well, if it ever adopts the elliptic-curve crate for providing cross-curve abstractions (see also: dalek-cryptography/curve25519-dalek#492)

[omibo]

I would like to take on this task and would greatly appreciate it if you could assign it to me.

As a starting point, I will review RFC9381, as well as the elliptic-curve and primeorder crates, to gain a deeper understanding of the requirements.

[burdges]

Anonymized signatures would liekly be out of scope here, but..

I've done some mid-level traits for EC VRFs in https://github.com/w3f/ring-vrf/blob/master/dleq_vrf/src/traits.rs which work around input-output pairs.

I designed those traits for anonymized VRFs like ring VRFs, including what the ETH people call semaphore. As such, they're designed to be chained, from a secret key or a secret key plus zero knowledge continuiation to a ring openning, or from a public key or a ring commitment.

You cannot capture all anonymous VRF like constructions, but the important points:

• An auxiliary signed message beside the VRF input -- EC VRFs supports this, although afaik not standardized. RSA FDH and BLS cannot support this, but BLS should basically never be used as a VRF, unless you're deploying a whole threshold signing infrastructure, and even then other schemes work better. RSA FDH variants can have faster verifiers.
• Multiple input-output pairs in the same VRF signature.

Anonymized VRFs [almost] always need one or both of these features, or else replay attacks exist. A regular non-anonymous VRF rarely needs multiple input-output pairs, but the auxiliary signed message turns out useful more broadly.