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 > 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 < 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 💡