Outline:

1. What is a Signature Scheme?
2. Some well-known signature schemes
3. Diffie-Hellman Problem (DHP)
4. Computational DHP vs Decisional DHP
5. Gap Group
6. 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 Gand 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 x as your private key in the range [0, r-1]. The public key shared is g^x
• Given the private key x and some message m, the signature is given by (H(m))^x
• To verify that the signature is valid, we check that e((H(m))^x,g) = e(H(m), g^x), given 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.