2 posts tagged with "ZK"

Elliptic curves form a basic building block for all kinds of complex cryptographic machinery: digital signature schemes, key exchange mechanisms, zero knowledge proofs, multi-party computation, etc.

While all curves have a similar mathematical structure they can have wildly different properties in terms of security, performance, and supported arithmetic. With the increasing adoption of zero-knowledge cryptography, finding and exploiting such differences becomes increasingly prominent. Thus, the search for new elliptic curves is an active area of research in cryptography. The goal is to find curves that offer higher security, more efficient arithmetic operations, and are widening the scope of cryptographic applications.

This post goes over different methods for constructing elliptic curves, some potential applications, and some practical consideration for application-specific curve development. The reader is assumed to have a basic understanding of elliptic curve cryptography. If not consider checking elliptic curves cheat-sheet first.

Why search for new curves?​

As with many things in modern cryptography, it is the rise of blockchains that sparked so many innovations related to elliptic curves as well as zero-knowledge cryptography, which subsequently pushed even more researchers to actively search for new elliptic curves. The applications described here would therefore be closely related to Web3 and ZK domains.

Platform-constraint arithmetic circuits​

In ZK systems computation is expressed as arithmetic circuits that in turn perform their operations on a finite field $\mathbb{F}_r$. This field corresponds to a scalar field of an elliptic curve whose base field is then used by the verifier in the proof verification algorithm. A verifier can be a person whom you need to prove some statement, but more commonly the verifier would be a smart contract. Blockchains that host these contracts usually support a fairly limited number of elliptic curves. Ethereum for example only has a precompiled contract for BN256. This can become a significant limitation when an in-circuit computation itself contains elliptic curve operations. Think of signature verification; checking that encrypted message has some properties, or even verifying another SNARK aka recursive proofs composition, which we discuss later.

An example to note is related to the StarkNet platform and Cairo language. The core technology powering these two is STARKs (no surprise). What's interesting is that, unlike other proof systems, STARKs only require a small prime field to operate, so researchers at Starkware invented a special STARK curve that has a very small prime field - 64 bytes. As a result, implementing cryptographic schemes over the standard curves (e.g. ECDSA over Secp256k1) would be wasteful. Unsatisfied with the status quo Mikerah from HashCloak resolved to find a new Cairo-friendly curve named Starkjub.

The solution to this kind of problem is quite simple, in fact, it's the oldest trick in the book. One can pick another curve $E'$ whose base field matches the scalar field of a curve $E$ used by the verifier. This offers a great alternative to simulating foreign fields with available (unfriendly) one, referred to as non-native arithmetic. Commonly, curves found with such intent have a twisted Edwards form. They are defined over a particular form of equation, $ax^2 + y^2 = 1 + dx^2\cdot y^2$, and are known for their efficient point addition. Many such curves were found in recent years. Some of them are given cute names like JubJub (Ed-on-BLS12-381) and funny pictures to be more memorable.

JubJub (left) and Bandersnatch (right)

Application-constraint arithmetic circuits​

For some applications the aforementioned curve substitution is impossible. Think of a cross-chain bridge where a smart contract on the destination chain needs to verify signatures of the source blockchain. Another example is identity-based encryption (IBE) like the one used in the tlock scheme to achieve practical time-lock encryption facilitated by Drand threshold network. Recently I've set to make such encryption verifiable and quickly realized that performing arithmetic on BLS12-381, which Drand operates on, is very inefficient with existing tools. Search for a better alternative brought me into this rabbit hole.

The discovered solution is the opposite of the one we've just discussed. Here a curve must be picked, whose scalar field matches the projective curve's base field. Depending on the proving system, there can be another important requirement: systems that rely on KZG commitment scheme, such as Groth'16, PLONK require pairing-friendly curves to operate. The reason is that KZG proof verification algorithm requires elliptic curve point multiplication which is not allowed in traditional ECC. However, when both points are from pairing-friendly curve $\mathbb{G}_1$ and $\mathbb{G}_2$ and there exists a bilinear map between their respective groups of points, then it's possible to map these points into a target group $\mathbb{G}_T$ point, which acts as a product $\mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$.

