# Bilinear Pairings

Central to pairing-based cryptosystems is a bilinear nondegenerate map, originally given as

$f : G \times G \rightarrow G_T$

where $$G, G_T$$ are both cyclic groups of prime order $$r$$, and the discrete log problem is hard in $$G$$.

## The Weil Pairing

Let $$E/\mathbb{F}_q$$ be an elliptic curve whose group of points contains a cyclic group of order $$r$$. Let $$k$$ be the smallest integer such that $$\mathbb{F}_{q^k}$$ contains the $$r$$th roots of unity. (If $$k \gt 1$$ then by the BK Theorem $$E[r] \subset E(\mathbb{F}_{q^k})$$.) Recall $$f_P$$ denotes the rational function with divisor $$l(P)-l(O)$$, and $$\mathcal{A}_P$$ denotes a divisor equivalent to $$(P) - (O)$$. The Weil pairing $$e : E[r] \times E[r] \rightarrow \mathbb{F}_{q^k}^*$$ is defined as

$e(P,Q) = \frac{f_P(\mathcal{A}_Q)}{f_Q(\mathcal{A}_P)}$

for choices of divisors that avoid the zeroes and poles of $$f_P, f_Q$$ thus allow $$e(P,Q)$$ to lie in $$\mathbb{F}_{q^k}^*$$. Miller’s algorithm is used to compute $$f_P(\mathcal{A}_Q)$$. The Weil pairing is nondegenerate and bilinear. Thus if we can find some point $$P$$ and a homomorphism $$\phi : \langle P \rangle \rightarrow E[r]$$ such that $$\phi(P)$$ and $$P$$ are linearly independent then taking $$G = \langle P \rangle$$ and $$G_T$$ to be the $$r$$th roots of unity (which lie in $$\mathbb{F}_{q^k}^*$$) gives a bilinear pairing suitable for cryptography, where we define

$f(P, Q) = e(P, \phi(Q))$

However, in practice it is better to use the Tate pairing.

## Examples

Suppose $$q$$ is a prime and $$q = 3 \bmod 4$$, so $$-1$$ is a quadratic residue in $$\mathbb{F}_q$$. Let $$E$$ be the curve

$E:y^2 = x^3 + x$

It turns out that $$\#E(\mathbb{F}_q) = q + 1$$ and $$\#E(\mathbb{F}_{q^2}) = (q+1)^2$$, thus the embedding degree is 2. Let $$r$$ be the largest prime dividing $$q+1$$, and define $$h$$ by $$r \cdot h = q+1$$. Then $$E(\mathbb{F}_q)$$ contains a cyclic subgroup of order $$r$$ which we call $$G$$, and $$E(\mathbb{F}_{q^2})$$ contains a group isomorphic to $$\mathbb{Z}_r \times \mathbb{Z}_r$$. Consider the homomorphism $$\phi:E(\mathbb{F}_q \rightarrow E(\mathbb{F}_{q^2})$$ given by

$\phi(x,y) = (-x, i y)$

where $$i$$ is a square root of -1. Clearly $$\phi$$ maps to points that are linearly independent of the input points, since the output points lie over a different field. (And since $$\phi$$ is a homomorphism, the output point has the same order as the input point.)

Thus with $$G$$, and $$\phi$$ as above, if we set $$G_T$$ to the subgroup of $$\mathbb{F}_{q^2}^*$$ that has order $$r$$, we have a concrete example of a bilinear nondegenerate pairing on groups where it is widely believed discrete log is hard.

A similar example is the curve $$E:y^2 = x^3 + 1$$ over $$\mathbb{F}_q$$ for any prime $$q = 2 \bmod 3$$. (For implementation purposes it is convenient to take $$q = 11 \bmod 12$$ so that $$-1$$ is guaranteed to be a quadratic nonresidue.) As above, it turns out $$\#E(\mathbb{F}_q) = q + 1$$ and $$\#E(\mathbb{F}_{q^2}) = (q+1)^2$$, and if we use the map $$\phi$$ given by $$\phi(x,y) = (\zeta x, y)$$ where $$\zeta$$ is a primitive cube root of unity we have another concrete instantiation of a pairing suitable for cryptography.

Note that these two examples fall in the first two classes of supersingular curves. TODO: link

Implementation note: $$r$$ can be chosen so that it is a Solinas prime, allowing Miller’s algorithm to be optimized greatly.

## Using Different Curves

In general a map $$\phi$$ may not exist. In fact if any curve except for the two examples given above is used, there is no known way to construct a suitable map $$\phi$$. To rectify the situation, we must change what it means to be a pairing suitable for cryptography.

Ben Lynn blynn@cs.stanford.edu 💡