Overview

Minimal pairing-based cryptography requires:

  1. Arithmetic in $\mathbb{Z}_p$: I built mine on top of the GMP library, which conveniently provides number theoretic functions such as inversion modulo a prime and the Jacobi symbol.

  2. Elliptic curve groups: mostly routines for solving $y^2 = x^3 + a x + b$ over $\mathbb{Z}_p$, point addition and multiplication.

  3. Bilinear pairing: Miller’s algorithm.

The above suffices for what I call Type A and B (and A1) pairings: very fast, but elements take a lot of space to represent.

Field extensions must be implemented for other pairing types.

Finding certain pairing-friendly curves requires more work. The the MNT curve construction method requires routines for finding roots modulo a given prime, testing polynomial irreducibility, computing Hilbert polynomials. These in turn depend on high precision complex floating point arithmetic and also an algorithm to solve a Pell-type equation.

Arithmetic on Elliptic Curves

Curves over fields of characteristic greater than 3 can be written in the form $y^2 = x^3 + a x + b$. For such curves, point addition and multiplication routines are straightforward. (See Blake, Seroussi and Smart.) We give the explicit formulae here.

Suppose we wish to compute $R = P + Q$. If $P = O$, then $R = Q$ and similarly $Q = O$ is easily handled. If $P_x = Q_x$ then either $P_y = -Q_y$ in which case $R = O$ (for we have $P = -Q$), or $P = Q$ in which case the point doubling algorithm is invoked. Note that the point doubling algorithm assumes the input does not have order 2, i.e. the $y$-coordinate is nonzero. (If $P$ has order 2, the result is $O$.)

Point addition for $P \ne Q$:

\[ \array { \lambda & = & \frac{Q_y - P_y}{Q_x - P_x} \\ R_x & = & \lambda^2 - P_x - Q_x \\ R_y & = & (P_x - R_x)\lambda - P_y } \]

Point doubling:

\[ \array { \lambda & = & \frac{3 P_x^2 + a}{2 P_y} \\ R_x & = & \lambda^2 - 2 P_x \\ R_y & = & (P_x - R_x)\lambda - P_y } \]

Generating Random Points

The standard method to generate a random point on an elliptic curve is to choose a random $x$-coordinate and solve a quadratic equation for $y$. (If no solution exists, a new $x$-coordinate is chosen.) For odd characteristics, this can be done once one is able to find square roots of elements. In a finite field of prime order, square roots can be obtained via the Tonelli-Shanks algorithm. In general fields, see D.J. Bernstein’s draft of a paper entitled "Faster square roots in annoying finite fields". At the moment I just solve $x^2 - a$ using the Cantor-Zassenhaus method (which is referred to as Legendre’s method in the aforementioned reference).

Easier ways to generate random points exist for particular cases. For example if $p$ is a prime with $p = 2 \bmod 3$ then the cube root of $x \in \mathbb{F}_q$ is simply $x^{(2p-1)/3}$. Thus if $a = 0$ in the equation of the elliptic curve, then it is a simple matter to pick $y$ first and then solve for $x$.