The known methods for finding pairing-friendly curves whose scalar field embeds other curve's base field are Cocks–Pinch (CP) and Dupont-Enge-Morain (DEM), and we will be taking a closer look at them later in the article. In the previously mentioned time-lock IBE project, the Cocks-Pinch method was used to find a curve that embeds BLS12-381 scalar field, which I named YT6-776 curve aka "Yeti".

Recursion substrate for ZKPs​

Recursive ZKPs is a short way of saying that one proof attests to the validity of another one, i.e. "proof of a proof". For this, an arithmetic circuit of the outer proof must implement the verification algorithm of an inner proof. If both outer and inner proofs are based on the same proving system we say it's a recursive proof composition, otherwise just a proof composition. When proof verifies a proof just once or a bounded number of times then it's one-layer or $N$-layer recursion respectively.

The reason why recursion is challenging relates closely to the aforementioned problems. Instead of repeating myself, I will quote an explanation for the "Zexe: Enabling Decentralized Private Computation" paper, which I recommend for those who'd like to go beyond the concepts mentioned in this article.

The way to approach recursive proof composition would vary depending on the desired type. For bounded recursion, the $n$-chain of curves would be sufficient to compose proofs up to $n$ levels, otherwise the cycle of curves must be used. A pair of curves that satisfy $r_1 = \#E_2(\mathbb{F}_2) \land r_2 = \#E_1(\mathbb{F}_1)$ forms a 2-cycle. During proofs generation, one would have to alternate the instantiation of the proofs with two curves of the cycle so that their fields "match up". Only prime-order curves can form cycles and it's generally much harder to find cycles of pairing-friendly curves. Ideally, both curves in the cycle should have the same embedding degree $k$ and same 2-adicity, like Pasta curves and unlike Tweedle curves.

The only known pairing-friendly cycles are formed by alternating MNT (Miyaji-Nakabayashi-Takano) curves of embedding degrees 4 and 6 using [KT07] method. Note, that due to low embedding degrees, secure curves in the MNT family must be constructed over very large (1024-bit) fields, which significantly downgrades the performances.

Methods for constructing elliptic curves​

Complex multiplication method​

Complex multiplication (CM) method is used to generate an equation for a curve with some given properties such as order $n$, embedding degree $k$, trace $t$, and fundamental discriminant $D$.

To construct an elliptic curve over $\mathbb{F}_q$ with $n$ points:

• Start by choosing a prime power $q$ and integers $n, D, k, t$.
• Find an integer solution $(x, y)$ for the CM equation of form $Dy^2 = 4q - t^2 = 4hr − (t − 2)^2$.

To construct family of curves $\mathbb{F}_q(x)$:

• Parametrise $t,r, q$ as polynomials: $t(x),n(x), q(x)$.
• Find all solutions $(x, y)$ to the CM equation in the polynomial form $Dy^2 = 4q(x) - t(x)^2 = 4h(x)r(x) - (t(x) - 2)^2$.

The output is coefficients $A$ and $B$ for the elliptic curve equation of the Weierstrass form ($y^2 = x^3 + Ax + B$).

Cocks-Pinch method​

Cocks-Pinch (CP) method is used to construct pairing-friendly elliptic curves with arbitrarily chosen embedding degree; curves constructed using this method have $\rho$-value of approximately 2.

To use CP method:​

• Choose a positive integer $k$ and a integer $r$ congruent to 1 modulo $k$, and fundamental discriminant $D$.
• Find trace $t$ and prime $q$ such that the CM equation is satisfied.

The output is a prime integer $q$ such that there exist an elliptic curve $E$ over $\mathbb{F}_q$ with an order-$r$ subgroup and embedding degree $k$. If fundamental discriminant $D \le 10^{12}$ then $E$ can be constructed using the CM method.

When to use CP method:​

• For embedding known curve's base field into new curve's scalar field.
• When minimising $\rho$ is not a priority.

Dupont-Enge-Morain method​

Dupont-Enge-Morain (DEM) method is similar to CP in that it produces elliptic curves with an arbitrary embedding degree, but in doing so it computes trace $t$ and subgroup order $r$ simultaneously using resultants.

