Chapter 8. PBC internals

Table of Contents

Groups, rings, fields
Internal randomness
Type A internals
Type B internals
Type C internals
Type D internals
Type E Internals
Type F internals
Type G Internals
Testing functions
Dynamic arrays
Symbol tables
Religious stances

The source code is organized by subdirectories:

include: Headers describing the official API. Headers in other places are for internal use only.

arith: Finite fields: modular arithmetic, polynomial rings, and polynomial rings modulo a polynomial. Finite fields of low characteristic are unsupported.

ecc: Elliptic curve generation, elliptic curve groups and pairings. One source file is dedicated to each type of pairing, containing specialized optimizations. Some of the code requires arbitrary precision complex numbers, which also live here but should be moved elsewhere one day.

misc: Dynamic arrays, symbol tables, benchmarking, logging, debugging, other utilities.

gen: Programs that generate pairing parameters and list Hilbert polynomials. These were used to prepare the samples in the param directory.

example: Example programs showing how to use the library.

guru: Tests, experimental code.

Groups, rings, fields

Algebraic structures are represented in the field_t data type, which mostly contains pointers to functions written to perform operations such as addition and multiplication in that particular group, ring or field:

struct field_s {
  ...
  void (*init)(element_ptr);
  void (*clear)(element_ptr);
  ...
  void (*add)(element_ptr, element_ptr, element_ptr);
  void (*sub)(element_ptr, element_ptr, element_ptr);
  void (*mul)(element_ptr, element_ptr, element_ptr);
  ...
};
typedef struct field_s *field_ptr;
typedef struct field_s field_t[1];

The name algebraic_structure_t is arguably more accurate, but far too cumbersome. It may help if one views groups and rings as handicapped fields.

The last two lines of the above code excerpt show how GMP and PBC define data types: they are arrays of length one so that when a variable is declared, space is automatically allocated for it on the stack. Yet when used as a argument to a function, a pointer is passed, thus there is no need to explicitly allocate and deallocate memory, nor reference and dereference variables.

Each element_t contains a field named field to such a field_t variable. The only other field is data, which stores any data needed for the implementation of the particular algebraic structure the element resides in.

struct element_s {
  struct field_s *field;
  void *data;
};

When an element_t variable is initialized, field is set appropriately, and then the initialization specific to that field is called to complete the initialization. Here, a line of code is worth a thousand words:

void element_init(element_t e, field_ptr f) {
  e->field = f;
  f->init(e);
}

Thus during a call to one of the element_ functions, the field pointer is followed then the appropriate routine is executed. For example, modular addition results when the input element is an element of a finite field, while polynomial addition is performed for elements of a polynomial ring and so on.

void element_add(element_t n, element_t a, element_t b) {
  n->field->add(n, a, b);
}

My design may seem dangerous because if a programmer inadvertently attempts to add a polynomial and a point on an elliptic curve, say, the code will compile without warnings since they have the same data type.

However I settled on having a catch-all “glorified void *element_t because I wanted to

  • extend a field an arbitrary number of times (though in practice, currently I only need to extend a field twice at most),
  • switch fields easily, so for example a program that benchmarks addition in polynomial rings can be trivially modified to benchmark addition in a group, and
  • interchange different implementations of the same algebraic structure, for example, compare Montgomery representation versus a naive implementation of integer modulo rings.

Additionally, defining PBC_DEBUG catches many type mismatches.

In mathematics, groups, rings and fields should be distinguished, but for implmentation, it is simplest lump them together under the same heading. In any event, distinct data types may lead to a false sense of security. Fields of prime order with different moduli would still fall under the same data type, with unpleasant results if their elements are mistakenly mixed.

I have vague plans to add flags to field_t describing the capabilities of a particular field_t. These flags would be set during initialization, and would indicate for example whether one can invert every nonzero element, whether there are one or two operations (that is, group versus ring), whether the field is an integer mod ring, polynomial ring, or polynomial mod ring, and so on. Once in place, more runtime checks can be performed to avoid illegal inversion and similar problems.

Another option is to introduce data types for each of the four pairing-related algebraic structures, namely G1, G2, GT and Zr, as these are the only ones needed for implementing pairing-based cryptosystems.

An alternative was to simply use void * instead of element_t and require the programmer to pass the field as a parameter, e.g. element_add(a, b, c, F_13), but I decided the added annoyance of having to type this extra variable every time negated any benefits, such as obviating the need for the field pointer in struct element_s, even if one ignores the more serious problem that runtime type checking is considerably harder, if not impossible.

I suppose one could write a preprocessor to convert one type of notation to the other, but I would like the code to be standard C. (On the other hand, as Hovav Shacham suggested, it may be nice to eventually have a converter that takes human-friendly infix operator expressions like a = (b + c) * d and outputs the assembly-like element_ equivalents.)