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. \)+

Ben Lynn blynn@cs.stanford.edu 💡