Elliptic Curves

Previously I started peeling away at the different components that make a cryptographic pairing. I talked about the general structure, and then gave a basic introduction to groups and fields. Today I pick up at that point and take you to the next step: elliptic curves.

So let’s up the game a bit.

Curves on Fields

You’re probably familiar with the real numbers ℝ and, possibly without realizing it, the two-dimensional space ℝ2, if you remember doing graphs in high school or some functional analysis later on. To draw a graph, we generally start with two axes and number some notable points in there, setting a scale. Each point in the graph is then associated to a coordinate on each axis, which normally represents a real number. The set of all such points forms the two-dimensional vector space ℝ2.

You can have higher-dimensional spaces, even if you can’t represent them graphically on paper or a screen. You just need to think as points having several coordinates taken from the underlying field, for example:

[5, 0.234, -72.13, 0, 48.1]

A curve on a graph, for example y = x2 + 2x - 5, goes through exactly those points of the whole space that satisfy the curve. This particular example looks like this:

The parabola y = x² + 2x – 5

You aren’t restricted to the real numbers. You could use other fields, like the complex numbers, or even finite fields. These are the ones relevant to cryptographic pairings, and so are the only ones I’m concerned with in this series.

Mathematics in a finite field

In a finite field, you only have a certain number of elements you can use. For an example, take 𝔽 = ℤ7, which is based on the set {0, 1, 2, 3, 4, 5, 6} with addition and multiplication modulo 7. Since this is a field, elements can be freely added and multiplied, both operations are commutative and associative, and we have distributivity.

Because we are working in a field, we are guaranteed every element has an additive inverse, and every non-zero element has a multiplicative inverse, which are used for subtraction and division. These operations do not exist per se: a subtraction is the same as adding the symmetric (ie the additive inverse), and dividing is the same as multiplying by the multiplicative inverse. For example, we can write things like this:

(4 + 5) * (-5) / 3 =
 2 * 2 * 5 = 
 4 * 5 =
 6 (mod 7)

The above derivation will be surprising if you are not familiar with modular arithmetics, so I will use it just as an introductory example. As a very basic guide, remember these points:

1. you only have integer numbers from 1 to the modulus (7 in this case, which is the same as 0).
2. A number is equivalent to any other number resulting from adding multiples of the modulus. For example, in this field, 0 is equivalent to -14, -7, 7, 14.
3. Likewise, -5 is the same as 2 or 9.

Multiplicative Inverses

As I said above, you can’t just divide by a number x, since that would in general return a non-integer. Instead, you have to compute the multiplicative inverse of that number, which means finding y such that x*y = 1. In this case, we want to divide by 3. The inverse is 5, since 5 * 3 = 15 = 1 mod 7.

If you feel curious enough about this, and wish to know how to compute such an inverse, I will direct you to the Euclidean Algorithm, normally used to compute the greatest common divisor of two numbers. Only, instead of using the normal one, you really want the Extended version. As usual, the Wikipedia page for it is overkill, but it has the information in there. I sometimes prefer Wolfram Math World pages for this kind of question, but I’ll let you make your own choice.

Finite fields will always look a bit like this, in that there will be a modulus element, equivalent to 0, that is used to reduce all others. For now, you can think of it as a number like 7 in the above example, but in a later post I will introduce you to a more general and esoteric case.

If you dip your foot in the water and really like this stuff, then maybe you would enjoy a whole book on Number Theory. I know it’s not for everyone, but if you would like to be a cryptographer at some point, some Number Theory would be pretty essential. Personally, this was what motivated me to study cryptography, when I had a brief course of it in college.

The Defining Equation of Elliptic Curves

Elliptic curves are defined by a specific kind of equation. They are typically represented using Weierstrass Form, which is

y2 = x3 + ax + b

They come in different families, with their own requirements. For the curves we’re using with ZK SNARKs, the most prevalent one is the Barreto-Naehrig (BN) family. Other families are the Barreto-Lynn-Scott (BLS), or Miyaji-Nakabayashi-Takano (MNT). You could go out and search all the differences in these families. I don’t recommend, it unless you are a mathematician or a cryptographer specializing in performance or the security level of elliptic curves. For the rest of this post, I will stay with BN curves.

If you want to know more about Elliptic Curves, I could point you to this book, but I must warn you it is a research level collection of separates articles. If you are a mere mortal trying to get into cryptography, this introductory book, by one of the authors of the first book, may be a better choice.

Properties of Barreto-Naehrig Elliptic Curves

BN curves were a revolution when they appeared. They combined the best security levels with performant calculations, and still could lead to short keys. Recent improvements in cryptanalysis have reduced their security a little, but they are still very good choices. Their equation has the form

y2 = x3 + b

and they have so-called embedding degree 12. I am not going to explain what this means but keep this value in mind for later.

