BBS Signatures Using Weil Pairings

Vasily Suvorov (https://www.linkedin.com/in/vsuvorov/) suggested I write about BBS signatures in Elliptic Curve Cryptography for Developers. Since it’s too late for that, I’m writing it up here and putting an example code on GitHub.

The paper “Revisiting BBS Signatures” by Stefano Tessaro and Chenzhi Zhu describes both the original BBS form and BBS+ form of multiple document signatures. They go to a lot of trouble to prove that the original form is in fact secure.

I’m going to describe their math in an expanded method here rather than the compressed academic terms of the paper so the code found on GitHub (https://github.com/drmike8888/More-Pairing-examples) will be easier to follow.

The Math

The first equation I’ll introduce is the public key:

The private key is a secret known only to one user. The public key is created as a point on an extension field of an elliptic curve using the base point G_2. For more details on how that works, dive into Elliptic Curve Cryptography for Developers ( http://mng.bz/D9NA) - specifically chapter 13.

The signing process requires a hash operation on each message as well as the use of a set of points. The following diagram is a pictorial representation of the process:

Each message can be a different length. The hash process is modulo the order of the elliptic curve pairing base points. I refer to this number as “r”, but you’ll find it as “p” or “q” or something else in different papers on elliptic curve pairings.

It’s the large prime factor that determines the security of the elliptic curve. The points H_1, H_2, … H_l are on the base curve. These points are common to all signatures that use the BBS signing process.

The paper mentions that the set of points H_i can be created rather than stored or transmitted. I chose to use a hash function that converts a block of bytes to a point. The block of bytes is based on the index number, so any number of messages can be signed.

It just has to be the same number each time a signature is verified. The block size is 8192 bytes which is 2048 longs. The equation is

The end result is that the number i is duplicated 2048 times, then hashed to the order of base point G_1 (which is r), then multiplied with the point G_1. This is easy to duplicate and fast to compute so none of the points H_i need to be saved.

In terms of an equation, the value C is computed using

Note that the point G_1, which is the base point, is added in as well. This ensures that C never goes to zero no matter what the result of the sum of points is.

The signature is performed using a random number e and the private key x. The random number e should be chosen using a hardware generator and should be different for every signature. The equation for the signature is

This figure describes the equation in a graphical form:

The private key and random value are combined, then inverted modulo the order of the points G_1 and G_2 which is r. This is important - it is NOT modulo the order of the field of the base curve. When my code didn’t work the first time, I found that out the hard way.

The full signature is (A, e). The private key can only be known by one person; the public key is known by everyone. The random number e is now public, so combined with the public key, it is possible to verify the signature. The following image shows how the verification is done

The verification includes computing the value of C again because it is not available. Only the messages are available, so the process of creating the value C requires repeating all the steps shown in the first figure.

Note that G_1 is on the base curve, and G_2 is on the extension field curve. The verifier has access to the public key, the random value e, and the point G_2. So they can compute the Left side value as well as the value C.

If the Weil pairing of A with the Left side value matches the Weil pairing of C with G_2, the signature verifies.

Mathematically, we want to check:

Expanding the left side of the equation gives

The magic of elliptic curve pairings shows up in this last step. The multiplication of the inverse of (x+e) with the value C is removed by the multiplication of (x+e) with the base point G_2. Nobody knows the value of x except for one person, and nobody needs to know.

If the hash of all the messages is the same in both cases, the signature will be verified. If any one of the messages is different, the signature will fail.

The “Revisiting BBS Signatures” paper goes through a lot of trouble to prove this is secure. From a real perspective, dealing with side-channel attacks and human psychology is probably a more important security problem.

The Code

Here’s the routine that computes the H_i(i) value. It uses the subroutine hash0() described in Elliptic Curve Cryptography for Developers from Chapter 18. Because the index i can start at 0, I add 1 to the index i to make sure I don’t hash 0 as an input. The output H is a point on an elliptic curve.

/* create a point based on value i */

void msgpoint(POINT *H, long i, SIG_SYSTEM sig)
{
  unsigned char *buf;
  long j, *bfptr;

  buf = (unsigned char*)malloc(sizeof(long)*2048);
  for(j=0; j<2048; j++)
  {
    bfptr = (long*)(&buf[4*j]);
    *bfptr = i + 1;
  }
  hash0(H, sig, buf, 8192);
  free(buf);
}

This chunk of code computes the vector of points m_j H_j shown in the first figure. I called the vector Cgrp. The routine hash1() is also from Chapter 18, and it outputs a value modulo the order of the base point.

/* create H[j] vector of points for each message j 
   and compute message signature with point. */
  
  Hvec = (POINT*)malloc(sizeof(POINT)*NUMESG);
  Cgrp = (POINT*)malloc(sizeof(POINT)*NUMESG);
  for(j=0; j<NUMESG; j++)
  {
    point_init(&Hvec[j]);
    msgpoint(&Hvec[j], j, sig);   // create H_j point
    point_init(&Cgrp[j]);
    mpz_init(msghsh[j]);
   // hash of message j
    hash1(msghsh[j], (unsigned char*)(&msg[j*128]), 256, sig.tor); 
    elptic_mul(&Cgrp[j], Hvec[j], msghsh[j], sig.E); // compute m_j*H_j
  }

The following three blocks 1) compute the value C (called Csum here) from the first figure, 2) compute the value A from the second figure, and 3) print out the signature values along with the public key value.

