-4
$\begingroup$

What would happen if I performed Elliptic Curve multiplication on some random point within the FiniteField that wasn't actually on the curve? I assume that I would get a point in return but would that point be on the curve? Is it possible to use this for Elliptic Curve Cryptography?

$\endgroup$
1
  • 5
    $\begingroup$ What exactly do you mean by "perform elliptic curve multiplication" on a point? $\endgroup$ Apr 29, 2015 at 0:05

1 Answer 1

3
$\begingroup$

I assume you mean that you will plug the $x$ and $y$ values into the addition formula. The answer is no, in general you will not get a point on the curve. And more importantly, the associative law won't be valid if you try adding three points in different orders. It might have been a good idea to try a few examples before asking a question on MathOverflow, which is why your question is likely to be closed.

However, one can take a random value for the "denominator" of the x-coordinates of $P$, $2P$, $3P$, and $4P$ (without first specifying the elliptic curve) and then use the composition law for the denominators, which is a non-linear recursion leading to what's known as an elliptic divisibility sequence $W_1,W_2,\ldots$. There is then an algorithm to compute $W_n$ is time $O(\log n)$, analogous to the double-and-add algorithm. And these sequences can be used for cryptography (both for Diffie-Hellman type constructions, I think, and also certainly for computing the Tate pairing).

$\endgroup$

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