Elliptic Curve Pairings
From the Ground Up
Elliptic curve bilinear pairings enable unique use cases for elliptic curve cryptography including efficient signature aggregation, single-round multi-party key exchanges, and polynomial commitment schemes used in zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK’s). Despite having profound impacts on the field of cryptography, they are largely shrouded in mystery. Commonly referred to as “moon math”, their implementation details are tucked into a black-box. The algebraic structure of non-degenerate bilinearity can largely be taken at face value, though there is some nuance in both performance and what curves can use what pairings.
In this document, we’ll introduce the fundamental properties necessary to construct an elliptic curve bilinear pairing alongside a few simple, un-optimized python snippets for intuition building. Group theory and subsequently ring theory are good prerequisites, particularly polynomial rings.
Introduction
Elliptic curves and bilinear maps are both quite abstract, there are many elliptic curves and separately many functions give rise to bilinearity. In particular, we are interested in elliptic curves over finite fields which exhibit an intractable elliptic curve discrete logarithm problem (ECDL). Additionally, we are interested in a bilinear map that transforms two elliptic curve points into a scalar such that bilinearity is preserved (more on this in the pairing section), the ECDL problem is still intractable, and it is infeasible to find two non-trivial pairs of elliptic curve points that map to the same scalar output.
Finite Fields
The foundation of all of this is the finite field, also known as the Galois field or prime field. The elements of this field are integers between zero and some prime number ‘p’, arithmetic operations are performed modulo ‘p’, and the field admits the algebraic structures we expect, namely addition and multiplication admit associativity, commutativity, invertibility (subtraction and division, respectively), and that multiplication is distributive over addition.
Note that division of field elements is different than integer division as is it commonly understood. To divide one by two, for example, the result is ‘0.5’, which is not in an integer in the prime field. However, since division is the inverse of multiplication, we only need to find an “inverse” for every number such that multiplying the number and its “inverse” modulo the prime returns 1. For example, if our prime is ‘7’, we can define the inverse of ‘two’ as follows:
p = 7
two = 2
inverse_of_two = 4
assert 1 == (two * inverse_of_two % p)Finding an inverse somewhat efficiently for any element of a large prime field can be done via the Extended Euclidean Algorithm, though this is inefficient to use in practice.
Extension Fields
An extension field is a proper superset of a given field which admits all of the algebraic structures its underlying field admits. A common example used to explain extension fields is the complex numbers as an extension of the real numbers, representable as a degree-1, or 2-coefficient, polynomial where the variable ‘i’ is the imaginary component.
The real numbers exist in the complex numbers where ‘b’ is zero.
class Complex:
a: float
b: float
def __init__(self, a, b):
self.a = a
self.b = b
def from_real(n):
return Complex(n, 0.0)
real_n = 5.0
complex_n = Complex.from_real(real_n)However, the complex numbers are algebraically closed, that is to say they cannot be extended any further.
Finite field extensions are also representable as polynomials. For example, a finite field of degree-1 would be represented as follows.
All of the expected field structures are preserved under polynomial addition and multiplication. Elements of Fp2 are degree-1 polynomials where the 2 coefficients are elements of the base field Fp
class Fp:
p = 7 # some prime
value: int
def __init__(self, value):
self.value = value % p
class Fp2:
a0: Fp
a1: Fp
def __init__(self, a0, a1):
self.a0 = a0
self.a1 = a1
def from_base_field(n):
return Fp2(n, Fp(0))
fp_n = Fp(5)
fp2_n = Fp2.from_base_field(fp_n)However, we can extend finite fields arbitrarily. For example, the field extension of degree-11, with 12 coefficients, would be as follows.
The “Tower of Field Extensions” or “Extension Towers” are referred to in bilinear pairing literature and implementations. This is a strategy in optimizing field extension operations.
In particular, rather than extending the base field directly from Fp to Fp12, implementors will often construct a polynomial with 2 coefficients in Fp, then an extension Fp6 with 3 coefficients in Fp2, then 2 coefficients in Fp6, building a tower of extensions.
The wording is tricky to get right and keep readable, the following notation should represent how each extension field is constructed with lower degree extension fields.
A simplified form in python is as follows.
class Fp:
a: int
# -- snip
class Fp2:
a0: Fp
a1: Fp
# -- snip
class Fp6:
a0: Fp2
a1: Fp2
a2: Fp2
# -- snip
class Fp12:
a0: Fp6
a1: Fp6
# -- snipThis representation is preferred in implementations as it enables divide-and-conquer strategies in computations over Fp12. However, this is an implementation detail, the outcomes are the same.
Elliptic Curves
We define an elliptic curve over finite field element coordinates ‘x’ and ‘y’ such that the following equation holds.
class ECPoint:
a = 1
b = 3
x: int
y: int
is_infty: bool
def __init__(self, x, y, is_infty=False):
assert self.is_on_curve(x, y)
self.x = x
self.y = y
self.is_infty = is_infty
def is_on_curve(self, x, y):
y**2 == x**3 + self.a*(x**2) + self.bThe ‘a’ and ‘b’ coefficients in the equation are carefully chosen such that the number of unique elliptic curve points, or the “subgroup order”, is both large and prime. We refer to the subgroup order as ‘r’, as such, field elements within the field modulo ‘r’ take the following form.
Point Addition
We define point addition as a map from two points to another point in the same curve. Note that this is not just adding the coordinates together, rather it is an equation that satisfies the cyclic group laws.
Intuitively, this can be visualized by a line intersecting an elliptic curve at three points, ‘P’, ‘Q’, and ‘R’ then inverting the ‘y’ coordinate of ‘R’.
Note: The grid uses the real numbers for intuitive visualization. However, in a finite field, the coordinates are only integers between 0 and ‘p’ and appear quite sparse.
We define this equation as follows for points that are not equivalent (that case is in the next section).
Where the lambda is the slope of the intersecting line and the coordinates are the inverse of where it intersects a third time.
Point Doubling
We also define a case in which a point is added to itself.
We succinctly refer to adding a point to itself, or point doubling, as ‘[2]P’. This is also referred to as ‘scalar-point multiplication’ and is the basis for elliptic curve cryptography.
Note that some notations refer to this scalar-point multiplication as exponentiation. We’ll avoid exponential notation for the scope of this article for clarity’s sake, however it is worth knowing the following notations are equivalent.
Note: The grid uses the real numbers for intuitive visualization. However, in a finite field, the coordinates are only integers between 0 and ‘p’ and appear quite sparse.
We define the equation for this as follows.
The Cyclic Group
Finally, we include an abstract “point at infinity”, which visually is represented as adding two points in the vertical direction, that is to say adding a point to its y-coordinate inverse.
However, it is worth noting that the point at infinity is not a concrete point with x and y coordinates, rather it is an abstract identity element for point addition.
With this, we can select a generator point ‘G’ from which we can derive every point in the cyclic group through adding a point to itself repeatedly.
Note we define ‘G1’ as the curve and ‘G’ as the generator point. The reason for using ‘G1’ will be explained in the next section. For now, treat it as interchangeable with ‘E(Fp)’
This cyclic group retains all of the expected laws of a group, in particular, we refer to these with scalars to demonstrate structure and build intuition working up to pairings.
Additionally, point addition between elements of the cyclic group can be represented in two equivalent ways.
Such that the group laws hold in both forms.
Also, note that some optimized elliptic curve software libraries use “projective points” where points are represented in a 3-dimension space. This form allows for optimized point arithmetic. Recall point addition and doubling on affine (2-dimension) points require division to compute ‘lambda’, the slope of the line. Also recall division over finite fields is expensive. However, point addition and doubling on projective (3-dimension) points requires no division. As such, this is a common optimization for elliptic curve arithmetic.
Elliptic Curves Over Field Extensions
Recall that field extensions are a superset of the base field. Just as we can define elliptic curves over the scalars of a prime field of integers, we can do the same for extensions of the prime field with an arbitrary degree.
All of the equations used to compute elliptic curve points can be performed over polynomials where all of the elliptic curve points are composed of polynomials as coordinates. As such, we define the elliptic curve over Fp2 as G2.
Bilinear pairings, defined below, depend on two elliptic curves of the same subgroup order, ‘r’. The problem is, an extension field polynomial of degree-1 has about ‘p’-squared elements and in turn, the elliptic curve defined over them has about ‘r’-squared elements.
However, there is a group-theoretic phenomenon, one which I am under-qualified to explain and which mathematicians describe using the words “magical” and “flourish”, where repeatedly extending the base field eventually results in an extension field such that its elliptic curve once again has the same subgroup order as the original. Likely due to points becoming non-distinct in the larger extension fields.
The number of extensions required for this to happen on a given elliptic curve is called the “embedding degree” and is generally represented as the ‘k’ parameter. For example, the BLS12-381 and BN254 curves have an embedding degree of 12. This embedding degree in particular is a feature that makes a curve “pairing friendly”, further explained in the bilinear pairings section.
Bilinear Pairings
General Bilinear Maps
Before we define the bilinear pairings of elliptic curves, it is important to understand what exactly a bilinear map actually is.
Abstractly, a bilinear map is a function that maps two objects to another object, though with an important structure.
Note we use ‘star’ and ‘diamond’ operators for abstraction purposes. The ‘star’ operator acts on elements of ‘M’, while the ‘diamond’ operator acts on elements of ‘R’.
The structure we care about is the ability to reorder variables in mathematical equations given by the bilinear map.
Elliptic Curve Bilinear Map
In the context of elliptic curves, we use bilinear pairings to map two elliptic curve points to a scalar. However, we also need the property of non-degeneracy, that is, given two distinct points, their pairing should never map to ‘1’. To achieve this, we need to use two elliptic curves with the same subgroup order. Recall that an elliptic curve with an embedding degree of 12 over a base field and an extension field of degree-11 (12 coefficients) has the same subgroup order.
With this, we can map a point in G1 and G12 to a scalar in Fp12. However, computing anything in G12 is computationally expensive. Scalar-point multiplication with a large scalar results in many point doubles and additions which results in many computations of slope and coordinates, each of which are polynomials of degree-11.
Sextic Twist
An optimization in both size and complexity comes from an isomorphism between elliptic curves built on extension fields. That isomorphism is called a twist. This twist enables us to transform an elliptic curve over points of some degree-n into an elliptic curve over points of some degree-m where ‘m’ is less than ‘n’. The maximum degree by which we can reduce this is 6, known as the sextic twist, and it only can happen on curves with an ‘a’ parameter of zero.
Recall that BLS12-381 and BN254 curves have an embedding degree of 12, that is, their extension field elliptic curve with subgroup order ‘r’ has 12 coefficients, which can be reduced to 2 coefficients via the sextic twist. That is to say, the following two pairings are isomorphic.
As such, the bilinear pairing generally used in pairing based elliptic curve cryptography is as follows.
Note that we denote point ‘g1’ in curve ‘G1 and point ‘g2’ in ‘G2’ as generator points in this example, this is to remove ambiguity in which curve is being used.
The Tate Pairing
There are 4 types of pairings, each suitable for different kinds of curves with different parameters. Covering all of them is both beyond the scope of this document and largely unnecessary. Most pairing equations are theoretical, not practical to compute, and some are simply iterations and optimizations on others. So we will focus on the Tate pairing and briefly on an optimized iteration of it, the Optimal Ate pairing.
The Tate Pairing depends on an algorithm known as the Miller loop and an exponentiation step commonly known as the “final exponentiation”. The theory behind this algorithm goes into function divisors which is far beyond the scope of this document, so we define the Tate pairing as follows.
Where the Miller loop computes the following,
and the final exponentiation is by the base field order to the power of the embedding degree minus one, divided by the subgroup order.
The Miller Loop
While a deep dive such as this would ideally contain the reasoning behind the Miller loop, the explanation as to what the Miller loop achieves mathematically goes quite deep into function divisors, projective spaces, and algebraic geometry, which requires many prerequisite concepts and branches of mathematics that would significantly increase the size of this document and frankly that I do not yet fully understand. As such, I propose a compromise; the Miller loop will be explained in its implementation but the reasoning behind it will be delegated to the links at the end of this document.
The implementation of the Miller loop accumulates a scalar in Fp12, denoted as variable ‘f’.
A line function is used to accumulate values into ‘f’ and can be visually represented as similar to point arithmetic, where a line either crosses two points (addition) or is at the tangent of one point (doubling), which we use to evaluate at a third point.
def line_function(p, q, t):
# 'p + q'
if p.x != q.x:
lam = (q.y - p.y) / (q.x - p.x)
return lam * (t.x - p.x) - (t.y - p.y)
# 'p + p'
elif p.y == q.y:
lam = 3 * (p.x**2) / (2 * p.y)
return lam * (t.x - p.x) - (t.y - p.y)
# 'p + -p'
else:
pass
return t.x - p.xThe ‘f’ scalar starts at one and accumulates the evaluations of the line function as follows. We loop over the bits of the subgroup order ‘r’. If the bit is zero, we simply double the ‘t’ point and evaluate the line function. If the bit is one, we double the ‘t’ point and evaluate the line function, then add the ‘t’ point to ‘p’ and evaluate the line function again.
r = .. # embedding degree
r_bits = bin(r)[2:]
def miller_loop(p, q):
f = Fp12.one()
t = p
for bit in r_bits:
f = (f**2) * line_function(t, t, q)
t = 2 * t
if bit == '1':
f = f * line_function(t, p, q)
t = t + p
return fThe Final Exponentiation
The final exponentiation is not particularly remarkable, though it is computationally intense, performing exponentiation of an Fp12 polynomial to the power of a massive scalar in Fp. This is why field extension towers become such an important optimization, as performing such large exponentiations without them would be much more expensive.
Additionally, research published in early 2024 shows potential in replacing the final exponentiation with a functionally equivalent check that’s significantly cheaper to compute.
Optimizations
In addition to transforming elliptic curve points from affine space to projective space, using field extension towers for cheaper extension field computations, and twist isomorphisms to reduce the extension field degree in elliptic curves for cheaper point arithmetic, there are many other optimizations in elliptic curve bilinear pairings.
The Tate pairing is a more efficient version of the Weil pairing, trading an additional Miller loop out for the final exponentiation. The Ate pairing significantly reduces the iterations performed in the Miller loop from the Tate pairing and the Optimal Ate pairing reduces it further. There are also precomputable values in certain cases when one of the two points in a pairing are fixed.
Conclusion
Elliptic curve pairings are quite a deep and complex niche, it exists at the intersection between elliptic curves and pairing based cryptography in a rather serendipitous way, where curve parameters yield incredibly unlikely combinations of features. Though its implementation details can often be black-boxed, there are nuances in implementations that enable novel optimizations and elliptic curve pairings are an actively developing field. Understanding the fundamentals and building up to pairings is a great start, though there are many things this document could not possibly cover in reasonable time, from function divisors to frobenius endomorphisms to security parameters. There is simply too much to cover all at once.
However, I hope this was informative if only as a foundation in an exploration of elliptic curve pairings.
Here are some invaluable resources I highly recommend in learning more.
BLS12-381 For the Rest of Us: An excellent explanation of BLS12-381 and what a pairing-friendly curve entails.
Pairings for Beginners (PDF): A comprehensive deep dive as to why elliptic curve pairings work.
py_ecc: An Ethereum pairing library over BLS12-381 and BN254 with readable and optimized implementations.
sylow: Warlock’s cutting edge BN254 pairing library with excellent documentation and references to relevant papers and advancements in the field.
Until next time.