# 22.5.1 BLS Signatures

Alice wants to sign a document  In earlier chapters, we have seen how to do this with RSA and ElGamal signatures. The BLS method, due to Boneh, Lynn, and Schacham, uses pairings.

We use a supersingular elliptic curve  and point  as in Section 22.1. To set up the signature scheme, we’ll need a public hash function  that maps arbitrary length binary strings to multiples of  A little care is needed in defining  since no one should be able, given a binary string  to find  with  See Exercise 7.

To set up the system, Alice chooses, once and for all, a secret integer  and computes  which is made public.

Alice’s signature for the message  is  which is a point on 

To verify that  is a valid signed message, Bob checks



If this equation holds, Bob says that the signature is valid.

If Alice signs correctly,



so the verification equation holds.

Suppose Eve wants to forge Alice’s signature on a document  The values of  and  are then already determined, so the verification equation says that Eve needs to find  satisfying  a known quantity. Assumption (A) is Section 22.1 says that (we hope) this is computationally infeasible.

# 22.5.2 A Variation

The BLS signature scheme uses a hash function whose values are points on an elliptic curve. This might seem less natural than using a standard hash function with values that are binary strings (that is, numbers). The following method of Zhang, Safavi-Naini, and Susilo remedies this situation. Let  be a standard hash function such as SHA-3 or SHA-256 that maps binary strings of arbitrary length to binary strings of fixed length. Regard the output of  as an integer. Alice’s key is the same as in BLS, namely,  But the signature is computed as



where  is the modular multiplicative inverse of  mod  (where  is the order of  as in Section 22.1).

The verification equation for the signed message  is



Since  the left side of the verification equation equals the right side when Alice signs correctly. Again, assumption (A) from Section 22.1 says that it should be hard for Eve to forge Alice’s signature.

# 22.5.3 Identity-Based Signatures

When Alice uses one of the above methods or uses RSA or ElGamal signatures to sign a document, and Bob wants to verify the signature, he looks up Alice’s key on a web-page, for example, and uses it in the verification process. This means he must trust the web-page to be correct, not a fake one made by Eve. It would be preferable to use something closely associated with Alice such as her email address as the public key. This is of course the same problem that was solved in the previous section for encyprytion, and similar techniques work in the present situation.

The following method of Hess gives an identity-based signature scheme.

We use a supersingular elliptic curve  and point  as in Section 22.1. We need two public hash functions:

1.  maps arbitrary length binary strings to multiples of  A little care is needed in defining  since no one should be able, given a binary string  to find  with  See Exercise 7.

2.  maps binary strings of arbitrary length to binary strings of fixed length; for example,  can be a standard hash function such as SHA-3 or SHA-256.

To set up the system, we need a Trusted Authority. Let’s call him Arthur. Arthur does the following.

1. He chooses, once and for all, a secret integer  He computes  which is made public.

2. For each User, Arthur finds the user’s identification ID (written as a binary string) and computes



Recall that  is a point on  so  is  times this point.

3. Arthur uses a secure channel to send  to the user, who keeps it secret. Arthur does not need to store  so he discards it.

The system is now ready to operate, but first let’s review what is known:

Public: 

Secret:  (known only to Arthur),  (one for each User; it is known only by that User)

To sign  Alice does the following.

1. She chooses a random point  on 

2. She computes 

3. She computes 

4. She computes 

5. The signed message is 

If Bob receives a triple  where  is a point on  and  is a binary string, then he does the following.

1. He computes  which is a th root of unity.

2. He computes 

3. If  then Bob says the signature is valid.

Let’s suppose Alice signed correctly. Then, writing  for  we have



Also,



Therefore,



so the signature is declared valid.

Suppose Eve has a document  and she wants to forge Alice’s signature so that  is a valid signature. She cannot choose  arbitrarily since Bob is going to compute  and see whether  Therefore, if  is a good hash function, Eve’s best strategy is to choose a value  and compute  Since  is collision resistant and  this  should equal  But  is completely determined by Alice’s ID and  This means that in order to satisfy the verification equation, Eve must find  such that  equals a given quantity. Assumption (A) says this should be hard to do.