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 mod 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 mod 3$. (For implementation purposes it is convenient to take $q = 11 mod 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.