◀ Bilinear PairingB-K Theorem ▶
Contents

The Tate Pairing

The Tate pairing is faster than the Weil pairing, not only because it only requires one application of Miller’s algorithm instead of two, but also because it allows a host of optimizations. Also, the Tate pairing can be used in some situations where the Weil pairing (see the example given after the BK Theorem). Futhermore the second input of the Tate pairing is a coset representative, thus it does not have to be of order \(r\).

The only advantage that the Weil pairing has over the Tate pairing is that it is simpler to describe: it is just a map that takes two points and spits out a root of unity. (The Weil pairing does have properties not shared by the Tate pairing such as antisymmetry, but these are not needed in cryptography.)

Let \(E\) be an elliptic curve defined over a finite field \(K\) containing a point of order \(r\) prime to \(\mathrm{char} K\). Suppose \(K\) contains the \(r\)th roots of unity. (A more succint way to state these conditions is to require that \(r\) divides \(\mathrm{ord} K - 1\).)

Then in the literature, the Tate pairing

\[ e : E[r] \cap E(K) \times E(K) / r E(K) \rightarrow K^* / K^{*r} \]

is given by

\[ e(P, Q) = f_P (\mathcal{A}_Q) \]

The Weil pairing requires us to find a field containing all \(r\)-torsion points, while the Tate pairing only requires the field to contain the \(r\)th roots of unity. When the embedding degree is greater than 1, these conditions are identical.

For efficiency, when the embedding degree \(k\) is at least 2, one of the inputs is restricted to a subfield. Depending on the application, we may choose to restrict the first input:

\[ e : E[r] \cap E(\mathbb{F}_q) \times E(\mathbb{F}_{q^k}) / r E(\mathbb{F}_{q^k}) \rightarrow \mathbb{F}_{q^k}^* / \mathbb{F}_{q^k}^{*r} \]

(we replace \(K\) with \(\mathbb{F}_{q^k}\), and restrict the first argument to a certain subfield). As before, \(\mathbb{F}_q\) is the smallest field containing some \(r\)-torsion points of \(E\).

Or we may choose to restrict the second input:

\[ e : E[r] \times E(\mathbb{F}_{q}) / r E(\mathbb{F}_{q}) \rightarrow \mathbb{F}_{q^k}^* / \mathbb{F}_{q^k}^{*r} \]

This time, the first input is any \(r\)-torsion point (which must lie in \(E(\mathbb{F}_{q^k})\) while the second input is represented by any point from \(E(\mathbb{F}_q)\) (it can be of any order).

The output of the Tate pairing is a coset representative. In order to standardize the coset representative, we may exponentiate appropriately, hence we redefine the Tate pairing to be the function

\[ e(P, Q) = f_P(\mathcal{A}_Q)^{(q^k-1)/r} \]

where \(P \in E/\mathbb{F}_q\) has order \(r\) and \(Q \in E/\mathbb{F}_{q^k}\) can be any point. This function is nondegnerate and bilinear.

◀ Bilinear PairingB-K Theorem ▶
Contents
Ben Lynn blynn@cs.stanford.edu 💡