News Archive 7

I spent most of my time since the last release on a new test program confusingly named pbc. It allows interactive testing of the library. During the development I felt I may have been better off working on performance improvements instead of squandering time on a hand-written parser and interpreter, but now that it works, I'm pleased with the results. I have yet to document it. The following session shows how it can be used:

$ test/pbc
Pairing-Based Calculator
> a=rnd(G1)
> b=rnd(G2)
> c=pairing(a,b,A)
> c
[8123908995412397222629407861526403178767561618899656268507645810910469570940171
354920981464587606639849486738202862428348258236992210185732214124221043399 1895
53814264885989040711088624722149213923285853653986751240825585711288561007379288
8682665226785064897799276077038762941403815137279201878124496544381814]
> r=rand(Zr)
> c^r
[3657835355267111517147932281225731429445945576520458069770856379924948048294629
981309298603543337841873858888814047590238596753897868865331802933313743255 5062
40043246682709738369359568183546905789682883656306401246404807118581570274256476
4691903194225678537056515561674449527079685938158385917551215894965196]
> ar=a^r
> pairing(ar, b)
expect three arguments
runtime error (error code = 0)
> pairing(ar,b,A)
[3657835355267111517147932281225731429445945576520458069770856379924948048294629
981309298603543337841873858888814047590238596753897868865331802933313743255 5062
40043246682709738369359568183546905789682883656306401246404807118581570274256476
4691903194225678537056515561674449527079685938158385917551215894965196]
> br=b^r
> pairing(a,br,A)
[3657835355267111517147932281225731429445945576520458069770856379924948048294629
981309298603543337841873858888814047590238596753897868865331802933313743255 5062
40043246682709738369359568183546905789682883656306401246404807118581570274256476
4691903194225678537056515561674449527079685938158385917551215894965196]

There are actually no prompts. I edited them in afterwards to show exactly what I was typing.

I made a couple of minor fixes so that mingw can compile PBC. The resulting binaries for Windows are on the download page.

I generally get worse times with the Windows binaries, and they seem to vary more from run to run.

Fri Sep 29 12:33:33 PDT 2006

I rewrote element_vfprintf() so it does not use GNU C extensions. PBC should now compile under mingw, though I have to test this.

Thu Sep 28 15:06:39 PDT 2006

I implemented finite fields using Montgomery representation. Multiplication is faster, though inversion slows down a little. This improves the running time of all pairings except E (this pairing type isn't useful anyway).

I enjoyed the challenge of writing it, but I can't help feel that there ought be an implementation of integer mod rings in GMP. After all, GMP already has Montgomery reduction in its mpz_powm() function, and it has modular inversion routines too. With a little more coding they could easily get a fast integer mod ring library. I would much rather focus on elliptic curves.

There are some changes which may break compatibility with previous releases. I had forgotten to write element_sgn for the new finite fields code (which broke a few things). I have now fixed this, but I have changed the way it works. This means compressed elements from earlier PBC versions will be incompatible.

Also, there are minor change in the element_from_hash() functions, and they behave differently now.

Thu Sep 28 13:31:56 PDT 2006

Besides minor bugfixes and cleanup, finite fields are now much faster, which benefits all pairings. I also added some optimizations for type F pairings in particular. I eliminated memset() calls (see previous post) in several places by introducing a flag.

I have also included a CMakeLists.txt file which allows the PBC to be built using CMake. I prefer CMake because it is faster and does not increase the package size [more on this].

Wed Sep 27 17:18:05 PDT 2006

I removed the list of things to do from this site, because it is outdated and probably not helpful to anyone but me. From now I'll post items if I want to make my plans public.

I've been working on a faster implementation of finite fields. It is almost the same as the naive implementation that consists mostly of GMP wrappers, but is slightly more efficient because it avoids some dynamic memory allocation (once the modulus is known, the number of GMP limbs needed to store field elements is fixed) and can call low-level GMP functions.

The new implementation has some drawbacks: notably setting an element to a low integer, especially zero or one, is much slower because now a whole array has to be cleared, whereas before GMP would only need to change the _mp_size field. This slows down some of my pairing code. At the moment I'm removing such calls on F pairings (I have already fixed D pairings), and will release once that is done.

Next I want to implement finite fields using Montgomery reduction. I had already tried this once before, but due to bad coding it was slower than the simple implementation. With more experience with GMP internals, I'm confident I'll be able to make it fast this time, which will benefit all pairings.

Wed Sep 27 02:37:24 PDT 2006