BLS signatures were introduces in [BLS01] by the authors Boneh, Lynn and Shacham. In fact, the name used in their paper is GDH-signatures where GDH stands for Gap-Diffie-Hellman. This name describes a property of the underlying group which is assumed to hold for the signature scheme to be proved secure. Put simply, the security of BLS-scheme is based on the GDH assumption.
Gap Diffie Hellman
Consider a cyclic group $G_1=\langle g_1 \rangle$ of prime order $p$. We say that the adversary solves the Computational Diffie-Hellman (CDH) if on input $(g_1,g_1^a,g_1^b)$, it can output $g^{ab}$ (with non-negligible probability) for random $a,b \in Z_q^*$. Furthermore, upon receiving a tuple $(g_1,g_1^a,g_1^b,g_1^c)$, the adversary solves the so-called Decisional Diffie-Hellman (DDH) problem if it can correctly decide whether $c=ab$. The only known way to solve CDH is by computing the $log_{g_1}(g_1^a)=a$ (discrete log) and then do $(g_1^b)^a$. And we can solve the DDH problem easily with access to an algorithm solving CDH.
So a natural question is then; are there any groups where CDH is hard1 but DDH is easy?
This was the topic of [JN01], by Joux and Nguyen, who presented a family of groups where CDH (and DL) were hard but DDH was easy to compute and thereby separating CDH and DDH. In fact, [OP01] - Okamoto and Pointcheval had already identified the Gap-DH (GDH) among other (gap-problems) and showed that this tractable/intractable asymmetry can be used to build signature schemes with specific properties. So the main contribution of BLS was not so much the idea a signature scheme on top of GDH, but rather the fact that (using the right parameters) these signatures can be made extremely short.
co-GDH and Bilinear Maps
Before talking about BLS signatures we need to introduce bilinear maps. First, let’s define a few other groups $G_2=\langle g_2 \rangle$ and $G_T=\langle g_T \rangle$ to the mix. We call $G_1$ and $G_2$ source groups and $G_T$ the target group and we assume that $|G_1|=|G_2|=|G_3|$. The bilinear map is then defined as $e:G_1\times G_2 \rightarrow G_T$ with properties
- (Bilinearity) $\forall a,b\in \mathbb{Z},e(g_1^a,g_2^b)=e(g_1,g_2)^{ab}$
- (Non-degeneracy) $e(g_1,g_2)\neq 1$.
- (Computability) The mapping $e$ is efficiently computable.
And now that we work over both $G_1$ and $G_2$ we need to introduce natural extensions2 of DDH, CDH and GDH.
- Computational Co-Diffie-Hellman: Given $g_2,g_2^a$ and $g_1\in G_1$, compute $g_1^a\in G_1$.
- Decisional Co-Diffie Hellman: Given $(g_1,g_2^a,g_2,g_2^b)$ output yes if $a=b$.
Then, basically co-GDH groups are pairs of groups $(G_1,G_2)$ where computational co-DH is hard but decisional co-DH is easy.
The Weil Pairing as a DDH Oracle
You probably know where this is going by now :) In BLS signatures the Weil pairing is used as the bilinear map $e$ and it can be used to solve co-DDH efficiently (if $e$ is efficiently computable). Consider the tuple $(g_1,g_2^a,g_2,g_2^b)$. We just check if $e(g_1^a,g_2)=e(g_1,g_2^b)$ and that is our oracle for DDH. Notice that, to establish that this is a pair of gap groups $(G_1,G_2)$, we still have to make sure that the co-CDH problem is hard.
BLS Signatures
Now we can finally present the BLS signature scheme.
Key Generation A user picks $x\leftarrow \mathbb{Z}_p$ as private key and computes the public key $v\leftarrow g_2^x$.
Sign A user signs a message $M\in {0,1}^*$ by computing $h\leftarrow H(M)$ such that $h\in G_1$ and computes the signature $\sigma\leftarrow h^x\in G_1$.
Verify A verifier can use the public key $v$ of the user and verify that $\sigma$ is a valid signature on $M$ by checking $e(\sigma,g_2)=e(h,v)$.
Summary
We looked briefly at the history of BLS signatures. BLS is a signature scheme with security based on the co-Gap DH assumption. Due to the structure of the curves involved, the scheme can allow for very short signatures (~48 bytes). There are plenty of additional things to explore in the realm of BLS signature. Perhaps the most compelling feature is that the scheme is so aggregation-friendly. But that is a topic for another post.