Elliptic curves

An elliptic curve is, in essence, simply the set of solutions (or points (x, y)) to an equation that can be represented in the form y^2 = x^3 + ax + b, where a and b, as well as points (x, y) that lie on the curve (that is, are solutions to the equation), belong to a finite field F_p defined by a prime p. That is, F_p is the set {0, 1, . . . , p − 1}, with addition and multiplication being modulo p.

Elliptic curves are of interest in cryptography because points can be added together, with the result also being a point on the curve. Furthermore, the set of points obtained by taking a point G (a generator) and adding it to itself repeatedly until reaching (or returning to) the starting point G, forms a group whose order (denoted here as q) is the number of points in the set. The relevance of this is that there is a class of asymmetric (or public key) cryptographic protocols known as the discrete log-based systems, and which include DSA and the Diffie-Hellman protocol, which are defined to work in a group. There are many different types of groups, but for cryptographic security, the so-called discrete log problem must be a complex problem to solve (for sufficiently large parameters). Two groups for which this problem is considered difficult are the group defined by the set of integers modulo a large prime p, and the group of points on an elliptic curve.

When used for cryptographic purposes, the order q is typically a large prime number and defines the scalar field of the curve.

Examples of elliptic curve groups include BN254 (the curve currently used by Panther), BLS12-377, and BLS12-381.

Note that in addition to size, the structure of the group of points on an elliptic curve is also important. The factorization of q − 1 defines the subgroups of Z_q. The inclusion in this factorization of 2^s for some sufficiently large s is required for using FFTs (for example, for multiplying polynomials), and is consequently crucial for the speed (or efficiency) of the proving process.

BN254 has 2-adicity 28 (that is, there exists a multiplicative subgroup of size 2^28).