hexresearch / hexresearch/hschain

High level API for BLS

Open
#525 2 comments 0 reactions 0 assignees View on GitHub
cryptography
Dominant language
C
Stars
4
Forks
0
PR merge metrics
No merged PRs in 30d

Description

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)

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.