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^{k1} (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
where $P, Q$ are points of trace zero and $e$ is any Galoisinvariant bilinear map. In particular, the Tate pairing is Galoisinvariant 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


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

$q$ does not divide $p1$.
Then $q$ divides $p^r 1$ but not $p^i1$ for $i = 1 ,..., r1$.
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 Galoisinvariant bilinear map.
Theorem: $e$ is degenerate on $T \times T$.
Proof: For $i=0,...,r1$ 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,...,r1$ 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
(The last equality holds since $e(P, Q) \in \mathbb{F}_{p^r}$.)
So for $i=0,...,r1$ 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 onetoone on $\mathbb{F}_{p^r}$ for $r \lt p1$.
But this means $e(P,Q) = \sigma_1(e(P,Q)) = ... = \sigma_{r1}(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.