## 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 > 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.

Ben Lynn blynn@cs.stanford.edu 💡