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.
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.
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:
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.
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.
He chooses, once and for all, a secret integer He computes which is made public.
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.
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:
Secret: (known only to Arthur), (one for each User; it is known only by that User)
To sign Alice does the following.
She chooses a random point on
The signed message is
If Bob receives a triple where is a point on and is a binary string, then he does the following.
He computes which is a th root of unity.
If then Bob says the signature is valid.
Let’s suppose Alice signed correctly. Then, writing for we have
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.