Elliptic Curves - Points of Trace Zero

Points of Trace Zero

Let $r$ be the security multiplier. Then consider the map $P \mapsto r P - t r (P)$ . This maps a point to a point of trace zero since the trace is additive and $t r (P) = r P$ if $P$ is in the ground field. The points of trace zero form a subgroup.

Consider a curve $E (F_{q^{k}})$ . Let $Φ$ be the Frobenius map $(X, Y) \mapsto (X^{q}, Y^{q})$ . For any $P \in E (F_{q})$ we have $Φ (P) = P$ , thus $E (F_{q})$ is a $1$ -eigenspace of $Φ$ .

The product of the eigenvalues of $Φ$ is $q$ , which means there must be a $q$ -eigenspace as well. Now suppose $tr Q = Q + Φ (Q) + . . . + Φ^{k - 1} (Q) = O$ . Then we see that $tr Φ (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} (A_{Q})$ has coefficients in the ground field (where we view the coordinates of $P, Q$ as variables).

Let $E / F_{p}, p > 3$ be an elliptic curve and let $q$ be a prime such that

$q$ divides $| E (F_{p}) |$
$E [q] \subset E (F_{p^{r}})$ but $E [q] ⊄ E (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 $F_{p^{r}}^{*}$ of the $q$ th roots of unity.

Let $T$ be the subgroup of $E [q]$ of points of trace zero over $F_{p}$ .

Let $e : E [q] \times E [q] \to U$ be a Galois-invariant bilinear map.

Theorem: $e$ is degenerate on $T \times T$ .

Proof: For $i = 0, . . ., r - 1$ let $σ_{i} : F_{p^{r}} \to F_{p^{r}}$ be the Galois map defined by $σ_{i} (x) = x^{p^{i}}$ .

Observe that for all $i = 0, . . ., r - 1$ we have that $σ_{i} (T) = T$ . Hence $T$ is an eigenspace for $σ_{i}$ .

Furthermore, for $P \in T$ we have $σ_{i} (P) = p^{i} P$ . To see this, let $λ_{1}, λ_{2}$ be the eigenvalues of $σ_{i}$ acting on $E [q]$ . By Weil’s Theorem, we have that $λ_{1} λ_{2} = p^{i}$ . Observe that $E (F_{p})$ is an eigenspace of $σ_{i}$ with eigenvalue one. Therefore the other eigenvalue must be equal to $p^{i}$ .

Let $P, Q \in T$ . Then

σ_{i} (e (P, Q)) = e (σ_{i} (P), σ_{i} (Q)) = e (p^{i} P, p^{i} Q) = e (P, Q)^{p^{2 i}} = σ_{2 i mod r} (e (P, Q))

(The last equality holds since $e (P, Q) \in F_{p^{r}}$ .)

So for $i = 0, . . ., r - 1$ we have $σ_{i} (e (P, Q)) = σ_{2 i mod r} (e (P, Q))$ .

Hence $σ_{1} (e (P, Q)) = σ_{2} (e (P, Q))$ which implies that $e (P, Q) = σ_{1} (e (P, Q))$ since $x \mapsto x^{p}$ is one-to-one on $F_{p^{r}}$ for $r < p - 1$ .

But this means $e (P, Q) = σ_{1} (e (P, Q)) = . . . = σ_{r - 1} (e (P, Q))$ and hence $e (P, Q) \in F_{p}$ , which implies we must have $e (P, Q) = 1$ .

Proof due to Dan Boneh.

Ben Lynn blynn@cs.stanford.edu 💡

Points of Trace Zero

Pairings on Points of Trace Zero

Contents