News

Thanks to many contributors for fixes, wrappers, and tests.

It’s been over a decade since the last release, and over two since pbc-0.0.0. I had thought this project would have faded into obscurity by now, but I still receive patches occasionally. I challenged myself to build a new release. Miraculously, the old scripts still seem to work, and the only non-trivial edit was renaming a few MinGW invocations in a Makefile.

I bumped up the major version number. At the rate I’m going, this could be the last release, and it’d be a shame if the project never reached v1.0!

Homer Hsing added the Eta pairing, which is Type I in the library.

On top of this, he also performed much-needed maintenance: removing obsolete macros.

Many thanks to Homer Hsing, who has volunteered to help maintain the library. I’ve been having trouble finding time to work on it myself.

This release removes nested functions, which should make life easier for those trying to compile on OS X.

This fixes a param parsing bug. The old code assumed the params would terminate with a whitespace, and would behave poorly if it didn’t. The sample params are not affected because they all end with a newline.

Thanks to Michael Rushanan, you can now build on win32 using certain compilers.

Michael Adjedj again found a bug. It turns out I didn’t fix the problem correctly in the last release. Hopefully this time I did!

Michael Adjedj fixed a bug which caused element_pairing() to fail because of an uninitialized pointer.

Also I supported a feature request from Zi Lin, who wanted to raise an element in a finite group to an enormous power. The library now detects this and reduces the power modulo the order of the group before proceeding with the main loop.

Due to popular demand I changed the license from GPL To LGPL.

Many thanks to Zhang Ye, for contributing code that computes products of pairings. I’m told that using techniques described by Scott, Granger and Smart, the new function element_prod_pairing() is about 20% faster than a naive loop.

Many thanks to Aniket Kate for releasing C++ wrappers for the PBC library.

Geremy Condra has written Python 3 bindings for PBC.

Zhang Ye contributed a bugfix, and a patch that reportedly speeds up A1 pairings by about 5%.

Angelo De Caro wrote Java wrappers for the PBC library, and more amazingly, ported almost all of PBC to Java. I added a link to jPBC 1.0.0 on the Download page.

A couple of bug fixes.

I added functions so you can get at the coordinates of a point, and also the coefficients of a polynomial.

I replaced the hand-coded parser of pbc/pbc with one generated by Flex and Bison. I also changed its syntax slightly.

No garbage is collected, so long scripts should be avoided. I added a sample script, pairing_test.pbc, which I hope to be the beginning of a battery of tests.

I fixed a bug with pbc_param_set_str(). The pbc/pbc program works again.

I added a DLL to the Windows binary release. Hopefully it works with compilers besides MinGW. I would have added a GMP DLL as well but I was unable to build one.

Paul Miller reported bugs in my brand new pairing initialization functions. They should be fixed now.

The largest changes involve pairing initialization and pairing parameters.

For pairing initialization, supply a buffer containing pairing parameters instead of a FILE * stream. For example, rather than:

write something like:

For file reads, personally I like to use mmap() which suits pairing_init_set_buf().

The pbc_param_t data type for pairing parameters replaces a_param_t, …​, g_param_t. Having the same data type for all pairing parameter types simplifies the library, though some functions had to be changed slightly.

At last, one can initialize a pairing_t from a pbc_param_t:

Minor differences:

I trimmed the API. The file stream operations are gone. I removed the fetch_ops_t and tracker_t types: the standard C library already provides routines for reading from disk to memory.

I refactored to avoid exposing symtab_t and darray_t, and undocumented routines such as poly_alloc(). I mostly preserved the headers that define these functions, but they are no longer included by pbc.h.

I replaced the CMake files with simple.make, which I use during development, though I test the autotools build before release.

To reduce symbol pollution, all official functions and variables of the PBC now start with pbc_, field_, element_ or pairing_. Other names mostly have hidden visibility in a shared library. Watch out for renamed functions.

I added a convenience wrapper element_pp_pow_zn(), and cleaned up a few source files.

Stefan Weber fixed a bug in Yulian Kalev’s random number generator code for Windows.

Yulian Kalev contributed a random number generator for Windows, using the Microsoft Crypto API.

A minor bugfix, and an API change for curve finding functions.

Pairings now handle identity elements, a feature requested by Aniket Kate. In the past, my attitude was that the caller should check first, because in practical applications there’s never a need to feed an identity element into the pairing. But the cost of handling this special case is negligible, so I’ve changed my mind.

The files should be downloadable again.

No major changes. One example was removed, and the license was upgraded to GPLv3.

I stopped a crash when element_from_hash is called for GT on type D curves. Thanks to Paul Miller for reporting the bug.

