Implement a threshold signature scheme.

[afck]

The common coin is based on threshold signatures: https://eprint.iacr.org/2002/118.pdf (section 4.2)

[afck]

Here's my reading of the algorithm, translated to (Rust pseudocode and) the context of potentially asymmetric pairing functions fn pair(G1, G2) -> GT instead of GDH groups: The three groups are assumed to be of prime order q, all written additively, and the function is nontrivial and bilinear: pair(a * h1, b * h2) = a * b * pair(h1, h2) for all integers modulo q a: Zq and b: Zq, and group elements h1: G1 and h2: G2. Let g1: G1 and g2: G2 be fixed generators. It must be infeasible to compute a h2dh: G2 for given h1 and h2 such that pair(h1, h2) == pair(g1, h2dh) — the assumption corresponding to the hardness of the computational Diffie-Hellman problem, implying that in particular the discrete logarithm problem is hard in G1 and G2. We also assume there's a hash function fn hash(&[u8]) -> G2. All of this information is public.

Simple signature scheme

To generate a key pair, I pick a random sk: Zq, and publish pk: G1 = sk * g1. (sk is now the discrete log of pk — remember we're writing the groups additively —, so you can't compute it.)

To sign a message msg: &[u8], I compute: sig = sk * hash(msg).

To verify my signature, you check that pair(pk, hash(msg)) == pair(g1, sig). If I didn't cheat, you will find that is true because:

let x = pair(pk, hash(msg));
assert_eq!(x, pair(sk * g1, hash(msg))); // Definition of `pk`.
assert_eq!(x, pair(g1, sk * hash(msg)); // Bilinearity of `pair`.
assert_eq!(x, pair(g1, sig)); // Definition of `sig`.

Threshold signature scheme

Now we want any t + 1 out of N parties to be able to sign a message, so none of us must know the actual secret key sk[0]. Instead, a trusted dealer (see below) chooses a polynomial sk of degree t, publishes each pk[i] = sk[i] * g1 (i.e. pk[0] is the public key matching the secret key sk[0]), and gives the secret share sk[i] to party i for i in 1..=N (but not for 0).

A polynomial of degree t is determined by any t + 1 of its points, so any t + 1 parties could now reconstruct the secret key sk[0]. In fact for any set of size t + 1, sk[0] depends linearly on the sk[i]. The coefficients in that linear map are the Lagrange coefficients lc(&set, i):

sk[0] == set.iter().map(|&i| lc(&set, i) * sk[i]).sum()

Of course we never actually compute sk[0] in that way, and never give away our sk[i]! Instead:

To sign a message msg: &[u8], party i computes: sig[i] = sk[i] * hash(msg). If a set of size t + 1 has signed, we can compute the correct sig[0] = sk[0] * hash(msg) without any one of us knowing sk[0]:

sig[0] == set.iter().map(|&i| lc(&set, i) * sig[i]).sum()

To verify our signature, you check that pair(pk[0], hash(msg)) == pair(g1, sig[0]). Again, this works because:

let x = pair(pk[0], hash(msg));
assert_eq!(x, pair(sk[0] * g1, hash(msg)); // Definition of `pk[0]`.
assert_eq!(x, pair(g1, sk[0] * hash(msg)); // Bilinearity.
// Lagrange interpolation of `sk`:
assert_eq!(x, pair(g1, set.iter().map(|&i| lc(&set, i) * sk[i]).sum() * hash(msg));
// Pull `hash(msg)` into the sum:
assert_eq!(x, pair(g1, set.iter().map(|&i| lc(&set, i) * sk[i] * hash(msg)).sum());
// Definition of `sig[i]`:
assert_eq!(x, pair(g1, set.iter().map(|&i| lc(&set, i) * sig[i]).sum());
// Lagrange interpolation of `sig`:
assert_eq!(x, pair(g1, sig[0]));

Distributed key generation

TBD

There are ways to create the secret keys without anyone ever knowing sk[0], i.e. without a trusted dealer, in a distributed fashion: https://eprint.iacr.org/2012/377.pdf