What is so special about elliptic curves?

Question

There seems to be sources like this, this also, and some introductions that discuss elliptic curves in general and how they're used. But what I'd like to know is why these particular curves are so important in cryptography as opposed to, let's say, any other polynomial degree $\gt$ 2 which you can then mod over some group. It seems like once a modulus is applied then other function types should be acceptable as well.

It seems even less intuitive when just looking at the bubble vs curve as here:

Since there are other curves (let's say anything from a sin wave to the $x^3 + x$ or even just some unusually shaped contour) that could do the job. It seems like they would provide much more surface area to get a larger space in $\mathbb{Z}_p$ or really just more possible combinations of connecting lines from some arbitrary $P$ and $Q$ to get $R$ as opposed to something as restrictive (on the graph) as beginning from some bubble (which would seem to unnecessarily reduce the possible combinations) and then use a modulus to implement the discrete logarithm problem.

Sorry if this seems a little naive of a question, I'm trying to write an implementation right now and just to understand it fully even if that means asking something that is taken for granted. Perhaps just walking through a simple example (most of the ones I've searched are anything but), just a few sentences, would be rather helpful, from "A wants to talk to B" all the way up to "now E can't listen in between A and B".

EDIT:

So it seems like this is the version of elliptic curves over a finite field:

Yes that looks pretty random. But I'm still not really seeing why they are the only equations that have cryptographic significance. It's difficult to imagine that if you simply took some other higher degree equation and applied modulus (to place within a group), then it seems like it would make sense that you'd get something that's also comparatively random.

Answer 1

Elliptic curves are not the only curves that have groups structure, or uses in cryptography. But they hit the sweet spot between security and efficiency better than pretty much all others.

For example, conic sections (quadratic equations) do have a well-defined geometric addition law: given $P$ and $Q$, trace a line through them, and trace a parallel line that goes through the identity element. Here's a handy picture for one of the best known conics, the unit circle $x^2 + y^2 = 1$:

If you take the identity element to be $(1, 0)$, then you get the very simple addition formula (modulo your favorite prime)

$$ (x_3, y_3) = (x_1x_2 - y_1y_2, x_1y_2 + x_2y_1)$$

This is much faster than regular elliptic curve formulas, so why not use this? Well, the problem with conics is that the discrete logarithm in this group is no stronger than the discrete logarithm over the underlying field! So we would need very large keys, like prime-field discrete logarithms, without any advantage. That's not good.

So we move on to elliptic curves, which do not have reductions to the logarithm on the underlying field.

But wait, we can generalize elliptic curves to higher degrees. In fact,

$$ y^2 = x^{2g+1} + \ldots $$

when $g > 1$ and some restrictions are respected, is called a hyperelliptic curve, and we can work on it too. But for these curves there does not exist a nice geometric rule to add points, like in conics and elliptic curves. So we are forced to work in the Jacobian group of these curves, which is not the group of points anymore, but of divisors (which are kind of like polynomials of points, if that makes any sense). This group has size $\approx p^g$, when working modulo a prime $p$.

Hyperelliptic curves do have some advantages: since the group size is much larger than the prime, we can work modulo smaller primes for the same cryptographic strength. But ultimately, hyperelliptic curves fall prey to index calculus as well when $g$ starts to grow. In practice, only $g \in \{2,3\}$, i.e., polynomials of degree $5$ or $7$ offer similar security as elliptic curves. To add insult to injury, as Watson said, the addition formulas also get much more complicated as $g$ grows.

There are also further generalizations of hyperelliptic curves, like superelliptic curves, $C_{a,b}$ curves, and so on. But similar comments apply: they simply do not bring advantages in either speed or security over elliptic curves.

Answer 2

Elliptic curves have a number of nice features that make them good for cryptography. One could write a whole book on the topic (as some have), so I'll highlight a few points.

1. The points on an elliptic curve over a finite field forms a group. The same is not true for the ideas you mentioned.
2. Discrete log on many of these EC groups is hard. In fact, there are no sub exponential algorithms to solve DLP in these groups as there are for other groups we often use in crypto (e.g., $\mathbb{Z}_p$). This means we have smaller key sizes and faster operations.
3. Elliptic curves have been successfully applied to cryptanalytic problems such as factoring.
4. We have been able to do some other cool things with elliptic curves such as pairings that we haven't gotten in any other setting.

Answer 3

You are not wrong: given any variety $V$, we can form the Jacobian $J(V)$ as an abelian variety, in particular an abelian group over which we could use the Diffie-Hellman problem. However, there are several details that get in the way of doing this. First, it is necessary to compute the order of the Jacobian. We only know how to do this for elliptic curves. Secondly for higher genus there are various reductions to the case of lower genus. Lastly the greater the genus, and hence degree, the more complex the formulas that have to be used to do these calculations. The Handbook of Elliptic and Hyperelliptic Curve Cryptography is an excellent reference on these issues.

Answer 4

The addition of points on elliptic curves has a different definition that is much more natural, can be defined for any curve, and makes it more obvious why it is interesting for elliptic curves specifically.

For any variety (curves, surfaces, etc etc) you can define something called the divisor class group, whose elements are just free sums of a finite number of points, modulo sums of points given by zeroes and poles of rational functions (with their multiplicities).

For any flat projective space of any dimension this is the trivial group since a rational function can have any finite number poles and zeros wherever, while for a general surface this group will be larger the more "holes" the original surface has, and the theorem that quantifies that by relating the number of rational functions to topology is called the Riemann-Roch theorem.

By sheer miracle, it turns out that for Elliptic curves (i.e. curves of genus one, i.e. that have one "hole" and are topologically like a torus), the Riemann-Roche theorem implies there is a bijection between points on the curve and the divisor class group that is uniquely defined if you pick a specific point to be the identity, so that each curve point can be mapped to an element of the divisor class group.

The specific cubic equations that you have seen are important for specific calculations but they don't tell you why the thing works. There's a number of ways in which you can embed an elliptic curve in projective space, and the cubic form is convenient for calculations as the multiplication happens to have a nice form in terms of intersecting lines. However, the actual group law actually exists because of the Riemann-Roch theorem, and the important part is that you have an algebraic curve that is topologically like a torus.

Over the complex numbers specifically, it's also possible to intuitively explain that torus topology -> definable addition law because you can parametrize those curves with elliptic functions which are doubly periodic, much like how you can parametrize a circle with a periodic function like e^ix, which maps addition of points to addition on the complex numbers modulo the periods.