Suppose the tuple $(P, a, Q)$ is given, where $P$ and $Q$ are points on an elliptic curve (I'm more interested in Montgomery curves but other curves are also fine), $a$ is a scalar and the notation $[a]P$ is the scalar multiplication. Is there a way to quickly check whether $Q = [a]P$? Specifically, is there a way to do this check that is faster than computing the scalar multiplication and then checking for equality?

  • 3
    $\begingroup$ Are there more information that can be used ? For example, do you need to check 1 value of 'a' or multiple ? P is a fixed as a global constant ? Q ? $\endgroup$
    – Ruggero
    Jul 13, 2022 at 12:37
  • $\begingroup$ I think the best you can do is apply a fast multiplication algorithm. You cannot avoid the operation and of course you cannot avoid the equality check. $\endgroup$
    – tur11ng
    Jul 13, 2022 at 15:38
  • $\begingroup$ P and Q are not constants, the "checking" algorithm doesn't know them in advance. Also a can be seen as something sampled uniformly at random, so it's very unlikely to be 1. The only other thing might help is the "checking" algorithm could take some auxillary information that might help it to do the computation. But this auxillary information cannot be trusted (e.g., auxillary information might say this triple is correct then the checking becomes trivial) $\endgroup$
    – lamba
    Jul 13, 2022 at 21:57
  • $\begingroup$ I think @Ruggero was asking whether more than one scalar value $a$ would be scalar multiplied with the same value of $Q$, in which case you could use precomputations in order to accelerate the multiplications. $\endgroup$
    – knaccc
    Jul 14, 2022 at 0:47
  • 1
    $\begingroup$ Thanks @knaccc, that was my point, but OP made it clear that the checking algorithm doesn't know them in advance. I believe at this point there are no other option than a full variable base scalar multiplication algorithm (with the final affine conversion) $\endgroup$
    – Ruggero
    Jul 14, 2022 at 7:51


Your Answer

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

Browse other questions tagged or ask your own question.