Introduction to Cryptography with Coding Theory, 3rd Edition

22.1 Bilinear Pairings

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