PBC Library - Pairing-Based Cryptography

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, 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.

Main

Docs

Misc

Benchmarks

Slower F Pairings in PBC 0.4.x