We use the same notation as before. Assume \(k\) is even. Let \(d = k / 2\). Let \(E\prime\) be the twist of the curve \(E(\mathbb{F}_{q^d})\), so that if \(v\) is a quadratic nonresidue in \(\mathbb{F}_{q^d}\) and \(E\) is given by \(y^2 = x^3 + a x + b\) then \(E\prime\) is given by \(y^2 = x^3 + v^2 a x + v^3 b\) (see notes on MNT curves). (We have \(\mathbb{F}_{q^k} = \mathbb{F}_{q^d}[\sqrt{v}]\).) Then the map \(\Psi : E\prime \rightarrow E(\mathbb{F}_{q^k})\) given by

is a homomorphism.

Now let \(P\) be a point of order \(r\) in \(E(\mathbb{F}_q)\) and \(Q\prime\) be any point in \(E\prime(\mathbb{F}_{q^d})\). Setting \(G = \langle P \rangle\), \(G\prime = \langle \{\Psi(Q\prime)\} \rangle\), where \(\{Q\}\) denotes the coset containing \(Q\), \(f\) to be the Tate pairing, and \(G_1\) to the subgroup of \(\mathbb{F}_{q^k}\) of order \(r\) yields a pairing suitable for cryptography.

Most operations occur in the fields \(\mathbb{F}_q\) and \(\mathbb{F}_{q^d}\). We only apply the map \(\Psi\) and perform operations in \(\mathbb{F}_{q^k}\) when a pairing is required.

The above map \(\Psi\) is precisely the map \(\phi\) that was mentioned in the the first example on the page defining the pairing. We have essentially described a way for all pairing-based cryptosystems (that use an even embedding degree) to benefit from twist maps.

Note we have a dilemma for the second example on the page mentioned above. The twist of \(y^2 = x^3 + 1\) is \(y^2 = x^3 - 1\) (if we have chosen a field where \(-1\) is a quadratic nonresidue). If the inputs to the pairing come from the same group, we cannot use twist curves. Although most operations still are performed in the base field, we cannot use the denominator elimination optimization described below. The alternative is to use the twist curve for the second input group, but now the inputs to the pairing come from different groups.

To compute a Tate pairing, a quotient is iteratively calculated (Miller’s algorithm) and then raised to power of \((q^k - 1)/r\), the Tate exponent. Each factor of the denominator is the equation of a vertical line evaluated at a particular point, i.e. the equation \(X - a\) evaluated at some point \((x,y)\), which gives the factor \((x-a)\).

Because of the way we have selected our groups, \(x \in \mathbb{F}_{q^d}\) (note that the map \(\Psi\) leaves the \(x\)-coordinate of its input in the same field), and \(a \in \mathbb{F}_q\) hence \((x-a) \in \mathbb{F}_{q^d}\).

Any element \(a \in \mathbb{F}_{q^d}\) satisfies \(a^{q^d - 1}\). Observe \(q^d - 1\) divides \((q^k - 1)/r\), the Tate exponent, because \(r\) cannot divide \(q^d - 1\) (otherwise \(d\) would be the embedding degree, not \(k\)). Thus each factor \((x-a)\) raised to the Tate exponent is \(1\), so it can be left out of the quotient. Hence there is no need to compute the denominator at any time in Miller’s algorithm, which we rewrite below.

For odd \(r\), the calculation in last iteration is

Since \({r-1}P = -P\), \(g\) is simply the vertical line at \(P\) which by denominator elimination can be ignored. Hence \(f_r = f_{r-1}\).