## 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. $$q$$ divides $$|E(\mathbb{F}_p)|$$

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

3. $$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.

Ben Lynn blynn@cs.stanford.edu 💡