Elliptic Curves

Computing the Tate Pairing

Suppose we are working on a curve $E$ over $𝔽_{q}$ with security multiplier $k$ such that $E [l]$ is contained in $E / 𝔽_{q}^{k}$ .

e (P, Q) = f_{P} (𝒜_{Q})^{(q^{k} - 1) / l}

where $𝒜_{Q}$ is a divisor equivalent to $(Q) - (O)$ . and $(f_{P}) = l (P) - l (O)$ . For a supersingular curve with $k > 1$ , we may simplify this to $e (P, Q) = f_{P} (Q)^{(q^{k} - 1) / l}$ provided $P \in E / 𝔽_{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 ℤ$ , 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:

set $f \leftarrow 1$ and $V \leftarrow P$
for $i \leftarrow t - 1$ to 0 do
1. set $f \leftarrow f^{2} g_{V, V} (Q) / g_{2 V, - 2 V} (Q)$ and $V \leftarrow 2 V$
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 $- λ X + Y + (- y + λ x)$ , where $λ = \frac{3 x^{2} + a}{2 y}$ .
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 $- λ X + Y + (- y_{1} + λ x_{1})$ where $λ = \frac{y_{2} - y_{1}}{x_{2} - x_{1}}$ .

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

Computing the Tate Pairing

Miller’s Algorithm

The g P,Q functions

The $g_{P, Q}$ functions