Elliptic Curves

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

Consider a curve $E({𝔽}_{q^k})$. Let $\Phi$ be the Frobenius map $(X,Y)\mapsto (X^q,Y^q)$. For any $P\in E({𝔽}_q)$ we have $\Phi (P)=P$, thus $E({𝔽}_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 $trQ=Q+\Phi (Q)+...+{\Phi }^{k-1}(Q)=O$. Then we see that $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({𝒜}_Q)$ has coefficients in the ground field (where we view the coordinates of $P,Q$ as variables).

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

1. $q$ divides $\mid E({𝔽}_p)\mid$
2. $E[q]\subset E({𝔽}_{p^r})$ but $E[q]\neg \subset E({𝔽}_{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 ${𝔽}_{p^r}^{*}$ of the $q$th roots of unity.
Let $T$ be the subgroup of $E[q]$ of points of trace zero over ${𝔽}_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 ${\sigma }_i:{𝔽}_{p^r}\to {𝔽}_{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({𝔽}_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\mathrm{mod}r}(e(P,Q))$$ (The last equality holds since $e(P,Q)\in {𝔽}_{p^r}$.)

So for $i=0,...,r-1$ we have ${\sigma }_i(e(P,Q))={\sigma }_{2i\mathrm{mod}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 ${𝔽}_{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 {𝔽}_p$, which implies we must have $e(P,Q)=1$.

[Proof due to Dan Boneh.]