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 💡