Due to a horrible hashing routine, which I hope to fix one day, hashing to GT for D curves map everything to 1. The crash occurred because standardizing the coset representative uses an optimization involving Lucas sequences, which divides by zero when given 1.

Thanks again to Adam McLaurin for reporting that PBC was not playing with well C++. This has been fixed.

Fixed bug reported by Adam McLaurin.

Adam Aviv has released an application for SSARES: Secure Searchable Automated Remote Email Storage, which uses the PBC library.

His code originally used PBC version 0.2.16, an ancient version of PBC. He recently converted to the latest version: 0.4.12. If anyone else needs to do this same, the main obstacles Adam reported are:

Preprocessed exponentiation works again in GT. Thanks to Ian Goldberg for reporting this bug.

I finally repaired my laptop on which I develop PBC.

This release plugs a couple of memory leaks that were reported on the mailing list.

My PhD dissertation, "On the Implementation of Pairing-Based Cryptography", talks about many of the algorithms used by the PBC library.

Since I’ll lose my office machine soon, I moved the git repository to repo.or.cz. Git doesn’t appear to be installed on any Stanford servers. In fact, Googling for "stanford git" suggests I’m the only person here using this version control system.

Mulitplicative subgroups are handled properly so that one can pick random elements and hash to G_T. Hopefully it should be more robust in general. The code is a bit messy though, and I plan to clean it up later.

Michael Cheng kindly sent me a modified version of PBC 0.4.7 which can be compiled using Microsoft Visual C++. I have made it available on the download page.

I have not tried it myself as I don’t have this particular compiler handy.

I patched a memory leak reported by Michael Cheng. I forgot to free a temporary variable when I added Lucas sequences (which speed up D and G pairings).

Applied patch by Joe Cooley that addresses configure.ac issues and fixes a bug in example/zss.c.

A fairly lowlevel bug had somehow escaped my attention for quite some time. Comparing zero elements previously returned the wrong result, due to a simple logic bug in montfp.c.

Simple final powering optimizations were applied to D and G pairings.

Fortunately for me, Paul Miller tests each version extensively soon after release. In version 0.4.5 he found a bug that I had overlooked for one of the usual reasons: "the modification is so trivial that it can’t possibly cause problems!". Luckily the bug wasn’t difficult to fix.

I finally implemented what I call type G pairings, which are curves of embedding degree 10 found by David Freeman.

They’re a bit slow at the moment, but I hope to speed them up soon. Interestingly, Katherine Stange’s elliptic net algorithm for computing a type G pairing is about the same speed as Miller’s algorithm, but this is without using (signed) sliding windows for the latter.

No big changes. I added code that generates random points by raising a generator by a random power, which is faster in some cases as it avoids finite field square root routines. This change does not affect pairing speed.

I’ve been trying to find a case where computing the pairing with elliptic nets is faster than Miller’s algorithm. I haven’t found one yet, but the type E pairing comes close. If the group order weren’t a Solinas prime then it’s possible that the Shipsey-Stange algorithm would be faster.

Various optimizations improve A, D, E pairing times. In the type E case the optimization was trivial: simply precomputing the random point used in the pairing saved a lot of time.

For type A curves, I implemented an algorithm that computes pairings using elliptic nets: see Katherine Stange’s paper. It is not used by default since it is slower. To activate it, if p is a type A pairing, use:

The above paper is accompanied by a PARI/GP script which I used to check against my implementation. I had never used PARI/GP before, and it took me some time to work out what to do. I’ll record what I did here so I won’t have to relearn it next time. First I ran gp with the script as the first argument. Then I typed something like:

Minor changes, e.g. pairing_is_symmetric() function.

The pbc/pbc test program can convert strings to elements of any group. This should make it more effective as outputs from previous runs can now be reused. This also allows some pairing-based cryptosystems to be built using shell scripts.

The PBC library now has a logo, a result of an attempt to liven up these otherwise text-only pages.

I had thought that releasing version 0.4.0 and two new libraries during the Thanksgiving holiday would give me ample time to fix a few things and release the successor before too many people noticed. After all, who does any work during this time?

I was wrong. I have already received two emails pointing out a number of issues, mainly to do with documentation and the organization of files. This release should address these problems.

I removed the gitweb link. I belatedly realized that a web spider could harvest email addresses buried in PBC code and documentation files via the interface. (How do other projects deal with this? Perhaps there are options I can enable to mangle email addresses?) I also removed all email addresses from the AUTHORS file for good measure. They probably should not have been there in the first place.

I wrote a simple script that automatically chunks five news items per page and generates navigation links. This is much better than the manual editing I was doing before. The oldest items appear their own page and not here.

