I'm working on a project with elliptic curve cryptography (ECC), I'm using the secp256k1 library (the one that's used in bitcoin).

My goal is to create the most compact platform-independent representation of an elliptic curve point.

Currently my encoding consists of an x-coordinate, 256 bits wide, encoded in a big-endian form, plus the sign (oddity) bit for the y-coordinate. In order to reconstruct the point I use the curve equation to receive the value for the y^2, and then find the square root. Though calculating square root isn't trivial, this enables to pass only a single bit for y.

Now I'm thinking to get rid of this bit too. I realize that it's just 0.4% of the data, but for casual point (part of some bigger data set) it's usually aligned to the byte boundary, so it's practically around 3%. Anyway, I'd like to see if/how this is possible.

The idea is that for y there's a solution for (roughly) half values of x, so I thought about using this fact. So that if, for example, there's a solution for the encoded x then even y is selected. Otherwise there should be some transformation for x, and then odd y is selected.

Is there a way to quickly calculate the "counter-part" of x, i.e. some unique transformation from x which will give the quadratic residue for y to x which will not, and vice-versa?

  • $\begingroup$ Even if it is possible, the encoding must be non-trivial, which means a noticeable computational overhead when processing each point. Then the question is whether it is worth paying the price for saving just one bit. $\endgroup$ Jun 3 '18 at 8:45
  • $\begingroup$ Of course it depends on how non-trivial the computation is vs how critical the size is. And that' what I'm trying to find-out, how complex is it to find the counter-part of x. $\endgroup$
    – valdo
    Jun 3 '18 at 9:11

Your Answer

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

Browse other questions tagged or ask your own question.