22.5 Signatures – Introduction to Cryptography with Coding Theory, 3rd Edition

22.5 Signatures

22.5.1 BLS Signatures

Alice wants to sign a document m. 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 E0 and point P0,  as in Section 22.1. To set up the signature scheme, we’ll need a public hash function H that maps arbitrary length binary strings to multiples of P0. A little care is needed in defining H,  since no one should be able, given a binary string b,  to find k with H(b)=kP0. See Exercise 7.

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

Alice’s signature for the message m is S=aH(m),  which is a point on E.

To verify that (m, S) is a valid signed message, Bob checks

e˜(S, P0)=?e˜(H(m), KAlice).

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

If Alice signs correctly,

e˜(S, P0)=e˜(aH(m), P0)=e˜(H(m), P0)a=e˜(H(m), aP0)=e˜(H(m), KAlice), 

so the verification equation holds.

Suppose Eve wants to forge Alice’s signature on a document m. The values of H(m), KAlice,  and P0 are then already determined, so the verification equation says that Eve needs to find S satisfying e˜(S, P0)= 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 H 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 H as an integer. Alice’s key is the same as in BLS, namely, KAlice=aP0. But the signature is computed as

S=(H(m)+a)1P0, 

where (H(m)+a)1 is the modular multiplicative inverse of (H(m)+a) mod q (where q is the order of P0,  as in Section 22.1).

The verification equation for the signed message (m, S) is

e˜(H(m)P0+KAlice, S)=?e˜(P0, P0).

Since H(m)P0+KAlice=(H(m)+a)P0,  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 E and point P0 as in Section 22.1. We need two public hash functions:

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

  2. H2 maps binary strings of arbitrary length to binary strings of fixed length; for example, H2 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 s. He computes P1=sP0,  which is made public.

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

    DUser=sH1(ID).

    Recall that H1(ID) is a point on E,  so D User is s times this point.

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

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

Public: E, p, P0, P1, H1, H2

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

To sign m,  Alice does the following.

  1. She chooses a random point P on E.

  2. She computes r=e˜(P, P0).

  3. She computes h=H2(m||r).

  4. She computes U=hDAlice+P.

  5. The signed message is (m, U, h).

If Bob receives a triple (m, U, h),  where U is a point on E and h is a binary string, then he does the following.

  1. He computes v1=e˜(H1(IDAlice), P1)h,  which is a qth root of unity.

  2. He computes v2=v1e˜(U, P0).

  3. If h=H2(m||v2),  then Bob says the signature is valid.

Let’s suppose Alice signed correctly. Then, writing H1 for H1(IDAlice),  we have

v1=e˜(H1, P1)h=e˜(H1, P0)hs=e˜(sH1, P0)h=e˜(DAlice, P0)h=e˜(hDAlice, P0).

Also,

v2=v1e˜(U, P0)=e˜(hDAlice, P0)e˜(U, P0)=e˜(hDAlice+U, P0)=e˜(P, P0)=r.

Therefore,

H2(m||v2)=H2(m||r)=h, 

so the signature is declared valid.

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