Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

up vote 17 down vote accepted

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.

share|improve this answer
    
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. –  stackuser Nov 6 '13 at 15:55
    
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. –  Samuel Neves Nov 8 '13 at 2:01
add comment

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.
share|improve this answer
    
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. –  stackuser Nov 5 '13 at 2:37
    
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. –  mikeazo Nov 5 '13 at 3:03
    
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. –  stackuser Nov 5 '13 at 3:46
1  
@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. –  Paŭlo Ebermann Nov 5 '13 at 7:31
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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