Elliptic Curves In Practice–Part 1

Definition: Elliptic Curve, Group, Field

The elliptic curve is defined by an equation, but when it comes to practices, it is discrete and finite, i.e, we cannot work on elliptic curves that are defined on \(\mathbb{R}\), instead, we defined it on a field \(\mathbb{F}_p\) .

The points on the curve are the solutions \((x,y)\) for the curve equation, at the same time, both \(x\) and \(y\) are the elements in the field \(\mathbb{F}_p\). We call them \(\mathbb{F}_p\)-rational points on an elliptic curve \(E(\mathbb{F}_p)\). These \( (x,y) \) coordinates are called “affine coordinates”. Each of the  \(\mathbb{F}_p\)​-rational points, together with a “point at infinity” \(\mathcal{O}\) that serves as the group identity, can be interpreted as an element of a group.

Let’s have a look at how elliptic curve are implemented in some popular frameworks:

Different Curves

Curves that are supported by gnark:

•  BN254 🙂
•  BLS12-381 🙂
•  BLS12-377
•  BW6-761
•  BLS24-315
•  BW6-633
•  BLS24-317

The properties of Elliptic Curve

Security

Parameters that influence the security of Elliptic Curve (assume you choose the standard elliptic curve)

1. Prime Field Parameters: In many cases, elliptic curves are defined over prime fields \(GF(p)\), where\(p\) is a prime number. The choice of this prime \(p\) influences the size of the curve and thus the security level. Larger prime values generally result in higher security but may also lead to slower computations.
2. Base Point: Elliptic curve cryptography relies on a base point (also called a generator point), denoted as \(G\), which generates all other points on the curve through scalar multiplication. The choice of this base point is crucial for security. It should have a large prime order (i.e., \(nG=\mathcal{O}\) where \(n\) is prime), ensuring that the discrete logarithm problem is hard. It should ideally be a large prime number to resist attacks such as the Pollard’s rho algorithm.

Efficiency

Implementation

Let’s have a look how the elliptic curve is defined in practice

BN254 in gnark

seed x₀=4965661367192848881
𝔽r: r=21888242871839275222246405745257275088548364400416034343698204186575808495617 (36x₀⁴+36x₀³+18x₀²+6x₀+1)
𝔽p: p=21888242871839275222246405745257275088696311157297823662689037894645226208583 (36x₀⁴+36x₀³+24x₀²+6x₀+1)
(E/𝔽p): Y²=X³+3
(Eₜ/𝔽p²): Y² = X³+3/(u+9) (D-type twist)
r ∣ #E(Fp) and r ∣ #Eₜ(𝔽p²)

Parameters

• \( \text{Seed } x_0 \): This is a starting value used in the generation of the parameters for the ECC.
• \( \text{Finite Field } \mathbb{F}_r \):\( r \) is the order of the base field. It represents the number of points on the elliptic curve defined over the prime field \( \mathbb{F}_p \), where \( p \) is another parameter. The polynomial representation \( 36x_0^4 + 36x_0^3 + 18x_0^2 + 6x_0 + 1 \) is used to represent the field size by the seed.
• \( \text{Finite Field } \mathbb{F}_p \): \( p \) is the prime number representing the size of the finite field over which the elliptic curve is defined. The polynomial representation \( 36x_0^4 + 36x_0^3 + 24x_0^2 + 6x_0 + 1 \) is used to represent the field size by the seed.
• \( \text{Elliptic Curve Equation } E/\mathbb{F}_p \): This represents a twisted curve \( E_t \) defined over an extension field \( \mathbb{F}_{p^2} \). The equation is \( Y^2 = X^3 + 3 \) over the finite field \( \mathbb{F}_p \). This kind of twist is often used for efficiency in cryptographic operations.
• \( \text{Twist of Elliptic Curve } E_t/\mathbb{F}_{p^2} \): This represents a twisted curve \( E_t \) defined over an extension field \( \mathbb{F}_{p^2} \). The equation is \( Y^2 = X^3 + \frac{3}{(u + 9)} \), where \( u \) is a parameter. This kind of twist is often used for efficiency in cryptographic operations.
• \( \text{Divisibility Relationship:} \) \( r \) divides the number of points on the elliptic curve \( E \) over \( \mathbb{F}_p \) and also divides the number of points on the twisted curve \( E_t \) over \( \mathbb{F}_{p^2} \).

Note: \(\mathbb{F}_r\) is the scaler field, \(r\) is the total number of \(\mathbb{F}_p\) rational points on curve. It is also the order of the cyclic group of the elliptic curve points. While \(\mathbb{F}_p\) is the base field, it is the elliptic curve defined upon, the coordinate of the point should be in the base field. These two field should not be mixed.

Functions

The functions are defined for ECC computations, typical operations like, addition, Equal, ScalerMultiplication, MultiExp on Affine and Jacobine, Pairing

In part 2, I will look at some specific function implementations.