**Table of Contents**

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.

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