Asymmetric cryptosystems based on curves besides elliptic curves

Question

Elliptic curve cryptography (ECC) has been gaining a lot of popularity recently because of its security. I tend to find the process of encoding plaintext using ECC particularly interesting so I was wondering, has it been proven/disproven that you can find other curves based on which you can create cryptosystems? If it has been proven that such is the case, what kinds of curves?

Because not all curves have the same properties that elliptic curves do. For example, if you select any two points on an elliptic curve and draw a line through them, this line will intersect the elliptic curve at exactly one other point. This property is used heavily in ECC.

Answer 1

For example, if you select any two points on an elliptic curve and draw a line through them, this line will intersect the elliptic curve at exactly one other point. This property is used heavily in ECC.

What you describe here is the group operation on the elliptic curve. As pointed out already, hyperelliptic curves, which are a generalization of elliptic curves, are also useful for cryptographic applications.

A hyperelliptic curve of genus $g$ over finite field $\mathbb{F}_q$ can be described by an equation of the form $$ C: y^2 + h(x)y = f(x) $$ where $f(x)$ is a monic polynomial of degree $2g+1$, $h(x)$ is a polynomial of degree atmost $g$ with some additional conditions.

Elliptic curves can be viewed as hyperelliptic curves of genus $g=1$, you might recall that an elliptic curve in Weierstrass form is given by $ y^2 = x^3 + ax + b$, where you see that degree of polynomial in $x$ is indeed $2g +1 = 3$.

Here, I would like to focus on hyperelliptic curves of genus $2$. I will explain in the end why this particular case is an interesting alternative to ECC. If the characteristic of finite field $\mathbb{F}_q$ is not $2$, then HEC of genus $2$ is given by the equation $$ y^2 = x^5 + b_4x^4 + b_3x^3 +b_2x^2 + b_1x + b_0, \quad b_i \in \mathbb{F}_q .$$ Do we have a group structure with respect to points on the curve? The answer is no. But roughly speaking, we can describe a group structure using "pairs of points" on the curve.

In the above picture, the blue curve is the unique cubic passing through $P_1, P_2, Q_1, Q_2$ (determined using interpolation).

Here you might ask yourself the following questions:

1. What guarantees that a line intersects an elliptic curve at three points?
2. How many intersection points does a line have with a hyperelliptic curve of genus $2$?

The answer lies in Bezout's theorem for plane algebraic curves. To understand the group structure associated to hyperelliptic curves (known as Jacobian of hyperelliptic curve), you will need some understanding of algebraic geometry as well. Here is a good starting point for hyperelliptic curves.

HEC of genus $2$ are most interesting for cryptographic applications based on Discrete Log Problem, since for higher genus curves, you have index calculus attacks that can be used to solve the DLP.

See this paper for efficient arithmetic on HEC of genus $2$.

Answer 2

There is a false premise in the question - that is:

Arbitrary curves may be useful in cryptography. Which I infer from the quote in the question:

has it been proven/disproven that you can find other curves based on which you can create cryptosystems

To tell the truth, it hasn't been disproven. But the reason ECC can be used in cryptography, is that it can serve as a compact drop-in replacement of discrete-logarithm-based cryptography based on prime-order finite fields (because point arithmetic forms a group).

So now, if we want to show that non-elliptic curves can be used in public-key cryptography, then we must either show that

1. they also form a group with no more weakness than ECC, or
2. they can be used differently and admit no worse security foundation than ECC.

And ideally, they're more efficient than ECC.

Answer 3

Besides Elliptic Curves, conic sections (over an appropriate finite field $\mathbb F_p$) also provide a group structure.

Therefore they could be used in Diffie-Hellman key exchanges. Note, however, that these curves do not seem secure to use for cryptography since the discrete logarithm problem appears easy to solve in the group of points over these curves. Generally, the DLP can be reduced to the underlying field.

For a concrete example: this paper studies the curve with equation $x^2 - Dy^2 = 1$, for an appropriate choice of $D$. in other words, this is the set of solutions to this equation over $\mathbb F_p$. It is shown that the discrete log is easy.