Chapter 2. Tutorial

Table of Contents

BLS signatures

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

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

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

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

BLS signatures

First we include pbc/pbc.h:

#include <pbc.h>

Next we initialize a pairing:

pairing_t pairing;
char param[1024];
size_t count = fread(param, 1, 1024, stdin);
if (!count) pbc_die("input error");
pairing_init_set_buf(pairing, param, count);

Later we give pairing parameters to our program on standard input. Any file in the param subdirectory will suffice, for example:

$ bls < param/a.param

We shall need several element_t variables to hold the system parameters, keys and other quantities. We declare them and initialize them,

element_t g, h;
element_t public_key, secret_key;
element_t sig;
element_t temp1, temp2;

element_init_G2(g, pairing);
element_init_G2(public_key, pairing);
element_init_G1(h, pairing);
element_init_G1(sig, pairing);
element_init_GT(temp1, pairing);
element_init_GT(temp2, pairing);
element_init_Zr(secret_key, pairing);

generate system parameters,


generate a private key,


and the corresponding public key.

element_pow_zn(public_key, g, secret_key);

When given a message to sign, we first compute its hash, using some standard hash algorithm. Many libraries can do this, and this operation does not involve pairings, so PBC does not provide functions for this step. For this example, and our message has already been hashed, possibly using another library.

Say the message hash is "ABCDEF" (a 48-bit hash). We map these bytes to an element h of G1,

element_from_hash(h, "ABCDEF", 6);

then sign it:

element_pow_zn(sig, h, secret_key);

To verify this signature, we compare the outputs of the pairing applied to the signature and system parameter, and the pairing applied to the message hash and public key. If the pairing outputs match then the signature is valid.

pairing_apply(temp1, sig, g, pairing);
pairing_apply(temp2, h, public_key, pairing);
if (!element_cmp(temp1, temp2)) {
    printf("signature verifies\n");
} else {
    printf("signature does not verify\n");