Building up to understand Pairings

The goal of this page is to build up knowledge from a somewhat undergraduate level, and arrive at the concepts needed to understand and intuit the math surrounding some of the more complex cryptographic concepts.

Glossary

Field

A field is a set where you can add, subtract, multiply, and divide (except by zero), and all of the usual algebraic rules work.

Example:

Rational numbers \mathbb{Q}
Real numbers \mathbb{R}
Finite fields such as \mathbb{F}_5 = \{0, 1, 2, 3, 4\}, with addition and multiplication done mod 5.

When we say “finite field” we mean there are finitely many elements. For every prime number p, there’s a finite field with exactly p elements, written \mathbb{F}_p.

Group

A group is a simpler algebraic structure - you only have one operation (like multiplication), and:

You can combine any two elements.
The operation is associative.
There’s an identity element. An element where x op identity = x.
Every element has an inverse.

For example, the nonzero elements of \mathbb{F}_p, written \mathbb{F}_p^*, form a multiplicative group under modular multiplication.

\mathbb{F}_5^* = \{1, 2, 3, 4\} is a cyclic group of order 4.

Cyclic Group

A group is cyclic if there exists one element g (called a generator) such that every element of the group can be written as a power of g.

In \mathbb{F}_5^*, for example, g = 2 works as the generator because,

$\begin{align*} 2^1 \bmod 5 \equiv 2 \\ 2^2 \bmod 5 \equiv 4 \\ 2^3 \bmod 5 \equiv 3 \\ 2^4 \bmod 5 \equiv 1 \end{align*}$

All elements in \{1, 2, 3, 4\} can be expressed as a power of 2, mod 5. So the group is cyclic.

Order of an Element

The order of an element x in a group is the smallest positive integer m such that x^m = 1.

For instance, in \mathbb{F}_5^*, the order of 2 is 4, since 2^4 \equiv 1 \bmod 5.

Roots of Unity

Elements whose power equals 1 are called roots of unity.

The m-th roots of unity are all elements x such that x^m = 1.

In \mathbb{F}_5^*, the 4-th roots of unity are {1, 2, 3, 4}, since each satisfies x^4 = 1 \bmod 5.

Subgroup

A subgroup is a smaller group that lives inside of a larger group and follows the same rules.

Formally, if (\mathbb{G}, \cdot) is a group (under multiplication), a subset \mathbb{H} \subseteq \mathbb{G} is a subgroup if:

The operation of \mathbb{G} keeps you inside \mathbb{H}
- For all a, b \in \mathbb{H}, a \text{ op } b \in \mathbb{H}.
The identity of \mathbb{G} is in \mathbb{H}.
Every element of \mathbb{H} has an inverse, which is also in \mathbb{H}.

For example let’s look at \mathbb{F}_7^* = \{1, 2, 3, 4, 5, 6\}. This group has order 6.

We can see that 3 is a generator of this group,

$\begin{align*} 3^1 \bmod 7 \equiv 3 \\ 3^2 \bmod 7 \equiv 2 \\ 3^3 \bmod 7 \equiv 6 \\ 3^4 \bmod 7 \equiv 4 \\ 3^5 \bmod 7 \equiv 5 \\ 3^6 \bmod 7 \equiv 1 \end{align*}$

So \langle3\rangle = \{1, 2, 3, 4, 5, 6\}. This means 3 is a generator of the whole group \mathbb{F}_7^*, making it a cyclic group.

We can look at a subset of this group, when we use 6 instead of 3.

$\begin{align*} 6^1 \bmod 7 \equiv 6 \\ 6^2 \bmod 7 \equiv 1 \\ 6^3 \bmod 7 \equiv 6 \\ ... \end{align*}$

When raising 6 to higher and higher powers, it will cycle between 6 and 1. This subset, \{1, 6\}, satisfies all subgroup rules:

1 is the identity.
It is closed under multiplication.
Inverses exist, 6^{-1} = 6.

Interestingly, the order of the subgroup (2 in this case) always divides the order of the whole group. This shows off Lagrange’s theorem, which states:

The order of a subgroup divides the order of the whole group.

Finite Field Extensions

Finite fields are fields with a finite number of elements. Every finite field has an order (size) q.

We can generalize finite field extensions by starting not from a prime field \mathbb{F}_p, but from any finite field \mathbb{F}_q of order q = p^m, where p is a prime, and m is a positive integer.

To construct a larger field \mathbb{F}_{q^n}, we adjoin a new element x that satisfies an irreducible polynomial of degree n over \mathbb{F}_q.

Formally,

$\mathbb{F}_{q^n} = \mathbb{F}_q[x] / (f(x))$

