# Pairing Programming

Needs maintenance; refer to my thesis instead.

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 Bernstein calls Legendre’s method).

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

Ben Lynn blynn@cs.stanford.edu 💡