The Pairing-Based Cryptography Library

Benchmarks

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.

Average Pairing Time (ms)
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.

Slower F Pairings in PBC 0.4.x

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.

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.