where f(x) is irreducible over \mathbb{F}_q.

Every element of \mathbb{F}_{q^n} can be written as a polynomial of degree less than n with coefficients in \mathbb{F}_q:

$a_0 + a_1 x + a_2 x^2 + \dots + a_{n-1}x^{n-1}, \quad a_i \in \mathbb{F}_q$

This way, \mathbb{F}_{q^n} is an n-dimensional vector space over \mathbb{F}_q.

Field Towers

Field extensions can themselves be used as the base field of a further extension. This leads us into the idea of field towers.

Let’s start with a base field \mathbb{F}_p, given some prime p, and we’ll build up to \mathbb{F}_{p^{12}}.

By setting q = p and n = 2, we can extend the base field to \mathbb{F}_{p^2}:

$\mathbb{F}_{p^2} = \mathbb{F}_p[u] / (u^2 + 1)$

Here u is a root of the irreducible polynomial f(u) = u^2 + 1 over \mathbb{F}_p. In this field, multiplication is done modulo u^2 + 1 = 0, so we have the following relation:

$u^2 \equiv -1 \pmod{p}$

Each element of \mathbb{F}_{p^2} can be written as:

$a + b u, \quad a, b \in \mathbb{F}_p$

This only works if -1 is a quadratic non-residue in \mathbb{F}_p. That is, there’s no element x \in \mathbb{F}_p with x^2 = -1. If -1 were a square, then u^2 + 1 would factor and we’d gain no extension. (Concretely, this is the case exactly when p \equiv 3 \pmod 4.)

How to determine this in general, and what it implies for other aspects of elliptic-curve cryptography, is a bit outside the scope of this post.

Now to extend \mathbb{F}_{p^2} by degree 3 to get \mathbb{F}_{p^6}. We define:

$\mathbb{F}_{p^6} = \mathbb{F}_{p^2}[v] / (v^3 - \xi)$

Here \xi is a cubic non-residue (a non-cube) in \mathbb{F}_{p^2}. That is, there’s no element x \in \mathbb{F}_{p^2} such that x^3 = \xi. This is exactly the condition that makes v^3 - \xi irreducible. (In practice \xi is often chosen to be both a non-square and a non-cube, e.g. \xi = u + 1, but it’s the non-cube property that is doing the work here.)

Similar to the 2nd degree extension, arithmetic is performed modulo v^3 - \xi, giving the relation:

$v^3 \equiv \xi$

Each element of \mathbb{F}_{p^6} can be written as:

$(a_0 + a_1 v + a_2 v^2), \quad a_i \in \mathbb{F}_{p^2}$

And finally we land at the final extension, by degree 2, to get \mathbb{F}_{p^{12}}. The math looks nearly the same as our first quadratic extension:

$\mathbb{F}_{p^{12}} = \mathbb{F}_{p^6}[w] / (w^2 - v)$

Here w satisfies w^2 = v. This extension is irreducible because v is a quadratic non-residue in \mathbb{F}_{p^6} - there’s no element of \mathbb{F}_{p^6} whose square is v.

So we have the defining relation:

$w^2 \equiv v$

And each element of \mathbb{F}_{p^{12}} can be expressed as:

$(b_0 + b_1 w), \quad b_i \in \mathbb{F}_{p^6}$

At each layer, the arithmetic re-uses the lower-level operations. For example, multiplication in \mathbb{F}_{p^{12}} can be implemented using three multiplications in \mathbb{F}_{p^6}, which in turn reduce to operations in \mathbb{F}_{p^2}.

But why build fields this way?

This layered approach makes arithmetic much faster. Operations in \mathbb{F}_{p^{12}} can be broken down recursively into smaller and simpler ones - first in \mathbb{F}_{p^6}, then in \mathbb{F}_{p^2}, and finally in the base field \mathbb{F}_p.

Pairing-based cryptography (like BLS12-381 and BN-254) uses these towers extensively:

$\mathbb{F}_p \subset \mathbb{F}_{p^2} \subset \mathbb{F}_{p^6} \subset \mathbb{F}_{p^{12}}.$

Each layer corresponds to a carefully chosen polynomial that makes multiplication and inversion efficient, enabling practical computation of pairings.

Multiplicative Group of a Field

For any finite field \mathbb{F}_{p^n}, the set of nonzero elements forms a multiplicative group:

$\mathbb{F}_{p^n}^* = \mathbb{F}_{p^n} \setminus \{0\}$

Cyclotomic Subgroups

Given a finite field \mathbb{F}_{p^n}, the m-th cyclotomic subgroup is:

