Points of Trace Zero

Let $r$ be the security multiplier. Then consider the map $P \mapsto r P - tr(P)$. This maps a point to a point of trace zero since the trace is additive and $tr(P) = r P$ if $P$ is in the ground field. The points of trace zero form a subgroup.

Consider a curve $E(\mathbb{F}_{q^k})$. Let $\Phi$ be the Frobenius map $(X, Y) \mapsto (X^q, Y^q)$. For any $P \in E(\mathbb{F}_q)$ we have $\Phi(P) = P$, thus $E(\mathbb{F}_q)$ is a $1$-eigenspace of $\Phi$.

The product of the eigenvalues of $\Phi$ is $q$, which means there must be a $q$-eigenspace as well. Now suppose $\mathrm{tr} Q = Q + \Phi(Q) + ... + \Phi^{k-1} (Q) = O$. Then we see that $\mathrm{tr} \Phi(Q) = O$, thus the group of trace zero points must be the $q$-eigenspace.

TODO: change notation below, also fix problems when $r$ and $k$ not coprime.

Pairings on Points of Trace Zero

It turns out that

\[e(P, Q)= 1\]

where $P, Q$ are points of trace zero and $e$ is any Galois-invariant bilinear map. In particular, the Tate pairing is Galois-invariant because $f_P(\mathcal{A}_Q)$ has coefficients in the ground field (where we view the coordinates of $P, Q$ as variables).

Let $E/\mathbb{F}_p, p \gt 3$ be an elliptic curve and let $q$ be a prime such that

  1. $E[q] \subset E(\mathbb{F}_{p^r})$ but $E[q] \not\subset E(\mathbb{F}_{p^i})$ for $i = 1,...,r-1$

  2. $q$ does not divide $p-1$.

Then $q$ divides $p^r -1$ but not $p^i-1$ for $i = 1 ,..., r-1$.

Let $U$ be the subgroup of $\mathbb{F}_{p^r}^*$ of the $q$th roots of unity.

Let $T$ be the subgroup of $E[q]$ of points of trace zero over $\mathbb{F}_p$.

Let $e:E[q]\times E[q] \rightarrow U$ be a Galois-invariant bilinear map.

Theorem: $e$ is degenerate on $T \times T$.

Proof: For $i=0,...,r-1$ let $\sigma_i : \mathbb{F}_{p^r} \rightarrow \mathbb{F}_{p^r}$ be the Galois map defined by $\sigma_i(x) = x^{p^i}$.

Observe that for all $i=0,...,r-1$ we have that $\sigma_i(T) = T$. Hence $T$ is an eigenspace for $\sigma_i$.

Furthermore, for $P \in T$ we have $\sigma_i(P) = p^i P$. To see this, let $\lambda_1,\lambda_2$ be the eigenvalues of $\sigma_i$ acting on $E[q]$. By Weil’s Theorem, we have that $\lambda_1 \lambda_2 = p^i$. Observe that $E(\mathbb{F}_p)$ is an eigenspace of $\sigma_i$ with eigenvalue one. Therefore the other eigenvalue must be equal to $p^i$.

Let $P,Q \in T$. Then

\[\sigma_i(e(P,Q)) = e(\sigma_i(P),\sigma_i(Q)) =e(p^i P, p^i Q) = e(P,Q)^{p^{2i}} = \sigma_{2i \bmod r}(e(P,Q)) \]

(The last equality holds since $e(P, Q) \in \mathbb{F}_{p^r}$.)

So for $i=0,...,r-1$ we have $\sigma_i(e(P, Q)) = \sigma_{2i \bmod r}(e(P,Q))$.

Hence $\sigma_1(e(P,Q)) = \sigma_2(e(P,Q))$ which implies that $e(P,Q) = \sigma_1(e(P,Q))$ since $x \mapsto x^p$ is one-to-one on $\mathbb{F}_{p^r}$ for $r \lt p-1$.

But this means $e(P,Q) = \sigma_1(e(P,Q)) = ... = \sigma_{r-1}(e(P,Q))$ and hence $e(P,Q) \in \mathbb{F}_p$, which implies we must have $e(P,Q) = 1$.

Proof due to Dan Boneh.