33
$\begingroup$

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: enter image description 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:

enter image description here

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.

$\endgroup$

4 Answers 4

34
$\begingroup$

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$:

enter image description here

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.

$\endgroup$
2
  • 3
    $\begingroup$ So elliptic curves are like the sweet spot over a continuum of equations that might be used over a group. That continuum seems like it ranges from "way too expensive for computation" (hyper/super elliptic curves) to "the DLP is not difficult enough" (putting P and Q over a conic section or circle). Although your conic section made me wonder why a sphere in $R^{3}$ wouldn't work, too expensive perhaps. +1 and accepted. $\endgroup$
    – stackuser
    Nov 6, 2013 at 15:55
  • 4
    $\begingroup$ A sphere ($x^2 + y^2 + z^2 = 1$) would still not be secure; however, if you intersect two quadric surfaces (i.e. surfaces defined by quadratic polynomials) you actually can get a secure curve, which --- guess what --- is actually an elliptic curve! The Jacobi intersection curves are an example of this. $\endgroup$ Nov 8, 2013 at 2:01
8
$\begingroup$

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.
$\endgroup$
5
  • $\begingroup$ 1. Wouldn't any curve be able to form a group if some modulus is applied? Many ec's don't even have the bubble unless $a \lt 0$ and $b \lt 1$ so it seems like any other wavy line in that case. $\endgroup$
    – stackuser
    Nov 5, 2013 at 2:37
  • $\begingroup$ The ECs that you see that look nice are over the reals. The elliptic curves over finite fields do not look that way at all. In fact they look pretty random which is another reason they are good for cryptography. AFAIK other functions over finite fields do not form a group. $\endgroup$
    – mikeazo
    Nov 5, 2013 at 3:03
  • $\begingroup$ OK so it makes more sense now, after seeing the before and after transformation of it going over the finite field (like caterpillar to butterfly). I added an EDIT as to what I'm still not really getting about why the ec's are so special in that way. It just seems like applying modulus (placing within a group) most equations with 2 higher degree variables would have a comparable effect to create something random enough for cryptographic purposes. $\endgroup$
    – stackuser
    Nov 5, 2013 at 3:46
  • 3
    $\begingroup$ @stackuser While you can define some kind of "addition" for most types of curves using a similar geometric construction like the one for elliptic curves, it is not automatically given that this operation is associative and has neutral and inverse elements, i.e. forms a group. $\endgroup$ Nov 5, 2013 at 7:31
  • $\begingroup$ Neither points itself, nor "other functions" form a group; points with an operation do, and that operation can be creative subject to associativity, neutral and inverse as Paulo Ebermann say. $\endgroup$ Feb 7, 2018 at 23:17
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 there 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-Roche 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.

$\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.