5
$\begingroup$

On an elliptic curve such as $y^2 = x^3 + b$, we define $a$ compressed point $P = (x, y)$ by it's coordinate $x$ and the parity of the $y$ coordinate. $y$ can be computed using $y = \pm\sqrt{x^3 + b}$ and choosing the right value of $y$ using the parity information.

We also define a point in Jacobian coordinate such as $P = (a, b, z)$ with $x = a / z^2$ and $y = b / z^3$ .

I would like to know if there is a known way to check if 2 points in these two set of coordinates are the same point that is cheap. Computing if the $x$ coordinates are the same is easy by checking if $x * z^2 = a$ .

To check if the $y$ coordinate are the same, the best I can come up with is to compute $y = a * z^{-3}$ and check if it has the same parity as the compressed point. However, it requires an expensive computation of the multiplicative inverse of $z$ to get $z^{-1}$. This seems rather overkill as it compute way more information than required. Only one bit is needed.

I was wondering if there is a known way to check if thee 2 points are the same that do not involve expensive computations such as the finding multiplicative inverse or a quadratic residue to decompress the point.

Improve this question
$\endgroup$
2
  • $\begingroup$ Obvious question: are you sure you need to check the $y$ coordinate? For some protocols (e.g. ECDH, where the shared secret consists of only the $x$ coordinate), which $y$ coordinate you use literally does not matter. Of course, for other protocols, which $y$ coordinate you use is essential, and so your answer might be "yes, I'm sure..." $\endgroup$
    – poncho
    Commented Mar 20, 2017 at 18:36
  • $\begingroup$ Yes, for malleability reasons. However, indeed, I check the y only if the x do match, which avoids the need for inversion for invalid signatures. $\endgroup$
    – deadalnix
    Commented Mar 20, 2017 at 20:33

1 Answer 1

Reset to default
2
$\begingroup$

Computing the $z^{-1}$ is very cheap. We can do this by Euclidean algorithm, and in logarithmic time. But you can set $z=1$ in projective coordination. This make computations easy($O(1)$ since $z^{-1}=1$), and with this representation you can see the equality of points evidently.

Note that, instead of computing $y=b*z^{-3}$ you can check $y*z^3=b$. In this state, you don't need to finding multiplicative inverse.

Also in powerful programs such as MAGMA, $z$ is equal to $1$, by default.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Simple $\ne$ cheap... $\endgroup$
    – poncho
    Commented Mar 20, 2017 at 19:00
  • $\begingroup$ Dear @poncho, I think that in Euclidean algorithm, simple and cheap are same, because of its low complexity. $\endgroup$
    – Meysam Ghahramani
    Commented Mar 20, 2017 at 19:07
  • $\begingroup$ So, an $O(n^3)$ algorithm is "cheap"? That's obviously a meaning of cheap that I'm not familiar with... $\endgroup$
    – poncho
    Commented Mar 20, 2017 at 20:16
  • 1
    $\begingroup$ @poncho, $O(n^3)$ or $O(n^2)$? Note that, $n$ is a number of digits of number, and we are talking about elliptic curves. Is it not cheap? I computed the inverse of $100000$ bit numbers in less that millisecond, by MAGMA. I'm sorry, maybe I don't know the meaning of cheap. $\endgroup$
    – Meysam Ghahramani
    Commented Mar 20, 2017 at 20:48
  • 1
    $\begingroup$ @deadalnix, If computing the multiplicative inverse is your problem, in projective coordination we don't compute any multiplicative inverse. for details you can see the page 88 of guide to elliptic curve cryptography, Darrel Hankerson, Alfred Menezes, Scott Vanstone. $\endgroup$
    – Meysam Ghahramani
    Commented Mar 20, 2017 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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