Introduction to Cryptography with Coding Theory, 3rd Edition

22.5 Signatures

22.5.1 BLS Signatures

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 ...