$\mu_m(\mathbb{F}_{p^n}) = \{ x \in \mathbb{F}_{p^n}^* \mid x^m = 1 \}$

This can be a bit hard to read, so to paraphrase:

We are saying that \mu_m(\mathbb{F}_{p^n}) is the set of elements of the multiplicative group \mathbb{F}_{p^n}^* whose m-th power equals 1. These are the m-th roots of unity that lie inside of the field \mathbb{F}_{p^n}.

We can show that the set \{x \in G \mid x^m = 1\} is a subgroup with a few simple reductions:

Closure: Given our two elements x and y, if x^m = 1 and y^m = 1, then (xy)^m = {x^m}{y^m} = 1 \cdot 1 = 1.
Identity: 1^m = 1, so 1 is included.
Inverses: if x^m = 1, then (x^{-1})^m = (x^m)^{-1} = 1^{-1} = 1.

Pairings

Pairings are a bit tricky to understand, but they boil down to a very simple concept.

Let’s say we have three groups, G_1, G_2, G_T. G_1 and G_2 are abelian groups, in this case elliptic-curve groups. G_T is a multiplicative group, a subgroup of \mathbb{F}_{p^k}^*.

A pairing is just a map that mixes two group elements and outputs a third element in another group:

$e : G_1 \times G_2 \rightarrow G_T$

Bilinearity

The pairing is bilinear if it satisfies:

$e(aP, bQ) = e(P, Q)^{ab} \quad \forall P \in G_1, Q \in G_2, a, b \in \mathbb{Z}$

When showing bilinearity, we care about the behaviour of e when only one of the inputs changes (either P or Q).

When we “fix” or “pin” one of the inputs, say P \in G_1, we get a map e_P(Q) \mapsto e(P, Q). If this map satisfies the following:

