]> Elliptic Curves - Computing the Tate Pairing

Computing the Tate Pairing

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

$e\left(P,Q\right)={f}_{P}\left({𝒜}_{Q}{\right)}^{\left({q}^{k}-1\right)/l}$

where ${𝒜}_{Q}$ is a divisor equivalent to $\left(Q\right)-\left(O\right)$. and $\left({f}_{P}\right)=l\left(P\right)-l\left(O\right)$. For a supersingular curve with $k>1$, we may simplify this to $e\left(P,Q\right)={f}_{P}\left(Q{\right)}^{\left({q}^{k}-1\right)/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 $\left({f}_{c}\right)=c\left(P\right)-\left(\mathrm{cP}\right)-\left(c-1\right)\left(O\right)$. Then for all $a,b\in ℤ$, we have ${f}_{a+b}\left(Q\right)={f}_{a}\left(Q\right){f}_{b}\left(Q\right){g}_{\mathrm{aP},\mathrm{bP}}\left(Q\right)/{g}_{\left(a+b\right)P,-\left(a+b\right)P}\left(Q\right)$. Let the binary representation of $l$ be ${l}_{t},...,{t}_{0}$. Then Miller’s algorithm is the following:

1. set $f←1$ and $V←P$

2. for $i←t-1$ to 0 do

1. set $f←{f}^{2}{g}_{V,V}\left(Q\right)/{g}_{2V,-2V}\left(Q\right)$ and $V←2V$

2. if ${l}_{i}=1$ then set $f=f{g}_{V,P}\left(Q\right)/{g}_{V+P,-\left(V+P\right)}\left(Q\right)$ and $V←V+P$

At the end, $f={f}_{l}\left(Q\right)={f}_{P}\left(Q\right)=e\left(P,Q\right)$, and $V=lP$.

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}+\mathrm{aX}+b$.

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

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

• Other lines: The line between $P=\left({x}_{1},{y}_{1}\right)$ and $Q=\left({x}_{2},{y}_{2}\right)$ is given by $-\lambda X+Y+\left(-{y}_{1}+\lambda {x}_{1}\right)$ 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.