== Tutorial ==

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 sigma, Bob checks that
'e'('h','g'^'x'^) = 'e'(sigma, '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,

    element_random(g);

generate a private key,

    element_random(secret_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");
}
....

=== Import/export ===

To be useful, at some stage the signature must be converted
to bytes for storage or transmission:

    int n = pairing_length_in_bytes_compressed_G1(pairing);
    // Alternatively:
    // int n = element_length_in_bytes_compressed(sig);
    unsigned char *data = malloc(n);
    element_to_bytes_compressed(data, sig);

On the other end, the signature must be decompressed:

    element_from_bytes_compressed(sig, data);

Eliding +_compressed+ in the above code
will also work but the buffer 'data' will be roughly twice as large.

We can save more space by using the 'x'-coordinate of the signature only

    int n = pairing_length_in_bytes_x_only_G1(pairing);
    // Alternative:
    //   int n = element_length_in_bytes_x_only(sig);
    unsigned char *data = malloc(n);
    element_to_bytes_compressed(data, sig);

but then there is a complication during verification since two different
points have the same 'x'-coordinate. One way to solve this problem is to
guess one point and try to verify. If that fails, we try the other.
It can be shown that the pairing outputs of the two points are inverses
of each other, avoiding the need to compute a pairing the second time.
(In fact, there are even better ways to handle this.)
....
int n = pairing_length_in_bytes_x_only_G1(pairing);
//int n = element_length_in_bytes_x_only(sig);
unsigned char *data = malloc(n);

element_to_bytes_x_only(data, sig);

element_from_bytes_x_only(sig, data)

pairing_apply(temp1, sig, g, pairing);
pairing_apply(temp2, h, public_key, pairing);

if (!element_cmp(temp1, temp2)) {
    printf("signature verifies on first guess\n");
} else {
    element_invert(temp1, temp1);
    if (!element_cmp(temp1, temp2)) {
	printf("signature verifies on second guess\n");
    } else {
	printf("signature does not verify\n");
    }
}
....