I know we usually blackbox pairings calling them moonmath and putting e(dot,dot) instead. But enough is enough. This article explains the math behind pairings. It relies on the course on ECC led by Matan Prasma and organized by PSE and Carlos in particular.
How to read: the article consists of two parts: prerequisites and pairings. It might make sense to go to the section “Pairings” be surprised and then come back to the prerequisites but maybe you know better. All the proofs are skipped; you can find them in Matan’s textbook. Hope you have fun reading it!
Pairings after being blackboxed by web3 community since forever:
I’ll assume the reader is aware of the intuition behind what an elliptic curve is as it pops up in many crypto write ups. Instead I will focus more on the properties and theorems affiliated with ECs that pairings rely on.
This write up also assumes that the reader is somehow fluent with groups, fields, and sets.
Note: because of the math mode limitations i might use f_bar to denote what’s usually denoted as f with bar over it.
Field characteristic – the smallest number of times you need to add the multiplicative identity to get the additive identity (i.e. the minimal number such that ).
Field closure – a field F is algebraically closed if every non-constant polynomial in has a root in .
Abelian group – a commutative group, a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written: .
An elliptic curve in general Weierstrass form over a field K:
+ some conditions (we are not really interested in this form).
We are interested in ECs of the short Weierstrass form: those over fields whose characteristic is neither 2 nor 3. In this case the equation can be way simplified:
. We also require that A and B satisfy the following: .
The solution set (all zeros) to the ECs is a set of points of the form and in general it does not have any apparent geometry.
Rude intuition: to make the solution set ’s work as a group we need to introduce some zero/neutral element. We introduce the point at infinity for this role. We denote the point at infinity as and can think of it .
Let be an elliptic curve over a field . The K-rational points of are the set
Let’s now define the group law (we do not provide the intuition of why it works this way, but if you want – check in this book).
Take two points on EC: and such that and that none of them is the point at infinity . We want to compute .
Define and . Then .
is a separate case. In this case, . Finally, to consider the point at infinity: and .
Let be an elliptic curve defined over a field K with . Then the K-rational points , together with addition of points defined above, form an abelian group. The neutral element is and the inverse of a point is given by .
A rational function is a function of the form where both f and g are polynomials and .
The field of rational functions is the set $K(x,y) = {f(x,y)/g(x,y) ∣ f, g ∈ K[x,y], g ≠ 0} $together with the obvious addition and multiplication. We use two-var polynomials as it’s what we are interested in for ECs.
Every field element of this type defines a map . Fyi: the map is a partial function as it’s not defined for points such as .
A rational function is regular at point if there exists a representation of as with (we can also say if it is defined at point ).
For an elliptic curve we define the set of polynomials over E to be . One can think of polynomials over EC as reminders of division even though for the case of polynomials in two variables there is no explicit way to divide polynomial over polynomial.
The canonical form of a polynomial is for some (i.e. and are polynomials in one variable). This form helps us to represent polynomials in two variables as polynomials in one variable. The canonical form is unique.
The conjugate of is .
The norm of f is .
The degree of is .
Useful properties:
: the degree of the polynomial equals the degree of the norm.
.
For an elliptic curve the set of rational functions on is the quotient set where stands for the equivalence relation . To check if equality holds, we can write and in canonical forms and compare coefficients.
Observation: is a field.
Let be an elliptic curve, and let be a rational function. We say that has a zero at if and that has a pole at if is not regular at (i.e. there is no representation such that ).
In the one variable case, and we say that is a zero of r of multiplicity n if divides but does not divide . The same for the pole but with instead of .
For two variable rational functions cases it’s not that straightforward. We can think of zero as a point of intersection of the elliptic curve and a curve (the same for the pole but with ). Now we want to derive a definition of multiplicity of zeros and poles.
Let be an elliptic curve and . A rational function with is called a uniformizer at if , and with , such that .
(As a rude intuition: for some rational function r that has problems at (zero or pole), a uniformizer for is a rational function with a zero at , such that for any rational function that is ”complicated” at , we can find a rational function s that is not complicated at ).
The uniformizers we present below are simply one common choice:
Let be an elliptic curve and a finite point with . Then the rational function is a uniformizer at .
For such that , the rational function is a uniformizer at .
For , the function is a uniformizer.
Remarks on uniformizers:
Uniformizers exist for all points in .
Even for a fixed point there is usually more than one uniformizer at .
The number (in ) does not depend on the choice of the uniformizer.
We say that has order/multiplicity at .
Note that we have two different definitions of order at P:
The first is the order of P as an element in the abelian group E(K), i.e. the minimal integer n such that nP = O.
The second one we’ve just described above in which we say that P has order n with respect to r.
(In this write up we are mostly dealing with the second definition).
Remarks about order:
A point has order if and only if it is neither a zero or a pole of .
We can add and multiply rational functions at if they are finite at : for such that and are finite we have and .
If is a zero of r (i.e. ) then and if is a pole of (i.e. is not defined) then .
Let be rational functions and . Then and for .
At point of infinity,
Sum of multiplicities of roots equal degree: for all such that .
A rational function has only finitely many zeros and poles.
The sum of orders is zero. Let be an elliptic curve over an algebraically closed field . For for all .
(These remarks are mostly used in proofs so here they might look random but they are illustrative to show how much we are dealing with the order).
Informally, divisor is a formal sum of all zeros and poles. Formally, a divisor on (over ) is an expression for all where are multiplicities/degrees at the points and only finitely many $n_P $’s are non-zero.
the set of all divisors on . This set is a group with addition as the group law. The neutral element is the divisor and the inverse of a divisor is the divisor .
The degree of a divisor is and the sum of a divisor is .
The norm of a divisor is for all .
For rational functions, and .
Astonishing fact: (in other words the number of zeros equals the number of poles).
The divisor is principle if and only if
;
.
(Also famous as Abel-Jacobi)
If $D_1 - D_2 $is principal, then we say that are linearly equivalent or in the same divisor class.
Other divisor properties:
Line on EC
A line on is a polynomial in of the form with and or . For finite with there is a line through and . For finite and not of order two, the line with has a double zero at and one other finite zero. In other words: .
Classification of divisors of lines
Suppose be an elliptic curve over an algebraically closed field. Let be a line on . Then there are distinct finite points on such that one of the following holds:
Moreover, there is a line for each of these divisors that furthermore satisfy sum.
For each , there is a unique point such that
Rational maps
A rational map is a pair where are rational functions on and is algebraically closed such that for all . And if and only if .
A rational map induces a map given by if and if .
(If you wonder why we distinguish between rational maps and rational functions as two different creatures – the reason is to avoid calling two different things ‘rational functions’ tho we could. There is always the problem of notation abuse whatever we are doing).
Torsion subgroups
The n-torsion points of are . Informally, we can say that these are all points on the curve such that while added to itself n times we get zero.
(btw we are really close to pairings now!)
The Divisor of
Now we want the divisor of but we can’t just go and take it. More work is required.
Let be the derivative of a rational function (but has been a divisor 5 min ago? Sorry so many words start with D. What are we expected to do?)
In this piece we omit the precise definition of derivative of a rational function, but if you remember the derivative of a function in two variables – that’s approx it.
Derivative also has an order: let be a rational function. If is prime to , then .
Now we want the derivatives of and : we have and .
We also need a rational function that will operate as a uniformizer at : suppose is a uniformizer at . Then the rational function defined by is a uniformizer at .
Finally we can have :
Say we write to denote the divisor whose nonzero entries are the points of , each with coefficient one. Then . This thing also has quite a long and entertaining proof if you are into things like that.
If n is prime to , then has points.
To approach pairing (or at least to poke them) we want to rely on the fact that where stands for isomorphic. It has a long and entertaining proof.
We are ready to construct pairings. We are going to use ‘facts’ discussed earlier step by step and hope it looks somehow logical. If it doesn’t – please blame yourself and only yourself.
Let be an elliptic curve over an algebraically closed field with char .
Recall that for an integer prime to we have an isomorphism .
Let be a point on EC and be a rational function such that the divisor of the rational function .
Take the map given by (it might look somehow affiliated with n-Torsion points hope you still remember them!)
This map is surjective.
Let be such that .
Consider the divisor .
The degree of is 0 and since .
So there exists a rational function such that
Consider the rational function .
The points are poles of of order each.
The points for are those points for which .
It follows that
Thus, is a constant multiple of and wlog, we may choose such that .
Let , an n-torsion point, and , a point on EC. Then
so that .
Finally!!!!!!!!!!
Weil pairing, this is this guy: and thus get a function .
Maybe it’s not what you expected (if you expected anything at all). In particular, pairing depends on the choice of the function g_Q. And what is that function? Remember several rows above we told “...wlog, we may choose such that …” If we stick to the math mindset we should say ‘AH that’s details of implementation we don’t care!’
But we are not that mean so let’s provide one example taken from a random textbook:
For an EC
Functions g:
But these are not those functions but some other functions , using their divisors one calculated functions :
And then these functions are utilized to calculate the pairing:
So pairings are some manipulation with polynomials and divisors. Even if the explanation was vague one definitely can see that there is no real magic there it’s just math.
Usually we are all somehow used to polynomial manipulations but divisors are a new creature for us. So understanding pairings heavily relies on understanding divisors and feeling fluent with these guys.
For proofs check the textbook. For detailed awesome explanations see the course.