Choose a cryptographic scheme

[Geal]

We have 4 different methods we can use:

• using pairings
• using verifiable random functions (we actually have 2 versions of this one, with different size and speed)
• using a kind of PKI with a final challenge response
• using aggregated gamma signatures

We have to choose one, depending on a few criterion:

• the most important is the security audit: we need to have a proper audit of biscuit's design. If one of the crypto designs is flawed and cannot be fixed, we will remove it from the list
• performance: the overhead of verifying a token should be small enough (signing should not be too slow, but it's not the limiting factor here)
• size: the token should not grow too much, so the crypto design should not have too much size overhead
• availability of good implementations or base libraries in various languages (mainly Rust and Java for now)

While the pairings solution is interesting, it is quite slow (cf the benchmarks results at https://github.com/CleverCloud/biscuit/tree/master/code#benchmarks-summary ). Also, there's no guarantee of finding high quality crypto libraries to use in various languages. So I think we'll eliminate right away.

The other solutions are fast enough, and based on the Ristretto group. There's a good implementation in Rust, curve25519-dalek, and a new one in Java, curve25519-elisabeth. Using this group reduces the risk of implementation errors.

The challenge token solution makes fast and small tokens, but its behaviour has an annoying tradeoff: when we want to verify the token, an additional operation must be performed, that prevents further attenuation. This might not be what we want for the token.

The gamma signatures solution produces short signatures and is faster than ost other schemes

[burdges]

I implemented a VRF using Ristretto in https://github.com/w3f/schnorrkel/blob/master/src/vrf.rs for use in Polkadot.

[Geal]

@burdges cool! curve25519-dalek is nice to use, right? :)
Does your implementation support signature aggregation?

[burdges]

Yes. I quite like the dalek ecosystem. :)

Afaik, there is no third-party aggregation per se without pairings, but schnorrkel's VRF permits signers to produce a single proof of multiple VRF outputs' correctness. We might use this to permit block producers to produce compact proofs of when they did an did not win blocks. This batching is implemented in the vrfs_merge* methods and uses the same as technique as used by CloudFlare's PrivacyPass: https://blog.cloudflare.com/privacy-pass-the-math/#dleqproofs

We also support batch verification similar to Schnorr/Ed25519 batch verification, although it should be further optimized into only having one multi-scalar exponentiation equation, instead of two.

Right now, it does not do verifiable shuffles, multi-secret same-signer VRFs, or multi-party VRFs, but..