n = 10; ttotal = 0.0; for (i = 0; i < n; i++) { element_random(x); element_random(y); t0 = get_time(); pairing_apply(r, x, y, pairing); t1 = get_time(); ttotal += t1 - t0; } printf("average pairing time = %f\n", ttotal / n);
The table below contains the output of the report_times script. For several different types of pairings, 10 pairings with random inputs are computed and the average time is printed. An excerpt of the benchmark code is shown below.
n = 10; ttotal = 0.0; for (i = 0; i < n; i++) { element_random(x); element_random(y); t0 = get_time(); pairing_apply(r, x, y, pairing); t1 = get_time(); ttotal += t1 - t0; } printf("average pairing time = %f\n", ttotal / n);
The following table shows running times of various pairings in PBC, where (pp) means preprocessing was used. Note preprocessing has not been implemented for every type of curve, which explains why it has no effect in some cases.
Version | Pairing Type | |||||||
---|---|---|---|---|---|---|---|---|
a | d159 | d201 | d224 | e | f | g149 | a1 | |
pbc-0.4.7 (pp) | 11 | 31 | 51 | 62 | 109 | 193 | 116 | 181 |
pbc-0.4.7 | 25 | 40 | 64 | 79 | 109 | 193 | 125 | 757 |
pbc-0.3.14 (pp) | 13 | 37 | 62 | 73 | 187 | 188 | - | 184 |
pbc-0.3.14 | 27 | 47 | 75 | 90 | 186 | 188 | - | 763 |
On the same machine and also using the GMP library, an RSA decryption takes roughly 12ms (and 19ms if CRT preprocessing is not used: see test/timersa.c).
Below is a description of all the pairing parameters. In each case the curve group has a 160-bit group order, and k denotes the embedding degree of the curve.
Type | Base field size | k | Dlog security | Comments |
---|---|---|---|---|
(bits) | (bits) | |||
a | 512 | 2 | 1024 | Fastest pairing, good for cryptosystems where group element size is not critical. Uses supersingular curve Y^2 = X^3 + X. Group order is a Solinas prime. |
dn | n | 6 | 6n | Good for cryptosystems when group elements must be as short as possible. Uses MNT method to generate curves. |
e | 1024 | 1 | 1024 | Not useful, but requires only modular arithmetic to implement. Curve easily found using CM method. |
f | 160 | 12 | 1920 | Useful for insuring against future finite field discrete log algorithm improvements. Curve found using method due to Paulo Barreto. |
gn | n | 10 | 10n | Slower than embedding degree 12 pairings, perhaps not worth using. Uses Freeman-Scott algorithm to generate curves. |
a1 | 1024 | 2 | 2048 | Some cryptosystems need the curve order to be a specific number, e.g. N = p q where p and q are large primes so that N is hard to factorize. We can find a suitable pairing by using the same curve as for type A pairings. |
Test machine:
ben@rooster:~$ cat /proc/cpuinfo processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 8 model name : Pentium III (Coppermine) stepping : 6 cpu MHz : 997.023 cache size : 256 KB fdiv_bug : no hlt_bug : no f00f_bug : no coma_bug : no fpu : yes fpu_exception : yes cpuid level : 2 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 sep mtrr pge mca cmov pat pse36 mmx fxsr sse bogomips : 1970.17 ben@rooster:~$ dpkg -p libgmp3 | grep Version Version: 4.1.4-6 ben@rooster:~$ dpkg -p gcc | grep Version Version: 4:3.3.5-3 ben@rooster:~$ uname -r -s Linux 2.6.12.5
I lost this machine after I graduated. I’ll have to use a new machine for any future benchmarks.
Type F pairings slowed in version 0.4.0 after checks for malloc() errors were added. The other pairings experienced a penalty too small to appear in the above table. I interpret this to mean my Type F code is allocating and deallocating memory excessively, which I will eventually investigate.
It is possible to reduce the penalty by calling
pbc_set_memory_functions(malloc, realloc, free);
but this means memory allocation errors will not be handled, which is potentially dangerous. To remove the penalty entirely one must search and replace the PBC malloc wrappers with the original mallocs and recompile the library.
I highly recommend TCMalloc, a fast drop-in replacement for the standard C memory allocation functions. Sadly, I don’t know how to tell the autotools to detect its presence and use it automatically.