$e_P(Q + Q') = e(P, Q + Q') = e(P, Q) \cdot e(P, Q')$

then it is a “group homomorphism”. When both e_P and e_Q have this property, we know the pairing e is bilinear.

Non-degeneracy

A pairing e : G_1 \times G_2 \rightarrow G_T is non-degenerate if:

$e(P, Q) = 1, \quad \forall Q \in G_2 \Longrightarrow P = 0$

Given a pairing e, if P \neq 0, then there exists at least one Q \in G_2 such that e(P, Q) \neq 1.

When thinking about it intuitvely, every element is “seen” by the map. A degenerate pairing would allow a non-zero element in G_1 (or G_2) to always produce the identity, which causes problems when applying pairings to cryptography.

Perfect Pairing

A pairing is perfect if it’s bilinear and non-degenerate in both directions. In other words, every non-zero element of one group produces a unique effect on the other group via the pairing. We can show that any change in one of the inputs will result in a measurable change in the output.

Formally, fixing an element P \in G_1 gives a homomorphism e_P : G_2 \rightarrow G_T defined by Q \mapsto e(P, Q), as described in bilinearity.

Perfectness ensures that no two different P produce the same homomorphism, and similarly for elements of G_2.

Building a Perfect Pairing from Scratch

We can try constructing a perfect pairing from small, concrete groups.

Let’s start with a cyclic additive group:

$A = \mathbb{Z}/3\mathbb{Z} = \{0, 1, 2\}$

where addition is done mod 3. This will be the “source” group in our pairing.

We’ll use the finite field F_7 = \{0, 1, 2, 3, 4, 5, 6\} and take its subgroup of 3rd roots of unity:

$R = \mu_3(\mathbb{F}_7) = \{1, 2, 4\}$

this will serve as our “target” group - the codomain of the pairing.

A group homomorphism f : A \rightarrow R is determined entirely by the image of 1 \in A. Because A has order 3, we must have f(1)^3 = 1, so f(1) can be any of the three elements of R.

That gives us three homomorphisms:

$\begin{align*} f_0(b) &= 1^b \bmod 7 = 2^{0b} \bmod 7 \\ f_1(b) &= 2^b \bmod 7 = 2^{1b} \bmod 7 \\ f_2(b) &= 4^b \bmod 7 = 2^{2b} \bmod 7 \end{align*}$

These form the group Hom(A, R) = \{f_0, f_1, f_2\}, with multiplication defined pointwise:

$(f_i \cdot f_j)(b) = f_i(b)f_j(b)$

This group is cyclic of order 3, generated by f_1.

Afterwards, we define a map

$\phi : A \rightarrow Hom(A, R)$

$\phi(a)(b) = 2^{ab} \bmod 7$

And we can observe what it does:

$\begin{array}{c|ccc} a & \phi(a) \\ \hline 0 & (b \mapsto 1) = f_0\\ 1 & (b \mapsto 2^b) = f_1\\ 2 & (b \mapsto 2^{2b}) = f_2\\ \end{array}$

It’s easy to verify that \phi(a + a') = \phi(a)\phi(a'), so \phi is a homomorphism. Looking at the table above, the three images f_0, f_1, f_2 are all distinct, so \phi is also injective. Since both sides have three elements, an injective map between them must be surjective too, so \phi is an isomorphism.

This is exactly the setup we want for a perfect pairing: there’s an isomorphism between one group and the dual of the other. Now we can define the pairing itself as the evaluation map:

$e(a, b) = \phi(a)(b) = 2^{ab} \bmod 7$

That’s our bilinear pairing

$e : A \times A \rightarrow R$

And if we write out the full table of values:

$\begin{array}{c|ccc} e(a,b) & b=0 & b=1 & b=2 \\ \hline a=0 & 1 & 1 & 1\\ a=1 & 1 & 2 & 4\\ a=2 & 1 & 4 & 2\\ \end{array}$

For the additive group A and multiplicative group R,

$e(a + a', b) = 2^{(a + a')b} = 2^{ab} \cdot 2^{{a'}b} = e(a, b)e(a', b)$

So e is bilinear.

A degenerate pairing would have some non-zero b \in \{1, 2\} such that e(a, b) = 1 for every a \in \{0, 1, 2\}. However it’s trivial to see that for an input like b = 1, we’d need e(a, 1) = 2^{a \cdot 1} = 2^a \equiv 1 to hold for all a. The only a \in \{0, 1, 2\} satisfying 2^a \equiv 1 \bmod 7 is a = 0, so no non-zero a gives e(a,1)=1 — the pairing fails to be degenerate at b=1. You can easily check the same holds for b = 2.

So the pairing is injective in its first argument, and by symmetry it’s also injective in the second argument. This makes e non-degenerate. Each non-zero element of A produces a nontrivial homomorphism into R.

The map

$\begin{align*} A \rightarrow Hom(A, R) \\ a \longmapsto (b \mapsto e(a, b)) \end{align*}$

is exactly our \phi, which we already proved is an isomorphism.

This should confirm that e is perfect: it gives a one-to-one relationship between elements of A and the homomorphisms A \rightarrow R.

In cryptographic cases, A and R are replaced with large cyclic subgroups of elliptic curve groups and field multiplicative groups, respectively.

Application

Now, with a general understanding of what a pairing is and what it represents from a mathematical point of view, what are some real-world applications?

The topic of applications is a deep one, and would require a separate post to describe in depth, going through use cases like Rank-1 Constraint Systems and Quadratic Arithmetic Programs, but an easier one to intuit would be signatures.

Pairing-Based Signatures (BLS)

The BLS scheme (Boneh-Lynn-Shacham) is one of the most elegant uses of a pairing. We fix our three groups G_1, G_2, G_T of prime order r with a pairing e : G_1 \times G_2 \rightarrow G_T, a generator g \in G_2, and a hash function H that maps a message onto a point in G_1. A signer picks a secret key x \in \mathbb{Z}_r and publishes the public key pk = x \cdot g \in G_2. To sign a message m, they hash it onto the curve and scale by the secret key:

$\sigma = x \cdot H(m) \in G_1$

Verification is then a single pairing check, e(\sigma, g) = e(H(m), pk).

This works precisely because of the bilinearity we built up earlier. Expanding the left-hand side and pushing the scalar through the pairing gives:

$e(\sigma, g) =e(x \cdot H(m), g) = e(H(m), g)^x = e(H(m), x \cdot g) = e(H(m), pk)$

so an honest signature always verifies, while a forger who doesn’t know x cannot produce x \cdot H(m) without solving the discrete log in G_1.

The payoff of this approach is being able to aggregate. As the pairing is linear in each argument, a batch of signatures \sigma_i = x_i \cdot H(m_i) can be summed into one short signature \sigma = \sum_i \sigma_i that verifies against all of the public keys at once via e(\sigma, g) = \prod_i e(H(m_i), pk_i).

This ability to compact several signatures into one point is why BLS is often found in blockchains and consensus protocols, where thousands of signatures need to be checked together, i.e. for a certificate of finality.

Conclusion

My intention for this post is for it to be a general summary of the mathematics required to understand the basis of modern cryptography. In the future, I’d love to discuss other properties of groups and fields, ones that are used in interesting corners of cryptography.

I may update this page with further refined examples and new sections. Perhaps it could grow into a small dictionary of terminology.

← Twisted ElGamal and Pedersen Commitments