## The Weil Pairing

Consider the group of $$m$$-torsion points $$E[m]$$ for some $$m$$ coprime to $$q = \mathrm{char} K$$.

For a point $$T \in E[m]$$, find a $$T_0$$ such that $$m T_0 = T$$ (i.e. $$T_0 \in [m]^{-1}(T)$$). Let $$g_T$$ be a rational function with divisor

$\langle g_T \rangle = \sum_{R\in E[m]} \langle T_0 + R \rangle - \langle R \rangle$

Let $$\tau_S$$ be the translation-by-$$S$$ map for some $$m$$-torsion point $$S$$. Then define the Weil pairing to be

$e(S,T) = \frac{g_T \cdot \tau_s }{ g_T }$

Since $$R, S$$ are both elements of the group $$E[m]$$:

$\langle g_T \cdot \tau_S (P) \rangle = \sum_{R\in E[m]} \langle T_0 + R - S \rangle - \langle R - S \rangle = \langle g_T \rangle$

So $$g_T$$ and $$g_T \cdot \tau_S$$ have the same divisor which implies $$e(S, T) = g_T \cdot \tau_S / g_T = \mu$$ for some constant $$\mu$$ (recall that $$g_T$$ is unique up to a constant).

Repeating this argument gives $$g_T \cdot \tau_S^i = \mu^i g_T$$. Since $$m$$ translations by $$S$$ is the identity (since $$S \in E[m]$$) we find $$\mu^m = 1$$, when $$i = m$$. In other words $$e(S,T) = \mu$$ is an $$m$$th root of unity.

So we may view the Weil pairing as a map

$e : E[m] \times E[m] \rightarrow \mu_m$

where $$\mu_m$$ is the group of the $$m$$th roots of unity.

Note this definition of the Weil pairing is not suitable for practical computations as the representations of the functions $$g_T(P), g_T(P+S)$$ grow quickly with $$m$$. (There are $$2m^2$$ poles and zeroes for each function, which means each function is a product of $$2m^2$$ line equations.) Fortunately an alternative definition of the Weil pairing lends itself well to explicit computation.

### Pullback of Divisors

This is another way to view this definition of the Weil pairing.

Suppose $$\alpha$$ is an endomorphism, and $$g$$ is a rational function. Then a natural construct is to compose $$g$$ and $$\alpha$$, i.e. $$g \cdot \alpha$$.

For example, if $$\alpha$$ is translation by a point $$T$$, then $$g \cdot \alpha (P)= g(P+T)$$.

The map $$\alpha$$ also induces a map on the divisors $$\alpha^* : Div(E) \rightarrow Div(E)$$ that takes the divisor of $$g$$ to the divisor of $$g \cdot \alpha$$.

For example, if $$\alpha$$ is translation by $$T$$, then $$\alpha^*$$ takes a divisor $$\sum m_P \langle P \rangle$$ to $$\sum m_P \langle P - T \rangle$$.

Then the function $$g_T$$ in the Weil pairing may be defined as a function such that

$\langle g_T \rangle = [m]^*(\langle T \rangle - \langle O \rangle)$

### Properties of The Weil Pairing

The Weil pairing is nondegenerate, alternating and bilinear.

• $$e(S_1 + S_2, T) = e(S_1, T) e(S_2, T)$$

• $$e(S, T_1 + T_2) = e(S, T_1) e(S, T_2)$$

• $$e(S, S) = 1$$

• $$e(S, T) = e(T, S)^{-1}$$

• $$e(S, T) = 1$$ for all $$T$$ if and only if $$S = O$$

• $$e(S, T) = 1$$ for all $$S$$ if and only if $$T = O$$

• For any nonzero endomorphism $$\alpha$$, $$e(\alpha(S), \alpha(T)) = e(S,T)^{\deg \alpha}$$
[TODO: define degree of endomorphism]

Ben Lynn blynn@cs.stanford.edu 💡