diff options
author | 2015-09-04 07:35:06 +0000 | |
---|---|---|
committer | 2015-09-04 07:35:06 +0000 | |
commit | ca6aa8198d2335f8c326c3dd4d26bf5899064214 (patch) | |
tree | 6274a2d971fc0cac0896efe8583927d0190e3d20 /moon-abe/pbc-0.5.14/doc/sigex.txt | |
parent | 92fd2dbfb672d7b2b1cdfd5dd5cf89f7716b3e12 (diff) | |
parent | 3baeb11a8fbcfcdbc31976d421f17b85503b3ecd (diff) |
Merge "init attribute-based encryption"
Diffstat (limited to 'moon-abe/pbc-0.5.14/doc/sigex.txt')
-rw-r--r-- | moon-abe/pbc-0.5.14/doc/sigex.txt | 155 |
1 files changed, 155 insertions, 0 deletions
diff --git a/moon-abe/pbc-0.5.14/doc/sigex.txt b/moon-abe/pbc-0.5.14/doc/sigex.txt new file mode 100644 index 00000000..dcfc8d5e --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/sigex.txt @@ -0,0 +1,155 @@ +== 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"); + } +} +.... |