9
$\begingroup$

There are Chinese, French and NIST curves. There's a Million Dollar one. The BADA55 Research Team studied 1 million variants. Some are based on widely different formulae. Indeed there are entire suites of curves, and we're still actively developing more. It's all starting to look like a plate of spaghetti.

Why is there not just one or two curves that have been widely accepted as useful?

$\endgroup$
  • 6
    $\begingroup$ Relevant xkcd $\endgroup$ – puzzlepalace Apr 20 '17 at 21:08
  • $\begingroup$ Expand please. With cryptography, you can hash something. You can encrypt /decrypt something and you can generate random numbers. You can do combinations of these too. What are the other 999,996 curves for? $\endgroup$ – Paul Uszak Apr 20 '17 at 21:15
  • 1
    $\begingroup$ Elliptic curves are for public key cryptography (signing, key exchange, etc). The curve parameters define the group we're working in. Different standards define different groups. Similar to how there were several standardized groups for DSA / Diffie Hellman (where the group is $\mathbb{Z}_p^*$) $\endgroup$ – puzzlepalace Apr 20 '17 at 21:24
12
$\begingroup$

Why is there not just one or two curves that have been widely accepted as useful?

Several reasons; some of it is politics (for example, I suspect a good part of the reason behind national curves is, in fact, national pride), some of it is multiple teams working independently (for example, the Brainpool team, the NUMS time, the people behind the million dollar curves)

However, what can't be discounted is that people have different opinions on what makes a good curve. Here are some of the highlights:

  • What sort of prime is the curve based on. You can define an elliptic curve based on any finite field; recently, people have (mostly) settled on defining them based on large prime fields. For these curves, a large part of the expense is performing modulo operations based on the large prime. Now, if we select a prime with a simple binary representation, this modulo operation can be performed much faster than if we selected a random prime. On the other hand, some people note that these special primes make some blinding operations (important for side channel protection) harder, and so they do prefer random primes.

  • Lack of suspicious design decisions. If you look at the NIST curves, they are based on the equation $y^2 = x^3 - 3x + b$ where the value $b$ is a rather odd constant. Some people worry that $b$ might have been selected to induce an obscure weakness; that's a good part of the motivation for a number of the curves.

  • Curve equation. Traditionally, the curves have been based on the Weierstrass equation, $y^2 = x^3 + ax + b$ (for characteristic > 3), which can represent any curve (that is, if you have an EC curve formula, you can find a simple mapping from that to the equivalent Weierstrass curve). However, some people say that there are advantages to other curve equations (even if they can't represent arbitrary curves); Curve25519 is the most prominent example here.

On the other hand, if we look at what curves people actually use, there isn't that huge of a variety. We see P256 in wide spread use, we see some uses of P384 and uses of Curve25519 are becoming prominent. Every other curve would appear to be to be, at least, niche; used for an application or two, but not really that wide spread (at least, in my experience)

$\endgroup$
  • 2
    $\begingroup$ @fgrieu If your prime is sparse (i.e. the binary representation has mostly zeros), then the group order is sparse (by Hasse's theorem). To (additively) scalar blind, you add $r$ times the group order to your scalar. The size of $r$ is related to the sparseness of the group order (the more sparse, the larger $r$ needs to be). The larger $r$, the larger your blinded scalar, the more expensive your computation. $\endgroup$ – CurveEnthusiast Apr 21 '17 at 7:53
  • 1
    $\begingroup$ @fgrieu “these special primes make some blinding operations harder” (the misplaced parenthesis made me pause too). $\endgroup$ – Gilles 'SO- stop being evil' Apr 21 '17 at 8:17
  • $\begingroup$ Your 3 excellent bullet points are long and full of many details /variations about many curves. Is ECC still so fledgling that no standard (and safe /efficient) form has evolved yet? Might it within the foreseeable future? $\endgroup$ – Paul Uszak Apr 21 '17 at 13:31
  • $\begingroup$ @PaulUszak: there's no standard form that everyone agrees upon, in part because people have different opinions about the requirements. However, as I stated in my last paragraph, there really isn't that much variety that's used in practice... $\endgroup$ – poncho Apr 21 '17 at 13:53

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.