I understand for prime curves it is just

bytes(0x02 + flag) + bytes(x)

where flag is the LSB of y. For the F2m curves I cannot make out how to do it.

  • IEEE P1363 section appears to say flag is '1 if y of point > y of inverse point else 0' which I think just means if y > x.

  • These slides (slide 15) by Julio Lopez and Ricardo Dahab appear to suggest my interpretation of the IEEE method is off (I think).

  • And this PDF - which I think is the standard reference - has yet another notation in section 2.3.3 part 2.2.2 that I do not understand.

Which of the above references represents the "standard" to handle this? And can someone please explain the proper/correct way to handle things; preferably from a programmer's perspective?

  • $\begingroup$ Note: with the standard Weierstrass elliptic curve with $p>3$, the inverse of $(x, y)$ is $(x, -y)$. For the standard curve with $p=2$, the inverse of $(x, y)$ is $(x, x\oplus y)$, where $\oplus$ is the bitwise xor operator. The Certicom reference has that as $+$; that's because, in $GF(2^k)$, bitwise-xor is the field addition operation $\endgroup$ – poncho Dec 4 '16 at 3:55

There are many different but similar ways to do point compression. To make sure we are all aligned, we need to standardize what we do. Let me summarize the content of the documents you cite:

  1. This is P1636.3, which is meant for Identity-Based Public Key Cryptography using Pairings, as can be seen on the IEEE P1636 homepage. It only considers elliptic curves over fields of odd order, and therefore is irrelevant for curve-based crypto over $\mathbb{F}_{2^m}$.
  2. The presentation by Lopez and Dahab shows distinct ways to do point compression over the field $\mathbb{F}_{2^m}$. They seem to propose a novel method, so this is really a perspective from researchers. On slide 15 they show a particular way to do compression, and they refer to the standard IEEE P1636 which contains it. Note that they refer to the general standard P1636, not P1636.3.
  3. This is the actual SEC1 standard, which among other things shows how to do point compression for elliptic curves over $\mathbb{F}_{2^m}$. This is described, as you say, in 2.3.3 part 2.2.2. They show how to do decompression in 2.3.4 part 2.4.2 and 2.4.3. Judging from Lopez and Dahab's slides (I don't have access to P1636 itself), this is done exactly the same way as in IEEE P1636.

Conclusion: in all your documents there is only a single standardized method to do point compression. This would be the most likely option, although I don't have enough experience "in the field" to guarantee this.


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.