Param generation

These were used to prepare the sample parameters in the param subdirectory.

We label the pairing families with capital letters roughly in the order of discovery, so we can refer to them easily. Type A is fastest. Type D is a good choice when elements should be short but is slower. Type F has even shorter elements but is slower still. The speed differences are hardware-dependent, and also change when preprocessing is used. Type B and C are unimplemented.

The pbc_cm_t data type holds CM parameters that are used to generate type D and G curves.

void pbc_cm_init(pbc_cm_t cm)

Initializes cm.

void pbc_cm_clear(pbc_cm_t cm)

Clears cm.

int pbc_cm_search_d(int (*callback)(pbc_cm_t, void *), void *data, unsigned int D, unsigned int bitlimit)

For a given discriminant D, searches for type D pairings suitable for cryptography (MNT curves of embedding degree 6). The group order is at most bitlimit bits. For each set of CM parameters found, call callback with pbc_cm_t and given void *. If the callback returns nonzero, stops search and returns that value. Otherwise returns 0.

int pbc_cm_search_g(int (*callback)(pbc_cm_t, void *), void *data, unsigned int D, unsigned int bitlimit)

For a given discriminant D, searches for type G pairings suitable for cryptography (Freeman curve). The group order is at most bitlimit bits. For each set of CM parameters found, call callback with pbc_cm_t and given void *. If the callback returns nonzero, stops search and returns that value. Otherwise returns 0.

void pbc_param_init_a_gen(pbc_param_t par, int rbits, int qbits)

Generate type A pairing parameters and store them in p, where the group order r is rbits long, and the order of the base field q is qbits long. Elements take qbits to represent.

To be secure, generic discrete log algorithms must be infeasible in groups of order r, and finite field discrete log algorithms must be infeasible in finite fields of order q^2, e.g. rbits = 160, qbits = 512.

The file param/a.param contains parameters for a type A pairing suitable for cryptographic use.

void pbc_param_init_a1_gen(pbc_param_t param, mpz_t n)

Generate type A1 pairing parameters and store them in p. The group order will be n. The order of the base field is a few bits longer. To be secure, generic discrete log algorithms must be infeasible in groups of order n, and finite field discrete log algorithms must be infeasible in finite fields of order roughly n2. Additionally, n should be hard to factorize.

For example: n a product of two primes, each at least 512 bits.

The file param/a1.param contains sample parameters for a type A1 pairing, but it is only for benchmarking: it is useless without the factorization of n, the order of the group.

void pbc_param_init_d_gen(pbc_param_t p, pbc_cm_t cm)

Type D curves are generated using the complex multiplication (CM) method. This function sets p to a type D pairing parameters from CM parameters cm. Other library calls search for appropriate CM parameters and the results can be passed to this function.

To be secure, generic discrete log algorithms must be infeasible in groups of order r, and finite field discrete log algorithms must be infeasible in finite fields of order q6. For usual CM parameters, r is a few bits smaller than q.

Using type D pairings allows elements of group G1 to be quite short, typically 170-bits. Because of a certain trick, elements of group G2 need only be 3 times longer, that is, about 510 bits rather than 6 times long. They are not quite as short as type F pairings, but much faster.

I sometimes refer to a type D curve as a triplet of numbers: the discriminant, the number of bits in the prime q, and the number of bits in the prime r. The gen/listmnt program prints these numbers.

Among the bundled type D curve parameters are the curves 9563-201-181, 62003-159-158 and 496659-224-224 which have shortened names param/d201.param, param/d159.param and param/d225.param respectively.

See gen/listmnt.c and gen/gendparam.c for how to generate type D pairing parameters.

void pbc_param_init_e_gen(pbc_param_t p, int rbits, int qbits)

Generate type E pairing parameters and store them in p, where the group order r is rbits long, and the order of the base field q is qbits long. To be secure, generic discrete log algorithms must be infeasible in groups of order r, and finite field discrete log algorithms must be infeasible in finite fields of order q, e.g. rbits = 160, qbits = 1024.

This pairing is just a curiosity: it can be implemented entirely in a field of prime order, that is, only arithmetic modulo a prime is needed and there is never a need to extend a field.

If discrete log in field extensions are found to be substantially easier to solve than previously thought, or discrete log can be solved in elliptic curves as easily as they can be in finite fields, this pairing type may become useful.

void pbc_param_init_f_gen(pbc_param_t p, int bits)

Generate type F pairing parameters and store them in p. Both the group order r and the order of the base field q will be roughly bits-bit numbers. To be secure, generic discrete log algorithms must be infeasible in groups of order r, and finite field discrete log algorithms must be infeasible in finite fields of order q^12, e.g. bits = 160.

Type F should be used when the top priority is to minimize bandwidth (e.g. short signatures). The current implementation makes them slow.

If finite field discrete log algorithms improve further, type D pairings will have to use larger fields, but type F can still remain short, up to a point.

void pbc_param_init_g_gen(pbc_param_t p, pbc_cm_t cm)

Type G curves are generated using the complex multiplication (CM) method. This function sets p to a type G pairing parameters from CM parameters cm. They have embedding degree 10.

To be secure, generic discrete log algorithms must be infeasible in groups of order r, and finite field discrete log algorithms must be infeasible in finite fields of order q6. For usual CM parameters, r is a few bits smaller than q.

They are quite slow at the moment so for now type F is a better choice.

The file param/g149.param contains parameters for a type G pairing with 149-bit group and field sizes.