I cheated with the random number e - it is taken modulo the field, not modulo the order of the base point. For a demo, it doesn’t matter - but for real code, it does. Don’t copy this!

/* compute C, the combination of all signature points and G_1 */

  point_init(&Csum);
  point_copy(&Csum, sig.G1);
  for(j=0; j<NUMESG; j++)
    elptic_sum(&Csum, Csum, Cgrp[j], sig.E);

/* compute aggregate signature of all documents.
   access to a hardware random number generator 
   is a better choice than this example. */

  mpz_inits(e, xe, ex, NULL);
  mrand(e);              // technically wrong modulus - don't do this for real
  mod_add(xe, e, sk[0], sig.tor);
  mpz_invert(ex, xe, sig.tor);
  point_init(&A);
  elptic_mul(&A, Csum, ex, sig.E);

/* Output final signature (A, e)  */
  
  gmp_printf("Signature random value is %Zd\n", e);
  point_printf("Signature point: ", A);
  printf("\n");
  poly_point_printf("public key:\n", PK[0]);

Normally, the verification process is done on a different computer at a different time than the original signature. The value of C has to be recomputed along with all the H_i. That just repeats the first two blocks of code above. The next block shows how the verification works.

The routine tog2() converts a point on the base curve to a point on the extension curve. This is just a change in representation because the point does not change, just that it becomes a value on a polynomial field extension.

If the computation of the two Weil pairings match, the signature verifies. If they don’t match - which is what happened the first two times I tried this example - the signature fails. The two errors can be seen in the previous code block. The statements mod_add() and mpz_invert() use the value r as the modulus.

I had madd() and minv() which use the field prime as the modulus, and instead of seeing the obvious the first time, it took me two times. Oh well, it works now!

/* compute verification of signature */

  poly_init(&wa);
  poly_init(&wc);            // create check results
  poly_point_init(&A2);
  poly_point_init(&C2);      // space for G2 versions of G1 points
  tog2(&A2, A);
  tog2(&C2, Csum);
  poly_point_init(&eV);      // compute e * G2 + public key
  poly_elptic_mul(&eV, sig.G2, e, sig.Ex);
  poly_elptic_sum(&eV, eV, PK[0], sig.Ex);
  poly_point_init(&R);
  poly_point_rand(&R, sig.Ex);
  weil(&wa, A2, eV, R, sig.tor, sig.Ex);
  weil(&wc, C2, sig.G2, R, sig.tor, sig.Ex);
  if(poly_cmp(wa, wc))
    printf("Signature verifies!\n");
  else
    printf("Signature FAILS!\n");

Once you have elliptic curve pairing routines available, lots of algorithms become possible. To fully understand the details, check out Elliptic Curve Cryptography for Developers: http://mng.bz/D9NA. So when someone says “Hey, you should try this!”, you can easily make it happen.

Reference:

@misc{cryptoeprint:2023/275, author = {Stefano Tessaro and Chenzhi Zhu}, title = {Revisiting BBS Signatures}, howpublished = {Cryptology ePrint Archive, Paper 2023/275}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/275}}, url = {https://eprint.iacr.org/2023/275} }