0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ "(ECC) has been gaining a lot of popularity recently", not really, PQC (post-quantum cryptography) is. $\endgroup$
    – DannyNiu
    Sep 2 at 1:01
  • $\begingroup$ I don't understand what your question is. There are other asymmetric systems other than ECC. RSA is an example. PQC as DannyNiu mentioned has many other examples. If you just want to restrict yourself to curves, other sorts of algebraic curves can be used for cryptography, but they're not as efficient. In your last paragraph, you're mixing up cause and effect. That property is used heavily because ECC is useful. ECC isn't useful solely because of that property. $\endgroup$ Sep 2 at 1:15
  • 1
    $\begingroup$ In case your'd like to focus on ECC group law, some hyperelliptic curves have groups with strong DLP suitable for cryptography. Group law could be visualized with lines intersecting hyperelliptic curve graph, and group elements could be interpreted as tuples of points on the curve facilitating encoding. $\endgroup$ Sep 2 at 9:13
  • $\begingroup$ Another option might be DH-like key exchange with isogenies of supersingular elliptic curves. Start from Velu formula to understand the map operation. Get comfortable with the idea of a subgroup serving as a secret key, and a curve of a smooth order like $2^k 3^n$. Do your homework following SIKE/SIDH papers. $\endgroup$ Sep 3 at 17:50
6
$\begingroup$

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. General case addition on HEC

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ ..3: or they have something else, useful enough, complementing proper security. $\endgroup$ Sep 2 at 9:19
0
$\begingroup$

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

Source Wikipedia

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.

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