I’m trying to hype up PBC. The "About" page now looks more like a sales pitch, and I started a list of projects that use the PBC library. If you’re using PBC for something please let me know!

See the mailing list press release or the NEWS file for details. One big change is that the signature and broadcast encryption code have been spun off into new libraries. Together with new debugging features and file renaming (and the usual slew of minor fixes and cleanups), these constitute substantial modifications which justifies incrementing the minor version number.

The new libraries have their own webpages:

PBC_sig: http://crypto.stanford.edu/pbc/sig/

PBC_bce: http://crypto.stanford.edu/pbc/bce/

but share the same mailing list. They are in a highly immature state.

I’m following the cumbersome but informative satellite library naming convention of the SDL library. (Some SDL-based libraries have names such as SDL_Image or SDL_net.)

The roles of the three different places to get news on the library are becoming clearer. I changed the NEWS file to look more like the one in GMP and less like the ChangeLog. The latter is now the only place containing a play-by-play analysis.

One drawback of this new regimen is that I only started maintaining the ChangeLog from around version 0.3.0. Before that, details of changes can only be found an old verson of the NEWS file, though I have posted a webpage summarizing early PBC history.

I now use Valgrind to find memory leaks, and I have jettisoned my own clumsy kludgy leak detection code.

Various bugfixes. The most serious one was reported by Paul Miller: element_from_hash() was not returning the same point each time.

pbc.h now includes more header files so all the functions documented in the manual can be used without generating warnings (or learning about these extra header files).

I also added the pbc_mpz_randomb() function and a couple of test programs use this now.

Minor fixes: applied John Bethencourt’s patch to address bugs that arose on 64-bit machines, added some comments from Dmitry Kosolapov, resolved a naming conflict that should solve compilation problems in some cases.

The official PBC library URL is now

which means PBC is hosted by a department webserver rather than my personal office machine. However, the git repository still lives on my system.

I’ll try to keep the old URLs working for a while.

I reordered the arguments to element_from_hash(). It seems to be standard to pass the length of a buffer after the pointer to the buffer. This is incompatible with older versions of the library.

I renamed quan.c (contributed by Dmitry Kosolapov) to yuanli.c and removed workarounds that are not needed anymore.

I fixed a bug in element_init_same_as() (reported by John Bethencourt).

I also implemented some discrete log algorithms (brute force, Pollard rho and index calculus for some cases), but these aren’t documented.

I added the element_mul_zn() function so using additive notation for groups matches multiplicative notation better.

I changed how element_from_hash() and element_to_bytes() work. They are incompatible with older versions of PBC.

By default, PBC now tries to use /dev/urandom for random number generation. If this fails, it prints a warning and falls back to a deterministic random number generator.

Dmitry Kosolapov contributed quan.c (in the test subdirectory), which demonstrates the scheme described in this paper.

The previous release accidentally omitted a certain header file, due to a problem with Makefile.am.

Preprocessing for A1 pairings was implemented.

I was a little surprised because I have a script named makerelease that performs basic sanity checks when I release new versions. But then I realized my script only checks building from a git export, not from a tarball built by the autotools.

To avoid these sorts of problems in the future, I rewrote my script to create the tarball from the git tree, rather than rely on make dist. I’m not very good with the autotools, and for me it is much more important that the git repository contains every file.

Fixed a bug in the element_to_bytes() function for finite fields causing the output to depend on the host byte order.

Behind the scenes, code was cleaned. For example, I got rid of the curve_t data type which I found confusing, and did not fit with my philosophy of shoehorning every algebraic structure into the field_t data type.

The main improvement is Hovav Shacham’s preprocessed element exponentiation routines. See the manual for details.

Hovav Shacham and I created a mailing list to discuss the development of the PBC library.

From now, if you have any PBC-related questions please send them to pbc-devel at googlegroups dot com.

The URL for the list is: http://groups.google.com/group/pbc-devel

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:

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.

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

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.

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

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.

Preprocessing has been implemented for A and D pairings, the former benefiting greatly from this. See the benchmarks page.

Some minor bugfixes. Code cleanup: started removing include statements from header files that are used internally by PBC (see the last section in Rob Pike’s notes on programming in C). And the previous tarballs left out a header file.

I renamed type BGN pairings to type A1.

I wrote more of the manual. Now it describes how to generate pairing parameters, and some of the gory behind-the-scenes details of PBC.

I also modified the contributed code so it comforms to the way I do things.

I’ve been working on PBC fairly intensely and yet there have been no performance improvements. Most of the work has been manual labour. The documentation is in much better shape now, and includes a tutorial that I hope will show how easy it is to write cryptography applications using the library.

