0
$\begingroup$

According to my measurements and to this work, it seems that operations, for example scalar multiplication, are more expensive in larger groups. If I have, for example, an 80-bit elliptic curve and an 384-bit elliptic curve, then the difference is very big:

  • 80-bit curve: 10ms per 1 multiplication on average
  • 384-bit curve: 501ms per 1 multiplication on average

I don't know if it's related, but the method for multiplication is probably wNAF.

Question: Why basic operations are more expensive on larger groups?

$\endgroup$
2
$\begingroup$

There are many different flavors of elliptic curves and coordinate systems for them with different costs for computing addition or scalar multiplication. You can find cost estimates for many of these at the Explicit-Formulas Database (EFD), and measurements from SUPERCOP at https://bench.cr.yp.to/.

Certain curves like Curve25519 in Montgomery form $y^2 = x^3 + 486662 x^2 + x$ were designed to admit fast $x$-restricted scalar multiplication, i.e. to compute $x([n]P)$ given $n$ and $x(P)$, as is sufficient for applications like Diffie–Hellman; software to compute it will consequently run much faster than software to compute scalar multiplication of a generic short Weierstrass curve of comparable size. Certain curves also admit an Edwards or twisted Edwards form like $-x^2 + y^2 = 1 - (121665/121666) x^2 y^2$, which also admits much faster addition formulas than generic short Weierstrass curves, but only those with cofactor at least 4 can have this form.

The cost estimates of the EFD are all written in terms of numbers of additions, multiplications, etc., in the underlying field $\mathbb F_q$. Certain fields like $\mathbb F_{2^{255} - 19}$ are designed to admit constant-factor speedups for fast arithmetic in software by being just below a power of two, but largely, the number of bit operations to compute addition in $\mathbb F_q$ grows as $O(\log q)$, and to compute multiplication, $O(\log^2 q)$, or $O(\log^{\log_2 3} q)$ if you use Karatsuba's algorithm, etc.

There are no substantive shortcuts around these bit operation costs in general. Of course, in special cases, curves may admit a fast endomorphism like Koblitz curves, FourQ, etc., which can be used to speed up scalar multiplication on those curves.

Finally, Hasse's theorem bounds the distance between the size $q$ of the underlying field and the size $\ell$ of the group, which is also the size of the scalar ring. So for larger fields, the scalars may be larger (unless for some reason you're safely working in a subgroup), and to have larger scalars, the field must be larger. Security is generically limited by the cost $O(\sqrt\ell)$ of Pollard's $\rho$ to compute discrete logs in the group, so if you want Pollard's $\rho$ to cost ${\sim}2^{128}$ bit operations you must choose a group with $\ell \sim 2^{256}$.

$\endgroup$
  • $\begingroup$ Hi, you just answer every question :) Thanks a lot for exhaustive answer. It is what I wanted to know. But if I can one more question - how do you know that the number to compute multiplication is O(log^2 n)? $\endgroup$ – Daniel Herbrych Feb 27 at 0:06
  • $\begingroup$ @DanielHerbrych If you do $n$-digit long multiplication by hand using the usual method, you need to compute $n^2$ digit products: you need to multiply every digit by every other digit. E.g., $$(a r + b) \cdot (c r + d) = ab r^2 + (ad + bc) r + bd,$$ which requires computing the $2^2$ digit products $ab, ad, bc, bd$; here $r$ is the radix, e.g. $10$ or $2^{32}$. Well, not necessarily need: the Karatsuba algorithm uses fewer digit multiplications, at the cost of more additions, hence $O(n^{\log_2 3})$ instead of $O(n^2)$. Point is: cost grows faster than linearly with $n = \log_r q$. $\endgroup$ – Squeamish Ossifrage Mar 23 at 9:25
1
$\begingroup$

A somewhat generic answer, given the question is quite generic.

In cryptography, groups are usually chosen such that they have no large subgroups or other substructures which would speed up attacks.

This also impacts computation speed, in the sense that group operations cannot necessarily be implemented to run faster, by use of such substructures.

And a larger group takes more memory to store as well, which also has an impact.

$\endgroup$

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.