3
$\begingroup$

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,

$\endgroup$
3

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ How is tr(x-coordinate) calculated? $\endgroup$
    – knaccc
    Feb 18 at 15:42
  • $\begingroup$ Nice find @SamJaques. I will have an extended look over the weekend and come back to you on that one. $\endgroup$ Feb 18 at 18:19
  • 1
    $\begingroup$ @knaccc $Tr(x)$ over a binary extension field can be calculated as the sum of the conjugates of the polynomial representation of the element (in which case, $x$). In terms of elliptic curves, trace has to do with Frobenius and can be calculated in a similar (albeit not identical) way. Check this: math.uci.edu/~asilverb/bibliography/compress.pdf $\endgroup$ Feb 18 at 18:22
  • $\begingroup$ if an element generates a group of order odd then all elements are double of some other. Actually. we need more than odd, prime order. Section H, of the above paper, has better writing and mentions even case explicitly! $\endgroup$
    – kelalaka
    Feb 20 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.