BLS Signature

Open Table of contents

What it is
How it works
Why it works
References

What it is

The BLS Signature scheme is a digital signature algorithm that uses Elliptic Curve Pairings as a building block to generate very small signatures for arbitrary messages.

BLS Signatures furthermore exhibit desirable properties such as the ability to aggregate signatures to implement collaborative signing, no dependency on randomness during signing and its potential to be used in Zero-Knowledge Proof constructions.

How it works

As a prerequisite, it’s very useful to have some familiarity with Elliptic Curve Pairings before moving on to study BLS Signatures.

Recall that an Elliptic Curve Pairing maps two Elliptic Curve points from two Elliptic Curves to an element in another group:

e: E_1 \times E_2 \rightarrow \mathbb{F}

Here, $e$ is the pairing, $E_1$ and $E_2$ are the Elliptic Curves and $\mathbb{F}$ is a finite field.

Also remember that an Elliptic Curve Pairing comes with specific properties called bilinear mappings, two of which are important for the rest of this post:

\begin{aligned} e(P + Q, R) &= e(P, R)e(Q, R) \\ e(aP, bQ) &= e(P, Q)^{ab} \end{aligned}

where $P$ , $Q$ and $R$ are Elliptic Curve points and $a \in \mathbb{Z}$ , $b \in \mathbb{Z}$ .

In our example we have two participants, Alice and Bob. Alice will sign a message which in turn will be verified by Bob.

Furthermore we’ll be working with the Elliptic Curve $E$ that is of order $q$ and has a generator $G$ . The Elliptic Curve Pairing on such curve will be called $e$ . All calculations are done $\bmod\ q$ if not stated otherwise.

We also assume that $H$ is a cryptographic hash function that maps a message $m$ to a uniformly random looking value.

As a first step, Alice generates here private key $x$ by sampling a random value from $\mathbb{Z}_q$ :

x \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

She then generates here public key $X$ by multiplying her private key with the generator $G$ :

X = xG

Once done, Alice hashes the message $m$ which results in a value that can be interpreted a point $p$ on the Elliptic Curve $E$ :

p = H(m)

To generate a signature for the message $m$ , Alice multiplies her private key $x$ by the value that the hash of the message resulted in:

\sigma = xH(m)

Alice then sends the signature $\sigma$ alongside her public key $X$ to Bob for verification.

Bob verifies the signature $\sigma$ on the message $m$ by checking if:

e(H(m), X) \overset{?}{=} e(\sigma, G)

BLS Signature

Why it works

The first thing to note is that the result returned by the hash function $H$ can be interpreted as a point on the Elliptic Curve $E$ . The hash value can therefore be used in an Elliptic Curve Pairing.

Using the aforementioned bilinear mapping, we can see that:

\begin{aligned} e(H(m), X) &\overset{?}{=} e(\sigma, G) \\ &= e(xH(m), G) \\ &= e(H(m), G)^{x} \\ &= e(H(m), xG) \\ &= e(H(m), X) \end{aligned}

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.