Score:3

Distinguishing points in elliptic curves over binary extension fields using Trace

lu flag

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,

poncho avatar
my flag
Actually, Weierstrass equations for even characteristic curves are different
G. Stergiopoulos avatar
lu flag
I amended the equation to fit for characteristic 2 curves, thanks.
kelalaka avatar
in flag
[An Analysis of Efficient Formulas for Elliptic Curve Point Addition over Binary Extension Fields](https://sci-hub.st/https://doi.org/10.1109/CISS.2011.5766253)
Score:3
us flag

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.

knaccc avatar
es flag
How is tr(x-coordinate) calculated?
G. Stergiopoulos avatar
lu flag
Nice find @SamJaques. I will have an extended look over the weekend and come back to you on that one.
G. Stergiopoulos avatar
lu flag
@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: https://www.math.uci.edu/~asilverb/bibliography/compress.pdf
kelalaka avatar
in flag
[An Analysis of Efficient Formulas for Elliptic Curve Point Addition over Binary Extension Fields](https://sci-hub.st/https://doi.org/10.1109/CISS.2011.5766253)
kelalaka avatar
in flag
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!
Sam Jaques avatar
us flag
Odd order is sufficient for every point to be double some other. I couldn't find anything in section H that covers the case of full-order points in an even-order subgroup.
G. Stergiopoulos avatar
lu flag
This adequately covers all possible situations for odd orders and, as @SameJaques stated, curves of even order under the aforementioned assumptions. Thanks! [continued]
G. Stergiopoulos avatar
lu flag
[continued] I tried to transfer this to curves over prime fields but, since $tr$ is not binary and doesn’t have characteristic = 2, I am not sure if this generalizes in some way over prime fields. Any thoughts?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.