Skip to main content
eliptic -> elliptic
Link
Maarten Bodewes
  • 97.1k
  • 14
  • 171
  • 328

Is there an economic way to check if an elipticelliptic curve point in jacobianJacobian coordiate is the same as a compressed point

Tweeted twitter.com/StackCrypto/status/844879721494122496
Source Link
deadalnix
  • 203
  • 1
  • 6

Is there an economic way to check if an eliptic curve point in jacobian coordiate is the same as a compressed point

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.