An example of a BN curve, with b = 3

Homogeneous Coordinates

The equation of BN curves shows points on these must have at least two coordinates, X and Y, which are themselves elements of the field 𝔽. This makes them easily representable in a graph.

It is often more efficient to turn these points into homogeneous or projective coordinates, which add a third coordinate (Z) to the point. A point (X,Y) in Cartesian coordinates becomes (X,Y,1) in homogeneous coordinates. But this introduces an interesting property: any point (X,Y, Z) is equivalent to another point (kX, kY, kZ), which means that in this coordinate system, each point has an infinitude of equivalent representations. To normalize a number, we simply divide all coordinates by Z, ending up again with something like (X,Y,1).

This was one of several difficulties in our work at Artos (as will be detailed in other posts). When we transitioned from ZoKrates to other libraries, and were trying to verify whether they produced the same result, we were faced with representations in full projective coordinates, whereas ZoKrates by default normalizes them and prints only (X,Y).

As a consequence, we might receive this point in ZoKrates:

(4407273740129956103199206381674388571562541678897750695293641007314240357886,
12736046180745556842853876822831838464421485794088871196194553131582128174744)

and receive this in another library

(2946337088698561182441604874498577406359925633941015321680697665685275101913,
19607339821656175953378250327109544682088110977207135820455253658175119673332,
5550013512887652721478346499161092033631982655402508028685309118537179826927)

without understanding they are exactly the same point.

I recommend you always normalize your points before printing them out.

Elliptic Curves As Finite Groups

In order for elliptic curves to be used in cryptography, and to be secure, they have to support groups where certain problems are hard. To do that, we need to define an operation on the curve, typically representing the addition of two curve points. We also need an identity element, which is the neutral for this operation.

For the majority of points, the operation is simply described:

• draw a line passing through the two points you’re adding (say A and B)
• this line must intersect the curve at a third point (call it C)
• the result of A+B is the symmetric of C in relation to the x-axis

The identity point can only be defined in projective coordinates. This is because, with these, all lines will meet exactly at one point, the point-at-infinity O. In this way, the addition line, which crosses the 3 points involved in the addition, will always “finish” at that point, making it possible to define the addition described above. This post does a great job of explaining it. Wikipedia (click below image) can also help.

In the projective plane, O has coordinates (0, 1, 0), and the additive inverse of an element (X,Y,Z) is its symmetric over the x-axis, (X, -Y, Z).

Some odd cases must be treated separately. For example, if you are adding one point to itself, you can’t draw a single line passing through this point. Instead, you pick the tangent to the curve at that point and proceed as above. Iif one of the operands is the neutral element, the operation returns the other summand, and if the inputs are symmetric to each other, it returns O.

This operation satisfies all the group axioms:

• every two points can be added to give a third point (closure);
• it does not matter in what order the two points are added (commutatitivity);
• if you have more than two points to add, it does not matter which ones you add first either (associativity);
• there is an identity element.

Creating New BN Elliptic Curves

There are two important parameters when defining a BN curve: the order of the underlying field, which I’ll call p, and the order of the curve, denoted by n. Just like for fields and groups, the order of the curve represents the number of distinct elements it contains. Both orders have to be primes, and satisfy a particular relation:

p = 36u4 + 36u3 + 24u2 + 6u + 1
n = 36u4 + 36u3 + 18u2 + 6u + 1

for some integer u in Z.

It is easy to generate new BN curves: just pick some u until p and n are prime. Then try several b until one is found that makes the curve be of order n. This algorithm will also return a generator for the curve, which is

(1,y), for y2 = b + 1 mod p.

Is this it?

Well, no. There is more to say about BN curves and in particular about pairings. But I want to break this series into self-contained small units. So I’ll stop this post here. The important points to take away are these:

• Elliptic curves are the set of points on a bi-dimensional space defined over a finite field 𝔽 of prime order p.
• BN curves are a family of elliptic curves with a simple equation: y2 = x3 + b
• It is possible to define an operation over points on an elliptic curve that give it a group structure. This is generally regarded as an “addition of points”.
• The identity point, called the point-at-infinity, is essentially 0 for this addition (the neutral element).
• The curve can also be represented with homogeneous coordinates. This introduces a third element that makes computation more efficient. As a consequence, there can be an infinite number of equivalent representations for each point.
  • a point (X,Y) is equivalent to (X,Y,1) in homogeneous coordinates
  • a point (X,Y,Z) is equivalent to (X/Z, Y/Z, 1)
  • the point-at-infinity is special. It only exists in homogeneous coordinates and its value is (0,1,0)

In later posts, I will introduce pairings over BN curves. That will lead me to talk about the other groups associated to the base curve and more complex fields.

Until then, stay tuned for more posts about SNARKs or blockchain in general.