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