# The BLS Signature Scheme — A short intro

*Outline*:

- What is a Signature Scheme?
- Some well-known signature schemes
- Diffie-Hellman Problem (DHP)
- Computational DHP vs Decisional DHP
- Gap Group
- BLS Signature Scheme

A digital signature scheme is essentially a mathematical setup to prove that a message has been authenticated by the sending party. The signature scheme ensures:

- Message is authenticated (by sender)
- Sender cannot deny sending the message (non-repudiation)
- Message is not tampered with (data integrity)

Diffie and Hellman conjectured the existence of a digital signature scheme in 1976 based on trapdoor one-way functions. (One-way functions have not been proven to exist to date.) Shortly after, the RSA encryption scheme was invented based upon the assumption that the factorization of semi-primes (N=p*q, where p, q are primes) is a difficult problem.

Soon after, many more encryption schemes were invented:

Some prominent encryption schemes in literature and the fundamental reasoning behind their formulation include:

- Boneh — Lynn — Shacham (BLS): Based on the existence of random oracles and the intractability of the computational Diffie-Hellman problem in a gap Diffie-Hellman group.
- ElGamal: Based on the hardness of the discrete logarithm problem.
- ECDSA: Based on the fact that given a point A on an elliptic curve and another point P = n*A, it is difficult to find n.
- Ring signature: Any non-empty subset of a group of n people can sign a message without the identity of any of the participants being leaked. It is a signature scheme built on other schemes.
- RSA: Factorization of numbers (semi-primes in particular) is hard.
- Schnorr Signature: Based on the hardness of the discrete logarithm problem.

With the broad understanding above, we now take a look at the Diffie-Hellman problem.

**Diffie-Hellman Problem (DHP)**

Given a multiplicative group *G** *and a generator ** g**,

**the Diffie-Hellman Problem (DHP) asks whether it is easy to find**

*g^xy*given

*g*,

*g^x*, and

*g^y*, where

*x*,

*y*are some randomly chosen integers. Solving the Diffie-Hellman problem (DHP) in many groups has been shown to be almost as hard as the discrete log problem (DLP).

**Computational DHP (CDHP) vs Decisional DHP (DDHP)**

At this stage, it is important to make a distinction between the computational DHP and the decisional DHP. The computational DHP involves finding *g^xy* from *g^x* and *g^y*, as described before, whereas the decisional DHP (DDHP) involves distinguishing *g^xy* from a random group element given *g*, *g^x*, *g^y*. It is trivial to see that the computational DHP is always as difficult as the decisional DHP, but it is unclear to see if one is strictly tougher in general.

**Gap Group**

A gap group is a group in which the computational DHP is difficult but the DDHP can be efficiently solved. One particular example is that of non-degenerate, efficiently computable, bilinear pairings. A pairing in cryptography is defined as follows:

We can see that the decisional DHP when a bilinear pairing is defined is easy because given *g^x*, *g^y*, *g^z*, where *z* = *x***y*, we can verify whether *g^z* is different from a random element in the group *G* as follows:

However, the computational DHP is conjectured to be intractable in this instance.

**BLS Signature Scheme**

Having given a primer to digital signature schemes and some basic background, the following are the components of the BLS signature scheme:

- Bilinear Pairing
*e( · , · )* - Elliptic Curve Group elements as signatures

Assumptions:

- Existence of random oracle
- Intractability of CDHP in a gap DH group

The scheme:

- Generate: Select a number
as your private key in the range [0, r-1]. The public key shared is*x**g^x* - Given the private key
and some message*x*the signature is given by*m,**(H(m))^x* - To verify that the signature is valid, we check that
given*e((H(m))^x,g) = e(H(m), g^x),**g^x, g*

Note that the above signature scheme works, because we have a bilinear pairing on a group and we cannot find the private key *x* given *g^x *and* g*.

In future posts, we will go deeper into the use of digital signature schemes in cryptocurrencies and blockchains.