To use DEM method:​

• Choose embedding degree $k$ and fundamental discriminant $D$.
• Find $t$ and $r$ simultaneously using resultants, then find cofactor $h$ such that CM equation is satisfied.

The output is prime integers $q$ and $r$ such that there exist an elliptic curve $E$ over $\mathbb{F}_q$ with an order-$r$ subgroup and embedding degree $k$. If $a = Dy^2$ with $D \le 10^{12}$ then $E$ can be constructed using the CM method.

When to use DEM method:​

• When $r$ is already defined by the polynomial in a higher-level application, otherwise use CP method instead.
• When $t, r, q$ are parameterised as polynomials, then the $\rho < 2$ can be achieved in resulting cyclotomic curve families ($\mathbb{F}_q$ is a cyclotomic field, $r$ is a cyclotomic polynomial).

Miyaji-Nakabayashi-Takano method​

Miyaji-Nakabayashi-Takano (MNT) method is used to sample a sparse family of elliptic curves with an arbitrary but limited embedding degree.

To use MNT method:​

• Choose embedding degree $k$ and fundamental discriminant $D$.
• Parametrise $t(x)$, $h(x)$ (set $h(x) = 1$ if prime-order curve is needed).
• Compute $r(x)$ and $q(x)$ such that $r(x) = q(x) + 1 − t(x)$ and $q(x)=h(x)r(x)+t(x)−1$.
• Find all solutions $(x, y)$ such that CM equation is satisfied.

The output is a polynomial $q(x)$ and $r(x)$ such that there exist a set of elliptic curve $E(x)$ over $\mathbb{F}_q(x)$ with $h(x) \cdot r(x)$ points and embedding degree $k = 3, 4,$ or $6$. If $q(x), r(x)$ are both primes, then curves $E(x)$ can be constructed via CM method.

* extension methods allow $k = 10$, $12$

When to use:​

• When a prime-order curve is needed.
• When looking for cycles of curves.

Twisted Edwards curves over the known field​

There's no single method for finding curves with a given base field size $q$, but the general procedure is following:

• Fix the curve by choosing coefficient $d$.
• Try different $a$, until you find a curve over $\mathbb{F}_q$ with satisfiable subgroup size $r$.
• During the search it’s possible to constraint other parameters, e.g. cofactor.

An alternative well-generalized method is described "Twisted Edwards Elliptic Curves for Zero-Knowledge Circuits" and was used to find Baby-JubJub over BN256 scalar field. Authors first find a Montgomery curve of desired parameters and then transform it to a twisted Edwards curve, which is possible because both forms are birationally equivalent. See example code.

More about the Twist​

Twist is a method of finding a twisted curve $E'$ over $\mathbb{F}_q$ which is isomorphic (equivalent) to a known curve $E$ over $\mathbb{F}_{q^d}$ such that it's possible to use the results of cheaper arithmetic over smaller $\mathbb{F}_q$ for computation on points of $E$ that is defined over a larger field $\mathbb{F}_{q^d}$.

The minimal integer $d$ for which $E$ and $E'$ are isomorphic over $\mathbb{F}_{q^d}$ is called the degree of the twist. There exist curves with: quadratic twist $d = 2$, cubic twist $d = 3$, and sextic twist $d = 6$.

To find (quadratic) twist:​

• Suppose you have a curve $E$ over $\mathbb{F}_{p}$ with equation $y^2 = x^3 + ax^3 + bx + c$.
• Pick some $d$ that is not a square mod $p$, i.e. there is no $x$ such that $x^2 - c$ is divisible by $p$.
• Define the twisted curve $E'$ with equation $dy^2 = x^3 + ax^3 + bx + c$.

To find higher-degree twists it's possible to stack multiple low-degree twists in a "tower" structure. For example, a sextic twist can be constructed by stacking two cubic twists: $\mathbb{F}^3_{q} \rightarrow \mathbb{F}^2_{q^3} \rightarrow \mathbb{F}_{q^6}$. Some operations such as pairing can be computed more quickly when performed over the extension field in tower form.

Advantages:​

