The Tate pairing
Suppose that P and Q are points on an elliptic curve and that the order of P is n. Let fP be a rational function equivalent to n(P) – n(O) and DQ be the divisor (Q) – (O). Then the Tate pairing of P and Q is e(P, Q) = fP(DQ).
We know how to get fP and how to evaluate it at a divisor, but the fact that evaluating fP at the divisor (Q) – (O) would require evaluating fP at the point O causes trouble. But if R is another point not equal to O, it turns out that we get the same answer when we evaluate fP at (Q + R) – (R) as we do when we evaluate fP at (Q) – (O). This means that we can find e(P, Q) by doing the following:
- Find fP as we described previously.
- Pick a random R.
- Calculate e(P, Q) = fP(Q + R) / fP(R).
That’s all there is to it. When I first heard about the use of the Tate pairing in Boneh-Franklin identity-based encryption, for example, I used this very approach to implement the Tate pairing in Mathematica, and it was good enough for that purpose. There are lots of ways to make this calculation more efficient, but for small values of n, what we’ve described is fairly simple to implement.