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
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 > 3\) be an elliptic curve and let \(q\) be a prime such that
-
\(q\) divides \(|E(\mathbb{F}_p)|\)
-
\(E[q] \subset E(\mathbb{F}_{p^r})\) but \(E[q] \not\subset E(\mathbb{F}_{p^i})\) for \(i = 1,...,r-1\)
-
\(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
(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 < 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.