This chapter walks through how one might implement the Boneh-Lynn-Shacham (BLS) signature scheme using the PBC library. It is based on the file example/bls.c.

We have three groups G1, G2, GT of prime order r, and a bilinear map e that takes an element from G1 and an element from G2, and outputs an element of GT. We publish these along with the system parameter g, which is a randomly chosen element of G2.

Alice wishes to sign a message. She generates her public and private keys as follows. Her private key is a random element x of Zr, and her corresponding public key is g^x.

To sign a message, Alice hashes the message to some element h of G1, and then outputs the signature h^x.

To verify a signature σ, Bob checks that e(h,g^x) = e(σ, g).

We now translate the above to C code using the PBC library.