2
$\begingroup$

How does performing scalar multiplication on an elliptic curve compare to exponentiation in a multiplicative group modulo a prime?

I.e. on a given elliptic curve of size $|t|$, what's the complexity of computing $kP$ with respect to $|k|$ and $|t|$?

And in comparison, what's the computational complexity of a modular exponentiation of form $g^a \bmod p$ with respect to $|g|=|p|$ and $|a|$?

It would already be a big help to know the answer for double-and-add and square-and-multiply respectively.

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Do you have any calculations for double and add or square and multiply? A good starting point would be to find out what the cost of double and add is for addOne co-ordinates and compare that to square and multiply. Then analyse each formulae to see how the cost rises when the respective parameters are increased. For example, how does the double and add formula increase when t increases. $\endgroup$ – user69644 Jul 10 '19 at 13:41
  • $\begingroup$ Although not mentioned in your question, I’m guessing you may decide to use the method which is the cheapest. If so l, you may want to compare both methods with the same security parameter. $\endgroup$ – user69644 Jul 10 '19 at 13:44
  • $\begingroup$ How many squarings do you need to calculate $g^(2^t)$? When do you do/what triggers a multiplication in the square-and-multiply algorithm? $\endgroup$ – j.p. Jul 11 '19 at 6:39
  • $\begingroup$ The security parameter is a good point, although the operations seem to be equally expensive, they will be performed on different sized security parameters for the same security. Thanks for the hint! $\endgroup$ – Evolir Jul 12 '19 at 9:30
2
$\begingroup$

If you only care about computational complexity, it's similar:

  • In ECC: the number of double-and-add steps is proportional to $O(|k|)$ (one double every bit, one add for each $1$ bit, in the non-windowed algorithm). Each double/add is a sequence of a constant number of field multiplications, squarings, additions and subtractions. Multiplication and squarings are the expensive ones, and using Karatsuba algorithm, they are $O(|t|^{1.58}$). Therefore the result is $O(|k||t|^{1.58})$.
  • Modular exponentiation is the same. Square-and-multiply is $O(|a|)$. Each square/multiply is $O(|p|^{1.58}$). Therefore the result is $O(|a||p|^{1.58}$)

Of course, if you need to be more precise, you'll have to decide on a specific point multiplication / modular exponentiations algorithms, since there are ones that use windows and precomputation tables; and in ECC, also specific formulas for point addition and doubling.

Improve this answer
$\endgroup$
  • $\begingroup$ The way you explain it makes me think I should've come up with it myself. Thank you! $\endgroup$ – Evolir Jul 12 '19 at 9:32

Your Answer

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

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