Distinguishing points in elliptic curves over binary extension fields using Trace

Question

Let $E$ be an elliptic curve curve $𝑦^2 + xy ≡ 𝑥^3+𝑎𝑥^2+𝑏$ (a Weierstrass curve) (in this case, with characteristic 2) over a binary extension field $𝐺𝐹(2^{m})$ with constructing polynomial $𝑓(𝑧)$ be an irreducible, primitive polynomial over $GF(2)$, and let $P(x_p,y_p)$ be a point on the curve.

I have seen various implementations and discussions (like this answer at the bottom) mention that points $P$ can be distinguished with the field Trace function and that "it can be shown that for points in the curve's subgroup of prime order, the trace of $x_p$ coordinate must equal the trace of $a$ from the elliptic curve equation", i.e.

$Tr(x_p) = \begin{cases} \mbox{a,} & \mbox{if } P \in E \\ \mbox{1,} & \mbox{otherwise} \end{cases}$

Still, I cannot find any relevant bibliography that clearly explains why this holds from a mathematical perspective. Can anyone provide the relevant theory behind this? Also, what are the underlying restrictions and conditions needed for Trace to be able to reflect whether a point is on the curve or not?

Thank you for your time,

Answer 1

Here is what I could figure out based on the elliptic curve notes here: https://crypto.stanford.edu/pbc/notes/elliptic/explicit.html, given a point $P=(x_1,y_1)$ and a curve defined by $$Y^2+a_1XY = X^3+a_2X^2+a_4X+a_6$$ then the $x$-coordinate of $2P$ is given by

$$x_2 = \lambda^2 + a_1\lambda - a_2 - 2x_1$$

In your case, $a_1=1$. Also $2x_1=0$ because the field has characteristic 2, and we can switch all minus signs to plus signs for the same reason. Thus, the formula becomes:

$$x_2=\lambda^2 + \lambda + a$$

The trace of $x_2$ will be $\text{tr}(\lambda^2) + \text{tr}(\lambda)+\text{tr}(a)$. Since $\text{tr}(\lambda^2) = \text{tr}(\lambda)$, this means $\text{tr}(x)=\text{tr}(a)$. Thus, for any point $P$ on the curve, if $P=2Q$ for some $Q$, then the trace of $P$'s $x$-coordinate equals the trace of $a$.

If we have a cyclic subgroup with odd order $n$, then $2$ has some inverse $2^{-1}$ modulo $n$. Thus, starting from any point $P$ in this subgroup, we know that $2(2^{-1}P)=P$, so there exists a point $Q=2^{-1}P$ such that $P=2Q$, and thus its $x$-coordinate has the same trace as $a$.

Generally, every element of the subgroup $2E(GF(2^m)) = \{x+x : x\in E(GF(2^m))\}$ will all have this same trace.

What about other points? I don't know. It might be that points $P$ which do not equal $2Q$ for any $Q$ can still have trace equal to $\text{tr}(a)$, or maybe you can prove that they cannot.