Chapter 10. PBC Internals
Prev   Next

Chapter 10. PBC Internals

Table of Contents

Design
Internal Randomness
Type A Internals
Type D Internals
Type E Internals
Type F Internals
Source Code
Religious Stances

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 on elements of 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. 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);
}

Design

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, but the results are undefined and the library will mostly cause a crash.

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, when I was comparing Montgomery representation versus a naive implementation of modular arithmetic.

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

The GNU libc manual states that data types ending in _t should not be used because they are reserved for future additions to C or POSIX. On the other hand, I want to stay consistent with GMP, and ending data types with _t is common practice.

Prev   Next
Benchmarks Home Internal Randomness