Elliptic Curves: Cheat Sheet

Elliptic curves are special mathematical objects commonly defined by a cubic equation of the form $y^2 = x^3 + ax + b$, where $a$ and $b$ are constants. Thanks to their mathematical properties, such as the ability to perform efficient arithmetic operations and the difficulty of solving discrete logarithm problem (DLP) on them, elliptic curves became ubiquitous in modern cryptography. Today elliptic curves can be found in digital signature schemes (DSA), key exchange mechanisms (KEM), zero knowledge proofs (ZKP), multi-party computation (MPC), and more.

The goal of this short post is to provide a brief overview of parameters that collectively specify an elliptic curve and give a somewhat opinionated classification of existing elliptic curves.

Anatomy of elliptic curves

The most defining characteristic of elliptic curves is their endomorphism ring, which is also the most abstract one. Namely, it's a set of mathematical operations that can be performed on the curve. These operations include point addition, scalar multiplication, and it gives information about the properties of the curve.

Order $n$ is the maximum number of points on the curve and is sometimes called cardinality.

Base field $\mathbb{F}_q$ of an elliptic curve is the field over which the curve is defined. The base field size $q$ thereby defines the number of elements of the finite field $\mathbb{F}_q$.

Scalar field $\mathbb{F}_r$ is the field of scalars used in the operations performed on the curve, such as point addition, scalar multiplication, and pairing. The scalar field size $r$ is also the size of the largest subgroup of prime order. Interestingly, the Elliptic Curve DLP (ECDLP) of an elliptic curve is only as hard as that curve's largest prime order subgroup, not its order. However, when curve's order is prime, its largest prime subgroup is the group itself, so $r = n$.

The following are three parameters that give a good taste of the curve's security and performance:

• Relative parameter $\rho = log\;q/ log\;r$ measures the base field size relative to the size of the prime-order subgroup on the curve. Small $\rho$ is desirable to speed up arithmetic on the elliptic curve.
• Cofactor $h = n/r$ measures curve's order relative to its largest prime subgroup. Cofactor of prime-order curves is always equal to 1. There's a trade-off where curves with cofactor tend to have faster and simpler formulas than that of prime-order curves, but are also more likely to be vulnerable to certain attacks like malleability.
• Trace of Frobenius describes the size of a reduced curve and can be defined as $q + 1 - r$. It's used to better estimate the security of the elliptic curve and is useful when finding new curves with desirable properties.

The embedding degree is the smallest integer $k$ that lets you transform an instance of the ECDLP over an elliptic $E(\mathbb{F}_q)$ into an instance of the DLP over the field $\mathbb{F}_{q^k}$. It's particularly important because the best known ECDLP attack $O(\sqrt{n})$ is Pollard's rho, while the best DLP attack is Index Calculus being sub-exponential in the field size. This kind of reduction is possible with pairing-friendly curves, so their $q^k$ must be significantly larger than order $n$. When $k > 1$ we say that curve is defined over extension field of size $q^k$.

Security bits $s$ measure the difficulty of solving the DLP on a curve. For plain curves $s$ is roughly $log_2\;r$. For pairing-friendly curves, $r$ must be selected such that $log_2\;r \geq 2s$ because of Pollard’s rho algorithm, but due to ambiguity of Index Calculus attack complexity, estimating $s$ isn't as trivial: $2^v \cdot e^{\sqrt[3]{c/9\cdot ln(kq)\cdot ln(ln(kq))^2}}$ where the constants $c = 32$ and $v = −7$ (source).

Primitive point $G$ is a generator of the group $\mathbb{F}_{q}$: all elements of the group can be expressed as $G+G+...+G$ (up to $q$ times). If a curve's order is prime, then all its points (except the point at infinity) are primitive.

Taxonomy of elliptic curves

There are many ways to classify elliptic curves: by their algebraic structure, geometric shape, cryptographic properties, security levels, etc. Let's start by looking at the properties of their endomorphism rings.

By the properties of their endomorphism rings

Ordinary elliptic curves have the endomorphism ring that is isomorphic (equivalent) to the ring of integers of a number field, i.e. all points are in the set of real integers.

Supersingular curves are elliptic curves whose order is not divisible by the characteristic of the field (the smallest positive integer $m$ such that for all elements $a$ in the field, $a+a+...+a$ ($n$ times) = 0).

Complex multiplication (CM) elliptic curves are curves whose points are created by multiplying their generator point on the complex multiplication constant. They naturally have a large number of points and can be used to generate large prime order subgroups.

Pairing curves are defined by a pair of elliptic curves $\mathbb{G}_1$, $\mathbb{G}_2$ and a bilinear map between their respective groups of points that map their points $\mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$. Curves with a small embedding degree $k < 40$ and a large prime-order subgroup $\rho \leq 2$ are called pairing-friendly curves.

By their definition form

Weierstrass curves are defined as $y^2 = x^3 + Ax + B$. This is arguably the most common form for elliptic curves. Weierstrass curves initially lack full addition and were slower, but the gap has closed over time. Examples is BLS family (BLS12-381, BLS12-377).

Montgomery curves are defined as $By^2 = x^3 + Ax^2 + x$. These curves are extremely efficient for elliptic curve multiplication (ECM) by being deliberately tailored for use with the Montgomery ladder. Using this algorithm it's possible to multiply any two points without failure cases. Although there are more performant methods to multiply a variable point on a fixed one, the Montgomery ladder remains practically unbeatable for multiplying two arbitrary points. A notable example is Curve25519.

Edwards curves are defined as $Ax^2 + y^2 = 1 + Dx^2*y^2$. Such curves gained huge popularity because were the first to implement full addition law, i.e. allowed to efficiently add any two points without failure cases. Complete addition formulas can simplify the task of an ECC implementer and, at the same time, can greatly reduce the potential vulnerabilities of a cryptosystem. An example of an Edwards curve is Ed25519.

Twisted Edwards curves are the generalization of the Edwards curves that include a special affine transformation which makes the curve "twisted" and thereby makes it more efficient for certain mapping operations such as the Elligator map and hash to curve. Interestingly, curves of this form are birationally equivalent to Montgomery curves, so it's common to find them by first specifying the Montgomery and then transforming it into Twisted Edwards form. Notable examples are Ed-on-BLS12-381 aka JubJub and Ed-on-BN254 aka Baby-Jubjub.

Summary

Elliptic curves are defined over two fields of finite order: the base field is used to represent points on a curve while the scalar field allows performing scalar multiplication on those points.

Characteristics such as relative parameter $\rho$, cofactor, and trace can say a lot about the curve's security and performance. Estimating security bits of a given curve is generally trivial for plain curves but can be quite troublesome for pairing-friendly curves.

Elliptic curves can be classified by their endomorphism rings or by their definition form. There exist ordinary, supersingular, CM, and pairing-friendly curves all having a different endomorphism ring structure. When it comes to defining elliptic curve equations the most popular ways are Weierstrass, Montgomery, Edwards, Twisted Edwards forms.