High level API for BLS

[Shimuuar]

We need to create high level safe to use API for BLS signatures and their aggregation. It doesn't lend itself for typeclass-based API easily so it's probably better to write monomorphic one. Thing are made more difficult by fact that there're 3 (!) aggregation schemes with different tradeoffs.

Here is brief summary of scheme. We have two groups of prime order p: G1, G2 with generator g1 and g2 respectively; bilinear mapping e : (G1×G2) → GT (GT is group of prime order as well) and group generator; hash function H0 : {0,1}^* → G1

Basic signature scheme

1. Secret key: sk ← random from Z/p
2. Public key: pk = g2^sk
3. Sign: σ = H0(m)^sk : G1
4. Verify: e(σ,g2) = e(H0(m), pk)

Simple key aggregation

If we have set of triples (m[i], σ[i], pk[i]) we can generate aggregate signature and aggregate public key:

1. Aggregate public key: apk = Π pk[i]
2. Aggregate signature: σ = Π σ[i]
3. Verification: e(σ, g2) = e(H0(m[1], pk[1]) ... e(H0(m[n], pk[n])
4. Verification when all messages are same: e(σ, g2) = e(H(m), apk)

Note that aggregation scheme is susceptible to rogue key attack. Let consider following: Alice has public key pk1. Attack works as follows:

• Attacker registers public key pk2 = g2^α·pk1^{-1}, where α : Z/p is chosen by attacker.
• Attacker presents message m and its signature σ=H0(m)^α
• e(σ,g2) = e(H0(m)^α, g2) = e(H0(m), g2^α) = e(H0(m), pk1·pk2). Therefore is able to forge signature of Alice without Alice signing anything

There're two defenses against this attack:

1. Require proof of possession of secret key corresponding to public key. Note that attacker does not have secret key corresponding to pk2 = g2^α·pk1^{-1}!
2. Require that all messages are distinct. This could be achieved by prepending public key to message. However if we do this it's not possible to use verification (4)

[Shimuuar]

Rogue-key resistant aggregation

This is schema was created later and protects against rogue key attacks, but requires that each signer signs same message, key generation is done in same way, but signing is different. Let assume that we have set of signers with key pairs (pk[i], sk[i]). In addition we'll need hash function H1 : {0,1}^*→Z/p

1. a[i] = H1(pk[i], {pk[1] .. pk[n]})
2. Signing: σ[i] = H0(m)^{a[i]·sk[i]}
3. Signature aggregation: σ = Π σ[i]
4. Public key aggregation: apk = Π pk[i]^a[i]
5. Signature verification: e(σ,g2^{-1}) e(H0(m), apk) = 1

Note that it's possible to aggregate signature made using previous method (σ[i]=H0(m)^sk[i]). Using σ=Π σ[i]^a[i]. It also allows to aggregate signatures without known set of signers in advance. AFAIR this is how bls library works.

Downside of this schema is that it requires that everyone signs same message

[Shimuuar]

What all that means from API design PoV?

1. We have only one type of secret/public key (thanks god!)
2. We have two kinds of signatures: plain and one with prepended public key. One way to encode this is to have two signature type. Another is to encode it as type parameter of data type being signed...
3. We have 3 ways of aggregating signatures!