I also made some API changes. It is now possible to implement cryptosystems without knowing the details of PBC library types, and also without calling any GMP functions. I thought about adding more wrapper data types so that type checking will prevent elements of G1, G2, GT and Zr getting mixed up, but I felt that the library is usable enough as it is, and I have other priorities.

It might be a while before I can start working on optimizations. I still want to clean up the build system a little, make a few more API changes, and of course, keep adding documentation.

There were a few minor problems which I hastily corrected. Luckily, since the new build system gives the distribution the extension tar.gz instead of tgz I got the link to it wrong so no one could have downloaded it anyway.

I’ve started more work on the documentation, but there’s still a long way to go.

Added element_printf(), element_out_str() now returns number of bytes written (and zero on error). Swapped type C and type D curves so that it matches the labeling in my thesis. Applied patch sent by Joe Cooley: many compilation warnings eliminated, uses GNU build system, and other miscellaneous improvements. Put code in a Git repository.

I wanted to add more but I decided to release sooner rather than later. High on my list is to improve the shoddy documentation.

The build system needs tidying. At the moment there is the GNU build system for various UNIX flavours, the legacy Makefile just in case, and a Makefile for mingw on Windows.

I also want to move platform-dependent code to separate files, rather than have a bunch of ifdefs. I like to have as little preprocessor code as possible in source files, and would prefer to delegate the problem of deciding which variant to use to the build system.

There are now three places to look for news. Firstly, the ChangeLog, generated by git, which will be updated with terse statements every time the source is edited. Secondly, this webpage, which I intend to make more like a blog: chatty and containing any items related to this project, not just release-related news (such as plans for the future). Lastly, the NEWS file, which shall be written with a library user in mind, as opposed to someone developing the library.

Uses (generalized) Karatsuba polynomial multiplication for degree 3, 6 polynomials giving a slight speedup. Commented out Sakai-Kasahara Schnorr identity-based signature scheme due to patent issues.

Various optimizations, e.g. removed gross inefficiencies in polynomial multiplication that were somehow overlooked.

More cleanup. Every source file is in a subdirectory now. Formatted manual in DocBook. Changed output of listmnt. Can see progress of Hilbert polynomial computation. Renamed testmnt to gencparam.

Fixed problems with MNT curve generation.

Started organizing source files into subdirectories. Added Cha-Cheon and Sakai-Kasahara-Schnorr identity-based signatures. Matt Steiner’s broadcast encryption code is now included.

Added BGN curves i.e. type A curves of any given order.

Changed the way compressed points work. Incompatible with last version.

Added wrapper functions for reading/writing compressed/x-coordinate-only points.

Type F pairings implemented: these use curves with embedding degree 12.

Sliding windows for exponentiations in finite fields (due to Hovav Shacham). Fixed problem which prevented previous version from compiling.

Code cleanup. Type A pairings use projective coordinates. Minor type C pairing optimization.

Plugged a memory leak.

When possible, generated curves have group orders whose length in bits match the desired length exactly. Before it could be a off by one. Generated new sample A and E pairing parameters. Type E pairing optimized.

A few more optimizations.

Minor optimizations, bugfixes and cleanup.

Cleaned up code, plugged a memory leak. Implemented one type of singular curve.

New makefile from Hovav. Now creates the library libpbc.a. More documentation. API changes, pairings can be initialized with parameters from different types of curves.

Fixed a bug that caused element_from_bytes for field extensions to fail in some situations. Applied patch due to Hovav Shacham: new Makefile, code cleanup, multiexponentiation, bugfix.

Fixed curve parameter output bugs.

Plugged a memory leak.

Tate exponentiation optimization for MNT k=6 curves. The pairing is now over twice as fast for this case.

Optimizations e.g. denominator elimination for even embedding degrees by using twist curves. Bug fixes, e.g. length_in_bytes() for some fields.

Plugged memory leaks, some pairing optimizations (Solinas-prime-specific Miller’s algorithm, improved Tate exponentiation for degree 2 extensions). Bumped up minor version number rather than patch level to reflect increased confidence in the library for real applications.

Code cleanup, implemented k=2 supersingular curves.

Minor bugfix, BBS group signatures demo.

Implemented serialization for points.

Added different ways of generating random numbers. e.g. can call random_set_file("/dev/urandom") to use /dev/urandom as the source of random bits.

Wrote basic serialization/deserialization routines for some data types. Example Boneh-Lynn-Shacham and Boneh-Boyen signature libraries included, though eventually I intend to have a separate library for these.

Introduced the `pairing_t' data type, to make it easier to write programs using pairings. IBE, short signature demo programs.

Routines for MNT curve generation, pairing computation.