Hyperelliptic curves

Image001

Hyperelliptic curves are interesting for many reasons. The reason that we’re particularly interested in them at Voltage is that you can implement pairings using them and it might turn out that pairings on hyperelliptic curves can be more efficient than pairings on elliptic curves.

An elliptic curve is the set of points defined by an equation like

y2 = x3 + ax + b

This gives you a structure that’s much like a torus – a shape that has a single hole in it, like a doughnut.

A hyperelliptic curve is defined by an equation like

y2 = f(x)

where f is a monic polynomial of degree 2g + 1.

(There's really no reason to restrict the degree of f to being odd, and a polynomial of degree 2g + 2 will also work just as well. This makes some things trickier, so most people just stick to the odd degree case. One complication is that you actually get two different points at infinity instead of just one. More about that in a future post.)

When g = 1 this reduces to an elliptic curve, but the term “hyperelliptic curve” is usually reserved for the case where g is 2 or greater.

The number g defines the genus of the curve, a number which tells you how many holes the structure corresponding to an elliptic curve’s torus has. If the genus is 2, then the curve has a structure much like a doughnut with 2 holes, etc. The graph above is the graph of a hyperelliptic curve of genus 2.

Working with hyperelliptic curves causes some problems that aren’t there for elliptic curves. It’s possible to easily define a way to add points on an elliptic curve using the usual connect-the-dots algorithm, but this can’t be done for hyperelliptic curves. It’s possible, however, to add sets of g points on a hyperelliptic curve instead of single points. On a curve of genus 2, for example, we might add P = {P1,P2} to Q = {Q1,Q2} to get R = {R1,R2}. (Note that I've used brackets here instead of parentheses to make the notation more set-like. The order in which you list the elements isn't important for a set, and the order of the points isn't important here, either.)

The way that we add these sets of points is by thinking them as divisors, so that we're really adding divisors instead of adding points on a curve. The set of divisors on a curve, along with the rule that defines how to add them is called the Jacobian of the curve.

For a curve of genus g, we can reduce any divisor to one no bigger than one of the form

i=1:g(Pi) – g(O)

For a curve of genus g = 2, for example, we can reduce any divisor to one like

P = (P1) + (P2) – 2(O)

So that when we calculate something like

P + Q = R

for a hyperelliptic curve we actually calculating

(P1) + (P2) – 2(O) + (Q1) + (Q2) – 2(O) = (R1) + (R2) – 2(O)

How we find R1 and R2 from P1, P2, Q1 and Q2 is very similar to how we add points on an elliptic curve. In the case of an elliptic curve, we fit a line through two points, find the third point where the line intersects the curve, and reflect this point across the x-axis.

In the case of a hyperelliptic curve of genus 2, we fit a cubic polynomial to the points P1, P2, Q1 and Q2. We then find the two additional points where this polynomial intersects the curve and then reflect each of those points across the x-axis to get R1 and R2. Here’s a picture that shows what it looks like when we add the points P (the two red dots) and Q (the two green dots) to get R (the two black dots).

Image002

Because doing operations on hyperelliptic curves are defined in terms of divisors, it shouldn't be much of a surprise that pairings, that are also calculated using divisors, work just as well on hyperelliptic curves as they do on elliptic curves. That means hyperelliptic curves might end up be useful in pairing-based cryptography. If there's a good use for them, they'll probably appear in Voltage's products in the future. Right now, however, elliptic curves seem to be good enough.

Leave a Reply

Your email address will not be published. Required fields are marked *