Alice wants to sign a document $m\text{.}$ 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 $E_0$ and point $P_0\text{,}$ 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 $P_0\text{.}$ A little care is needed in defining $H\text{,}$ since no one should be able, given a binary string $b\text{,}$ to find $k$ with $H(b)=k{P}_0\text{.}$ See Exercise 7.

To set up the system, Alice chooses, once and for all, a secret integer $a$ and computes $K_{\text{Alice}}=a{P}_0\text{,}$ which is made public.

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

To verify that $(m\text{,}S)$ 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 $m\text{.}$ The values of $H(m)\text{,}{K}_{\text{Alice}}\text{,}$ and $P_0$ are then already determined, so the verification equation says that Eve needs to find $S$ satisfying $\tilde{e}(S\text{,}{P}_0)=$ 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 $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, $K_{\text{Alice}}=a{P}_0\text{.}$ But the signature is computed as

where $(H(m)+a{)}^{-1}$ is the modular multiplicative inverse of $(H(m)+a)$ mod $q$ (where $q$ is the order of $P_0\text{,}$ as in Section 22.1).

The verification equation for the signed message $(m\text{,}S)$ is

Since $H(m)P_0+K_{\text{Alice}}=(H(m)+a)P_0\text{,}$ 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 $E$ and point $P_0$ as in Section 22.1. We need two public hash functions:

1. $H_1$ maps arbitrary length binary strings to multiples of $P_0\text{.}$ A little care is needed in defining $H_1\text{,}$ since no one should be able, given a binary string $b\text{,}$ to find $k$ with $H_1(b)=k{P}_0\text{.}$ See Exercise 7.

2. $H_2$ maps binary strings of arbitrary length to binary strings of fixed length; for example, $H_2$ 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\text{.}$ He computes $P_1=s{P}_0\text{,}$ which is made public.

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

   $$D_{\text{User}}=s{H}_1(ID)\text{.}$$

   Recall that $H_1(ID)$ is a point on $E\text{,}$ so $D_{\text{ User}}$ is $s$ times this point.

3. Arthur uses a secure channel to send $D_{\text{ User}}$ to the user, who keeps it secret. Arthur does not need to store $D_{\text{ User}}\text{,}$ so he discards it.

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

Public: $E\text{,}p\text{,}{P}_0\text{,}{P}_1\text{,}{H}_1\text{,}{H}_2$

Secret: $s$ (known only to Arthur), $D_{\text{ User}}$ (one for each User; it is known only by that User)

To sign $m\text{,}$ Alice does the following.

1. She chooses a random point $P\ne \infty$ on $E\text{.}$

2. She computes $r=\tilde{e}(P\text{,}{P}_0)\text{.}$

3. She computes $h=H_2(m||r)\text{.}$

4. She computes $U=h{D}_{\text{Alice}}+P\text{.}$

5. The signed message is $(m\text{,}U\text{,}h)\text{.}$

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

1. He computes $v_1=\tilde{e}(H_1(I{D}_{\text{Alice}})\text{,}{P}_1{)}^{-h}\text{,}$ which is a $q$th root of unity.

2. He computes $v_2=v_1\cdot \tilde{e}(U\text{,}{P}_0)\text{.}$

3. If $h=H_2(m||v_2)\text{,}$ then Bob says the signature is valid.

Let’s suppose Alice signed correctly. Then, writing $H_1$ for $H_1(I{D}_{\text{Alice}})\text{,}$ we have

Also,

Therefore,

so the signature is declared valid.

Suppose Eve has a document $m$ and she wants to forge Alice’s signature so that $(m\text{,}U\text{,}h)$ is a valid signature. She cannot choose $h$ arbitrarily since Bob is going to compute $v_2$ and see whether $h=H_2(m||v_2)\text{.}$ Therefore, if $H_2$ is a good hash function, Eve’s best strategy is to choose a value $v_2^{{}^{\prime }}$ and compute $h=H(m||v_2^{{}^{\prime }})\text{.}$ Since $H_2$ is collision resistant and $H_2(m||v_2^{{}^{\prime }})=h=H_2(m||v_2)\text{,}$ this ${v_2}^{\prime }$ should equal $v_2=v_1\cdot \tilde{e}(U\text{,}{P}_0)\text{.}$ But $v_1$ is completely determined by Alice’s ID and $h\text{.}$ This means that in order to satisfy the verification equation, Eve must find $U$ such that $\tilde{e}(U\text{,}{P}_0)$ equals a given quantity. Assumption (A) says this should be hard to do.