Computing the Tate Pairing

Suppose we are working on a curve $E$ over $\mathbb{F}_q$ with security multiplier $k$ such that $E[l]$ is contained in $E / \mathbb{F}_q^k$.

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

where $\mathcal{A}_Q$ is a divisor equivalent to $(Q) - (O)$. and $(f_P) = l(P) - l(O)$. For a supersingular curve with $k \gt 1$, we may simplify this to $e(P,Q) = f_P(Q)^{(q^k - 1)/l}$ provided $P \in E/\mathbb{F}_q$.

Miller’s Algorithm

Let $g_{P,Q}$ be the line between the points $P$ and $Q$, and let $f_c$ be the function with divisor $(f_c) = c(P) - (cP) - (c-1)(O)$. Then for all $a,b \in \mathbb{Z}$, we have $f_{a+b}(Q) = f_a(Q) f_b(Q) g_{aP,bP}(Q) / g_{(a+b)P, -(a+b)P}(Q)$. Let the binary representation of $l$ be $l_t ,..., t_0$. Then Miller’s algorithm is the following:

  1. set $f \leftarrow 1$ and $V \leftarrow P$

  2. for $i \leftarrow t-1$ to 0 do

    1. set $f \leftarrow f^2 g_{V,V}(Q)/g_{2V, -2V}(Q)$ and $V \leftarrow 2V$

    2. if $l_i = 1$ then set $f = f g_{V,P}(Q)/g_{V+P, -(V+P)}(Q)$ and $V \leftarrow V + P$

At the end, $f = f_l(Q) = f_P(Q) = e(P,Q)$, and $V = l P$.

Note on implementation: by adding extra logic in the above algorithm, one can avoid handling points of infinity when computing the $g$ functions.

The $g_{P,Q}$ functions

Let the curve be $Y = X^3 + aX + b$.

  • Tangents: At the point $(x,y)$, the line describing the tangent at that point is $-\lambda X + Y + (-y + \lambda x)$, where $\lambda = \frac{3x^2 + a}{2y}$.

  • Vertical lines: These are lines between $P$ and $-P$. Let $P=(x,y)$. Then the vertical line through $P$ is $X + (-x)$.

  • Other lines: The line between $P=(x_1, y_1)$ and $Q=(x_2, y_2)$ is given by $ - \lambda X + Y + (-y_1 + \lambda x_1)$ where $\lambda = \frac{y_2 - y_1}{x_2 - x_1}$.

In implementations, it may be more efficient scale $\lambda$ appropriately and do all the divisions at once.