Pairings coming out
January 20th, 2025

Introduction

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:

Prerequisites

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.

Prerequisites to prerequisites

  • Field characteristic – the smallest number of times you need to add the multiplicative identity to get the additive identity (i.e. the minimal number nNn ∈ N such that 1+1+...+1=01 + 1 + ... + 1 = 0).

  • Field closure – a field F is algebraically closed if every non-constant polynomial in F[x]F[x] has a root in FF.

  • 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: f(x,y)=f(y,x)f(x,y) = f(y,x).

Elliptic Curves

An elliptic curve in general Weierstrass form over a field K:

Ey2+a1xy+a3y=x3+a2x2+a4x+a6E ∶ y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6 + 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:

Ey2=x3+Ax+BE ∶ y^2 = x^3 + Ax + B. We also require that A and B satisfy the following: (E)=4A3+27B20∆(E) ∶= 4A^3 + 27B^2 ≠ 0.

The solution set (all zeros) to the ECs is a set of points of the form (x,y)(x,y) and in general it does not have any apparent geometry.

The group law on an elliptic curve

Rude intuition: to make the solution set (x,y)(x,y)’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 OO and can think of it O={,}O = \{∞,∞\}.

Let Ey2=x3+Ax+BE ∶ y^2 = x^3 + Ax + B be an elliptic curve over a field KK. The K-rational points of EE are the set E(K)={(x,y)K2y2=x3+Ax+B}{O}.E(K) = \{(x, y) ∈ K^2 ∣ y^2 = x^3 + Ax + B\} ∪ \{O\}.

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: P=(x1,y1)P = (x_1, y_1) and Q=(x2,y2)Q = (x_2, y_2) such that ​​PQP ≠ Q and that none of them is the point at infinity OO. We want to compute R=P+QR’ = P + Q.

Define m=(y2y1)/(x2x1)m = (y_2 − y_1)/(x_2 − x_1) and x3=m2x1x2x_3 = m^2 − x_1 − x_2. Then P+Q=R=(m2x1x2,m(x1x3)y1)P + Q = R' = (m^2 − x_1 − x_2, m(x_1 − x_3) − y_1).

P=QP = Q is a separate case. In this case, P+P=(m22x1,m(x1x3)y1)P + P = (m^2 − 2x_1, m(x_1 − x_3) − y_1). Finally, to consider the point at infinity: P+O=PP + O = P and O+O=OO + O = O.

Theorem

Let Ey2=x3+Ax+BE ∶ y^2 = x^3 + Ax + B be an elliptic curve defined over a field K with char(K)2,3char(K) ≠ 2, 3. Then the K-rational points E(K)={(x,y)K×Ky2=x3+Ax+B}{O}E(K) = \{(x, y) ∈ K × K ∣ y^2 = x^3 + Ax + B\} ∪ \{O\}, together with addition of points defined above, form an abelian group. The neutral element is OO and the inverse of a point P=(x1,y1)P = (x_1, y_1) is given by P=(x1,y1)−P = (x_1,−y_1).

Rational functions

A rational function is a function of the form r(x,y)=f(x)/g(x)r(x,y) = f(x)/g(x) where both f and g are polynomials and g0g ≠ 0.

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 (x0,y0)f(x0,y0)/g(x0,y0)(x_0, y_0) ↦ f(x_0,y_0)/g(x_0,y_0). Fyi: the map is a partial function as it’s not defined for points such as g(x0,y0)=0g(x_0, y_0) = 0.

A rational function r(x,y)r(x, y) is regular at point P=(x0,y0)P = (x_0, y_0) if there exists a representation of rr as r=f/gr = f/g with g(P)0g(P) ≠ 0 (we can also say if it is defined at point PP).

Polynomials over ECs

Set of polynomials

For an elliptic curve E/Ky2=x3+Ax+BE/K ∶ y^2 = x^3 + Ax + B we define the set of polynomials over E to be K[E]=K[x,y]/(y2x3AxB=0)K[E] = K[x,y]/(y^2 − x^3 − Ax − B = 0). 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.

