Although most of this chapter could be done in the context of cyclic groups of prime order, the primary examples of pairings in cryptography are based on elliptic curves or closely related situations. Therefore, for concreteness, we use only the following situation.

Let $p$ be a prime of the form $6q-1\text{,}$ where $q$ is also prime. Let $E$ be the elliptic curve $y^2\equiv x^3+1$ mod $p\text{.}$ We need the following facts about $E$.

1. There are exactly $p+1=6q$ points on $E$.

2. There is a point $P_0\ne \infty$ such that $q{P}_0=\infty$. In fact, if we take a random point $P\text{,}$ then, with very high probability, $6P\ne \infty$ and $6P$ is a multiple of $P_0$.

3. There is a function $\tilde{e}$ that maps pairs of points $(a{P}_0\text{,}b{P}_0)$ to $q$th roots of unity for all integers $a\text{,}b$. It satisfies the bilinearity property

   $$\begin{array}{r}\tilde{e}(a{P}_0\text{,}b{P}_0)=\tilde{e}(P_0\text{,}{P}_0{)}^{ab}\end{array}$$

   for all $a\text{,}b$. This implies that

   $$\tilde{e}(aP\text{,}bQ)=\tilde{e}(P\text{,}Q{)}^{ab}$$

   for all points $P\text{,}Q$ that are multiples of $P_0$. (See Exercise 2.)

4. If we are given two points $P$ and $Q$ that are multiples of $P_0\text{,}$ then $\tilde{e}(P\text{,}Q)$ can be computed quickly from the coordinates of $P$ and $Q$.

5. $\tilde{e}(P_0\text{,}{P}_0)\ne 1\text{,}$ so it is a nontrivial $q$th root of unity.

We also make the following assumption:

1. If we are given a random point $P\ne \infty$ on $E$ and a random $q$th root of unity $\omega \ne 1\text{,}$ it is computationally infeasible to find a point $Q$ on $E$ with $\tilde{e}(Q\text{,}P)=\omega$ and it is computationally infeasible to find $Q^{\prime }$ with $\tilde{e}(P\text{,}{Q}^{\prime })=\omega$.

The fact that $\tilde{e}(P\text{,}Q)$ can be computed quickly needs some more explanation. The two points $P\text{,}Q$ satisfy $P=a{P}_0$ and $Q=b{P}_0$ for some $a\text{,}b$. However, to find $a$ and $b$ requires solving a discrete log problem, which could take a long time. Therefore, the obvious solution of choosing a random $q$th root of unity for $\tilde{e}(P_0\text{,}{P}_0)$ and then using the bilinearity property to define $\tilde{e}$ does not work, since it cannot be computed quickly. Instead, $\tilde{e}(P\text{,}Q)$ is computed directly in terms of the coordinates of the points $P\text{,}$ $Q$.

Although we will not need to know this, the $q$th roots of unity lie in the finite field with $p^2$ elements (see Section 3.11).

For more about the definition of $\tilde{e}\text{,}$ see [Boneh-Franklin] or [Washington].

The curve $E$ is an example of a supersingular elliptic curve, namely one where the number of points is congruent to 1 mod $p$. (See Exercise 4.) For a while, these curves were regarded as desirable for cryptographic purposes because computations can be done quickly on them. But then it was shown that the discrete logarithm problem for them is only slightly more difficult than the classical discrete logarithm mod $p$ (see Section 22.2), so they fell out of favor (after all, they are slower computationally than simple multiplication mod $p\text{,}$ and they provide no security advantage). Because of the existence of the pairing $\tilde{e}\text{,}$ they have become popular again.