• Increases security of new curve while keeping the performance of origin curve, e.g. a twisted curve defined over $\mathbb{F}_{q^d}$ may have a 214-bit security, but group operations could be computed in $\mathbb{F}_q$ instead of $\mathbb{F}_{q^d}$.
• Compression: in a twisted curve with embedding degree $k$ and a degree-$d$ twist the output of pairing can be given as an element of $\mathbb{F}_{q^{k/d}}$ instead of $\mathbb{F}_{q^k}$, sparing $log_2 d$ bits.

Methods for curve optimization​

Ristretto method​

Ristretto is a technique that can be applied to Edwards curves with cofactor $h = 4$ or $8$ to map their points of infinite order to points of prime order effectively creating prime order groups.

To use Ristretto:​

• Define a new type for Ristretto points which contains the representative Edwards point.
• Add an equality function to compare both representations of the same point.
• Add encoding and decoding functions to represent a point in and from their corresponding bitstrings.
• Add a map from bitstrings to Ristretto points suitable for hash-to-point operations.

Advantages:​

• Prevents certain attacks e.g. small subgroup attacks.
• Compressed points are more efficient to transmit and store.
• Preserves points' specific properties, which can be important for security.
• Can reduce cofactor $h$ that can be exploited by attackers.

Gallant-Lambert-Vanstone method​

Gallant-Lambert-Vanstone (GLV) method is a technique that can be applied to curves whose endomorphism $\psi$ can be efficiently computed to significantly accelerate scalar multiplication.

To use GLV method:​

• During curve generation fundamental discriminant must be restricted to $−D \geq −388$ so that $\psi$ can be efficiently computed.
• When implementing curve's arithmetic, scalar multiplication should be written according to GLV algorithm (example).

Tools and Tips​

To start with elliptic curve development install SageMath - an open-source python-based math-oriented programming environment that offers a comprehensive suite of tools that are essential for generating and testing elliptic curves. Likely, there's no need to implement everything from scratch. The researchers from SCIPR Lab already developed and packaged many of the popular methods into the ecfactory plugin. Though the recommended installation method didn't work for me with SageMath 9.0+, so I opted to add pip installation support in my fork.

Security considerations are essential to elliptic curve development. To check that a given curve satisfies current security requirements use SafeCurves, which essentially is a set of criteria for evaluating the security of elliptic curve cryptography. The criteria include standards for the properties of the curve itself such as its order, shape, and rigidity to various attacks, as well as properties of the underlying field such as size, stability, randomness, etc. The describe-curve tool can further help with SafeCurves checks but at the time of writing, it's still under development.

Resources​

• YAFA-108/146: Implementing Ed25519-Embedding Cocks-Pinch Curves in Arkworks-rs https://eprint.iacr.org/2022/1145.pdf
• Programming ECC https://crypto.stanford.edu/pbc/notes/ep/mnt.html
• A taxonomy of pairing-friendly elliptic curves https://eprint.iacr.org/2006/372
• Methods for Constructing Pairing-Friendly Elliptic curves https://theory.stanford.edu/~dfreeman/talks/ecc.pdf
• Field selection for recursive SNARKs https://medium.com/delendum/field-selection-for-recursive-snarks-726ad56c3a3c

Demo​

Here is the SageMath script for finding a pairing-friendly elliptic curve whose scalar field embeds the base field of Curve25519 using the Cocks-Pinch method.

Summary​

The advances in blockchains and zero knowledge cryptography created a demand for new application-specific elliptic curves. This became especially relevant for arithmetic circuit development and recursive proof composition.

To reduce prover overhead when the verifier operates over a specific curve, the application can be expressed over a twisted Edwards whose base field matches the verifier's curve.

When the application logic requires certain curve arithmetic, then the same optimization is possible by using Cocks-Pinch or DEM methods to find a compatible pairing curve whose scalar field embeds application's curve base field.

To perform efficient recursive proving, an elliptic curve cycle is needed, which can be obtained using MNT method. A slightly more performant approach relies on Cocks-Pinch curves that form a chain, but this way the recursion depth is limited.

For developing elliptic curves use SageMath with ecfactory. To evaluate the security of newly founded curves use SafeCurves and describe-curve tools.

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.