Canonical form

The canonical form of a polynomial is f(x,y)=v(x)+yw(x)f(x, y) = v(x) + yw(x) for some v,wK[x]v, w ∈ K[x] (i.e. vv and ww 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 ff is fˉ\bar{f} =v(x)yw(x)= v(x) − yw(x).

  • The norm of f is Nf=ffˉN_f = f ⋅ \bar{f}.

  • The degree of ff is deg(f)=max{2degx(v),3+2degx(w)}deg(f) = max\{2 ⋅ deg_x(v), 3 + 2 ⋅ deg_x(w)\}.

Useful properties:

  • deg(f)=degx(Nf)deg(f) = deg_x(N_f ): the degree of the polynomial equals the degree of the norm.

  • deg(fg)=deg(f)+deg(g)deg(f ⋅ g) = deg(f) + deg(g).

Rational functions over EC

For an elliptic curve E/KE/K the set of rational functions on EE is the quotient set K(E)=K[E]×K[E]{0}/K(E) = K[E] × K[E]∖ \{0\}/ ∼ where stands for the equivalence relation (f,g)(h,k)fk=hgK[E](f, g) ∼ (h, k) ↔ f ⋅ k = h ⋅ g ∈ K[E]. To check if equality holds, we can write fkf ⋅ k and hgh ⋅ g in canonical forms and compare coefficients.

Observation: K(E)K(E) is a field.

Zeros and poles

Let E/KE/K be an elliptic curve, and let rK(E)r ∈ K(E) be a rational function. We say that rr has a zero at PE(K)P ∈ E(K) if r(P)=0r(P) = 0 and that rr has a pole at PP if rr is not regular at PP (i.e. there is no representation r=f/gK(E)r = f/g ∈ K(E) such that g(P)0g(P) ≠ 0).

Multiplicity

In the one variable case, r(x)=f(x)/g(x)r(x) =f(x)/g(x) and we say that x0x_0 is a zero of r of multiplicity n if (xx0)n(x − x_0)^n divides f(x)f(x) but (xx0)(n+1)(x − x_0)^{(n+1)} does not divide f(x)f(x). The same for the pole but with g(x)g(x) instead of f(x)f(x).

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 EE and a curve Cf:f(x,y)=0C_f: f(x,y) = 0 (the same for the pole but with Cg:g(x,y)=0C_g: g(x,y) = 0). Now we want to derive a definition of multiplicity of zeros and poles.

Introducing uniformizer

Let E/KE/K be an elliptic curve and PEP ∈ E. A rational function uK(E)u ∈ K(E) with u(P)=0u(P) = 0 is called a uniformizer at PP if rK(E){0}∀r ∈ K(E) ∖ \{0\}, dZ∃d ∈ Z and sK(E)s ∈ K(E) with s(P)0,s(P) ≠ 0,∞, such that r=udsr = u^d ⋅ s.

(As a rude intuition: for some rational function r that has problems at PP (zero or pole), a uniformizer for PP is a rational function uu with a zero at PP, such that for any rational function rr that is ”complicated” at PP, we can find a rational function s that is not complicated at PP).

The uniformizers we present below are simply one common choice:

  • Let E/KE/K be an elliptic curve and P=(a,b)E(K)P = (a, b) ∈ E(K) a finite point with 2PO2P ≠ O. Then the rational function u(x,y)=xaK(E)u(x, y) = x − a ∈ K(E) is a uniformizer at PP.

  • For PE(K){O}P ∈ E(K) ∖ \{O\} such that 2P=O2P = O, the rational function u(x,y)=yK(E)u(x, y) = y ∈ K(E) is a uniformizer at PP.

  • For P=OP = O, the function u(x,y)=x/yu(x, y) = x/y is a uniformizer.

Remarks on uniformizers:

  • Uniformizers exist for all points in E(K)E(K).

  • Even for a fixed point PE(K)P ∈ E(K) there is usually more than one uniformizer at PP.

  • The number dd (in r=udsr = u^d ⋅ s) does not depend on the choice of the uniformizer.

  • We say that rr has order/multiplicity dd at P:ordP(r)=dP: ord_P(r) = d.

More on the order

Note that we have two different definitions of order at P:

  1. 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.

  2. 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 PE(K)P ∈ E(K) has order ordP(r)=0ord_P(r) = 0 if and only if it is neither a zero or a pole of rr.

  • We can add and multiply rational functions at PP if they are finite at PP: for r,sK(E)r, s ∈ K(E) such that r(P)r(P) and s(P)s(P) are finite we have (rs)(P)=r(P)s(P)(r ⋅ s)(P) = r(P)⋅s(P) and (r+s)(P)=r(P)+s(P)(r + s)(P) = r(P) + s(P).

  • If PP is a zero of r (i.e. r(P)=0r(P) = 0) then ordP(r)>0ord_P (r) > 0 and if PP is a pole of rr (i.e. r(P)r(P) is not defined) then ordP(r)<0ord_P (r) < 0.

  • Let r,rK(E)r, r′ ∈ K(E) be rational functions and PE(K)P ∈ E(K). Then ordP(rr)=ordP(r)+ordP(r)ord_P(r⋅r') = ord_P(r) + ord_P(r') and for r0,ordP(r/r)=ordP(r)ordP(r)r' ≠ 0, ord_P(r/r') = ord_P(r) − ord_P(r').

  • At point of infinity, ordO(f)=deg(f)ord_O(f) = −deg(f)

  • Sum of multiplicities of roots equal degree: deg(f)=ordP(f)deg(f) = ∑ ord_P(f) for all PEP∈E such that f(P)=0f(P)=0.

  • A rational function rK(E)r ∈ K(E) has only finitely many zeros and poles.

  • The sum of orders is zero. Let E/KE/K be an elliptic curve over an algebraically closed field KK. For rK(E):ordP(r)=0r ∈ K(E) : ∑ ord_P(r) = 0 for all PE(K)P∈E(K).

(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).

Encoding zeros and poles with their multiplicities in a formal manner

Divisors

Informally, divisor is a formal sum of all zeros and poles. Formally, a divisor on EE (over KK) is an expression D=nP[P]D = ∑n_P [P] for all PE(K)P ∈E(K) where P,nPZ∀P, n_P ∈ Z are multiplicities/degrees at the points and only finitely many $n_P $’s are non-zero.

DivK(E)Div_K(E) the set of all divisors on EE. This set is a group with addition as the group law. The neutral element is the divisor 0[P]∑ 0 ⋅ [P] and the inverse of a divisor D=nP[P]D = ∑n_P [P] is the divisor D=nP[P]−D = ∑ −n_P [P].

  • The degree of a divisor DDivED ∈ Div_E is deg(D)=nPdeg(D) = ∑n_P and the sum of a divisor DDivED ∈ Div_E is sum(D)=nPPE(K)sum(D) = ∑n_P ⋅ P ∈ E(K).

  • The norm of a divisor D=np[P]D = ∑ n_p[P] is D=nP∣D∣ = ∑∣n_P∣ for all PE{O}P ∈E∖\{O\}.

  • For r,sK(E){O}r, s ∈ K(E) ∖ \{O\} rational functions, div(rs)=div(r)+div(s)div(r⋅s) = div(r) + div(s) and div(r/s)=div(r)div(s)div(r/s) = div(r) − div(s).

Astonishing fact: ordP(r)P=O∑ ord_P(r) ⋅ P = O (in other words the number of zeros equals the number of poles).

The divisor DD is principle if and only if

  • deg(D)=0deg(D) = 0;

  • sum(D)=0sum(D) = 0.

(Also famous as Abel-Jacobi)

If $D_1 - D_2 $is principal, then we say that D1,D2Div(E)D_1, D_2 ∈ Div(E) are linearly equivalent or in the same divisor class.

Other divisor properties:

  • div(r)=div(r)div(−r) = div(r)

  • div(r)=div(1/r)−div(r) = div (1/r)

Line on EC

A line on EE is a polynomial in K[E]K[E] of the form l(x,y)=αx+βy+γl(x, y) = αx + βy + γ with α,β,γKα, β, γ ∈ K and α0α ≠ 0 or β0β ≠ 0. For P1,P2EP_1, P_2 ∈ E finite with P1P2P_1 ≠ P_2 there is a line through P1P_1 and P2P_2. For P=(a,b)EA,BP = (a, b) ∈ E_{A,B} finite and not of order two, the line l(x,y)=m(xa)(yb)l(x, y) = m(x − a) − (y − b) with m=(3a2+A)/2bm = (3a^2+A)/2b has a double zero at PP and one other finite zero. In other words: QEdiv(l)=2[P]+[Q]3[O]∃Q ∈ E ∶ div(l) = 2[P] + [Q] − 3[O].

Classification of divisors of lines

Suppose E/KE/K be an elliptic curve over an algebraically closed field. Let ll be a line on EE. Then there are distinct finite points P1,P2,P3P_1, P_2, P_3 on EE such that one of the following holds:

  1. div(l)=[P1]+[P2]+[P3]3[O]div(l) = [P_1] + [P_2] + [P_3] − 3[O]

  2. div(l)=2[P1]+[P2]3[O]div(l) = 2 [P_1] + [P_2] − 3[O]

  3. div(l)=3[P1]3[O]div(l) = 3 [P_1] − 3[O]

  4. div(l)=[P1]+[P2]2[O]div(l) = [P_1] + [P_2] − 2[O]

  5. div(l)=2[P1]2[O]div(l) = 2 [P_1] − 2[O]

    Moreover, there is a line for each of these divisors that furthermore satisfy sum(div(l))=O(div(l)) = O.

For each DDiv0(E)D ∈ Div^0(E), there is a unique point PEP ∈ E such that D[P][O]D ∼ [P] − [O]

Rational maps

A rational map ρEEρ ∶ E → E is a pair ρ=(r,s)ρ = (r, s) where r,sK(E)r, s ∈ K(E) are rational functions on EE and KK is algebraically closed such that for all PE(K),s(P)2=r(P)3+Ar(P)+BP ∈ E(K), s(P)^2 = r(P)^3 + Ar(P) + B. And r(P)=r(P) = ∞ if and only if s(P)=s(P) = ∞.

A rational map ρ=(r,s)EEρ = (r, s) ∶ E → E induces a map ρE(K)E(K)ρ ∶ E(K) → E(K) given by P(r(P),s(P))P ↦ (r(P), s(P)) if r(P),s(P)r(P), s(P) ≠ ∞ and POP ↦ O if r(P)=s(P)=r(P) = s(P) = ∞.

(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 EE are E[n]={PE(K)nP=O}E[n] = \{P ∈ E(K) ∶ n ⋅ P = O\}. 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 gmgng_m − g_n

Now we want the divisor of gmgng_m - g_n but we can’t just go and take it. More work is required.

Let DrDr be the derivative of a rational function rr (but DD 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 rr be a rational function. If ordp(r)=d0ord_p(r) = d ≠ 0 is prime to pp, then ordp(Dr)=d1ord_p(Dr) = d − 1.

Now we want the derivatives of gng_n and hnh_n: we have Dgn=2nhnDg_n = 2nh_n and Dhn=n(3gn2+A)Dh_n = n(3g^2_n + A).

We also need a rational function that will operate as a uniformizer at (PQ)(P − Q): suppose uu is a uniformizer at PP. Then the rational function TQ(u)T_Q(u) defined by [TQ(u)](R)=u(R+Q)[T_Q(u)] (R) = u(R + Q) is a uniformizer at PQP − Q.

Finally we can have div(gmgn)div(g_m − g_n):

Say we write E[n]⟨E[n]⟩ to denote the divisor whose nonzero entries are the points of E[n]E[n], each with coefficient one. Then div(gmgn)=E[m+n]+E[mn]2E[m]2E[n]div (g_m − g_n) = ⟨E[m + n]⟩ + ⟨E[m − n]⟩ − 2⟨E[m]⟩ − 2⟨E[n]⟩. This thing also has quite a long and entertaining proof if you are into things like that.

Number of points on EC

If n is prime to pp, then E[n]E[n] has n2n^2 points.

To approach pairing (or at least to poke them) we want to rely on the fact that E[n]ZnZnE[n] ≅ Z_n ⊕ Z_n where stands for isomorphic. It has a long and entertaining proof.

Pairings coming out

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 E/KE/K be an elliptic curve over an algebraically closed field with char K=pK = p.

  • Recall that for an integer nn prime to pp we have an isomorphism E[n]ZnZnE[n] ≅ Z_n ⊕ Z_n.

  • Let QE[n]Q ∈ E[n] be a point on EC and fQK(E)f_Q ∈ K(E) be a rational function such that the divisor of the rational function div(fQ)=n[Q]n[O]div(f_Q) = n[Q] − n[O].

  • Take the map [n]E(K)E(K)[n] ∶ E(K) → E(K) given by PnPP ↦ nP (it might look somehow affiliated with n-Torsion points hope you still remember them!)

  • This map is surjective.

  • Let QE[n2]Q'∈ E[n^2] be such that nQ=QnQ' = Q.

  • Consider the divisor DQ=([Q+R][R])D_Q' = ∑([Q' + R] − [R]) .

  • The degree of DD is 0 and since #E[n]=n2,(Q+RR)=n2Q=O\#E[n] = n^2, ∑(Q' + R − R) = n^2Q' = O.

  • So there exists a rational function g=gQK(E)g = g_Q ∈ K(E) such that div(gQ)=([Q+R][R])div(g_Q) = ∑([Q' + R] − [R])

  • Consider the rational function fQ[n]K(E)f_Q ○ [n] ∈ K(E).

  • The points RE[n]R ∈ E[n] are poles of fQ[n]f_Q ○ [n] of order nn each.

  • The points X=Q+RX = Q’ + R for RE[n]R ∈ E[n] are those points XX for which nX=QnX = Q.

  • It follows that div(fQ[n])=n([Q+R])n([R])=div(gQn)div(f_Q ○ [n])=n∑([Q' + R]) − n(∑[R]) = div(g_Q^n)

  • Thus, fQ[n]f_Q ○ [n] is a constant multiple of gQng^n_Q and wlog, we may choose fQf_Q such that fQ[n]=gQnf_Q ○ [n] = g^n_Q.

  • Let PE[n]P ∈ E[n], an n-torsion point, and SE(K)S ∈ E(K), a point on EC. Then gQ(S+P)n=fQ(n(S+P))=fQ(nS)=gQ(S)ng_Q(S + P)^n = f_Q (n(S + P)) = f_Q(nS) = g_Q(S)^n

  • so that gQ(S+P)n/gQ(S)n=1g_Q(S + P)^n/g_Q(S)^n = 1.

Finally!!!!!!!!!!

Weil pairing, this is this guy: en(P,Q)=gQ(S+P)/gQ(S)e_n(P, Q) = g_Q(S + P)/g_Q(S) and thus get a function enE[n]×E[n]Ke_n ∶ E[n] × E[n] → K.

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 fQf_Q such that fQ[n]=gQnf_Q ○ [n] = g^n_Q…” 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 𝑌2=𝑋3+2𝑋23𝑋𝑌^2 =𝑋^3+2𝑋^2−3𝑋

Functions g:

But these are not those functions gg but some other functions gg, using their divisors one calculated functions ff:

And then these functions ff are utilized to calculate the pairing:

Conclusion

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.

Subscribe to Lisa Akselrod
Receive the latest updates directly to your inbox.
Nft graphic
Mint this entry as an NFT to add it to your collection.
Verification
This entry has been permanently stored onchain and signed by its creator.
More from Lisa Akselrod

Skeleton

Skeleton

Skeleton