Sinon's Blog

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 β„š
  • Real numbers ℝ
  • Finite fields such as 𝔽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 𝔽p.


Group

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

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

For example, the nonzero elements of 𝔽p, written 𝔽pβˆ—, form a multiplicative group under modular multiplication.

𝔽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 𝔽5βˆ—, for example, g = 2 works as the generator because,

21mod5≑222mod5≑423mod5≑324mod5≑1

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

For instance, in 𝔽5βˆ—, the order of 2 is 4, since 24≑1mod5.


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

In 𝔽5βˆ—, the 4-th roots of unity are {1, 2, 3, 4}, since each satisfies x4=1mod5.


Subgroup

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

Formally, if (𝔾,β‹…) is a group (under multiplication), a subset β„βŠ†π”Ύ is a subgroup if:

  1. The operation of 𝔾 keeps you inside ℍ
    • For all a,bβˆˆβ„, aΒ opΒ bβˆˆβ„.
  2. The identity of 𝔾 is in ℍ.
  3. Every element of ℍ has an inverse, which is also in ℍ.

For example let’s look at 𝔽7βˆ—={1,2,3,4,5,6}. This group has order 6.

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

31mod7≑332mod7≑233mod7≑634mod7≑435mod7≑536mod7≑1

So ⟨3⟩={1,2,3,4,5,6}. This means 3 is a generator of the whole group 𝔽7βˆ—, making it a cyclic group.

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

61mod7≑662mod7≑163mod7≑6...

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 𝔽p, but from any finite field 𝔽q of order q=pm, where p is a prime, and m is a positive integer.

To construct a larger field 𝔽qn, we adjoin a new element x that satisfies an irreducible polynomial of degree n over 𝔽q.

Formally,

𝔽qn=𝔽q[x]/(f(x))

where f(x) is irreducible over 𝔽q.

Every element of 𝔽qn can be written as a polynomial of degree less than n with coefficients in 𝔽q:

a0+a1x+a2x2+β‹―+anβˆ’1xnβˆ’1,aiβˆˆπ”½q

This way, 𝔽qn is an n-dimensional vector space over 𝔽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 𝔽p, given some prime p, and we’ll build up to 𝔽p12.

By setting q=p and n=2, we can extend the base field to 𝔽p2:

𝔽p2=𝔽p[u]/(u2+1)

Here u is a root of the irreducible polynomial f(u)=u2+1 over 𝔽p. In this field, multiplication is done modulo u2+1=0, so we have the following relation:

u2β‰‘βˆ’1(modp)

Each element of 𝔽p2 can be written as:

a+bu,a,bβˆˆπ”½p

This only works if βˆ’1 is a quadratic non-residue in 𝔽p. That is, there’s no element xβˆˆπ”½p with x2=βˆ’1. If βˆ’1 were a square, then u2+1 would factor and we’d gain no extension. (Concretely, this is the case exactly when p≑3(mod4).)

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 𝔽p2 by degree 3 to get 𝔽p6. We define:

𝔽p6=𝔽p2[v]/(v3βˆ’ΞΎ)

Here ΞΎ is a cubic non-residue (a non-cube) in 𝔽p2. That is, there’s no element xβˆˆπ”½p2 such that x3=ΞΎ. This is exactly the condition that makes v3βˆ’ΞΎ irreducible. (In practice ΞΎ is often chosen to be both a non-square and a non-cube, e.g. ΞΎ=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 v3βˆ’ΞΎ, giving the relation:

v3≑ξ

Each element of 𝔽p6 can be written as:

(a0+a1v+a2v2),aiβˆˆπ”½p2

And finally we land at the final extension, by degree 2, to get 𝔽p12. The math looks nearly the same as our first quadratic extension:

𝔽p12=𝔽p6[w]/(w2βˆ’v)

Here w satisfies w2=v. This extension is irreducible because v is a quadratic non-residue in 𝔽p6 - there’s no element of 𝔽p6 whose square is v.

So we have the defining relation:

w2≑v

And each element of 𝔽p12 can be expressed as:

(b0+b1w),biβˆˆπ”½p6

At each layer, the arithmetic re-uses the lower-level operations. For example, multiplication in 𝔽p12 can be implemented using three multiplications in 𝔽p6, which in turn reduce to operations in 𝔽p2.

But why build fields this way?

This layered approach makes arithmetic much faster. Operations in 𝔽p12 can be broken down recursively into smaller and simpler ones - first in 𝔽p6, then in 𝔽p2, and finally in the base field 𝔽p.

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

𝔽pβŠ‚π”½p2βŠ‚π”½p6βŠ‚π”½p12.

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 𝔽pn, the set of nonzero elements forms a multiplicative group:

𝔽pnβˆ—=𝔽pnβˆ–{0}

Cyclotomic Subgroups

Given a finite field 𝔽pn, the m-th cyclotomic subgroup is:

ΞΌm(𝔽pn)={xβˆˆπ”½pnβˆ—|xm=1}

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

We are saying that ΞΌm(𝔽pn) is the set of elements of the multiplicative group 𝔽pnβˆ— whose m-th power equals 1. These are the m-th roots of unity that lie inside of the field 𝔽pn.

We can show that the set {x∈G|xm=1} is a subgroup with a few simple reductions:

  1. Closure: Given our two elements x and y, if xm=1 and ym=1, then (xy)m=xmym=1β‹…1=1.
  2. Identity: 1m=1, so 1 is included.
  3. Inverses: if xm=1, then (xβˆ’1)m=(xm)βˆ’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, G1,G2,GT. G1 and G2 are abelian groups, in this case elliptic-curve groups. GT is a multiplicative group, a subgroup of 𝔽pkβˆ—.

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

e:G1Γ—G2β†’GT

Bilinearity

The pairing is bilinear if it satisfies:

e(aP,bQ)=e(P,Q)abβˆ€P∈G1,Q∈G2,a,bβˆˆβ„€

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∈G1, we get a map eP(Q)↦e(P,Q). If this map satisfies the following:

eP(Q+Qβ€²)=e(P,Q+Qβ€²)=e(P,Q)β‹…e(P,Qβ€²)

then it is a β€œgroup homomorphism”. When both eP and eQ have this property, we know the pairing e is bilinear.

Non-degeneracy

A pairing e:G1Γ—G2β†’GT is non-degenerate if:

e(P,Q)=1,βˆ€Q∈G2⟹P=0

Given a pairing e, if Pβ‰ 0, then there exists at least one Q∈G2 such that e(P,Q)β‰ 1.

When thinking about it intuitvely, every element is β€œseen” by the map. A degenerate pairing would allow a non-zero element in G1 (or G2) 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∈G1 gives a homomorphism eP:G2β†’GT defined by Q↦e(P,Q), as described in bilinearity.

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

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=β„€/3β„€={0,1,2}

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

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

R=ΞΌ3(𝔽7)={1,2,4}

this will serve as our β€œtarget” group - the codomain of the pairing.

A group homomorphism f:Aβ†’R is determined entirely by the image of 1∈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:

f0(b)=1bmod7=20bmod7f1(b)=2bmod7=21bmod7f2(b)=4bmod7=22bmod7

These form the group Hom(A,R)={f0,f1,f2}, with multiplication defined pointwise:

(fiβ‹…fj)(b)=fi(b)fj(b)

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

Afterwards, we define a map

ϕ:A→Hom(A,R)

by

Ο•(a)(b)=2abmod7

And we can observe what it does:

aΟ•(a)0(b↦1)=f01(b↦2b)=f12(b↦22b)=f2

It’s easy to verify that Ο•(a+aβ€²)=Ο•(a)Ο•(aβ€²), so Ο• is a homomorphism. Looking at the table above, the three images f0,f1,f2 are all distinct, so Ο• is also injective. Since both sides have three elements, an injective map between them must be surjective too, so Ο• 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)=Ο•(a)(b)=2abmod7

That’s our bilinear pairing

e:A×A→R

And if we write out the full table of values:

e(a,b)b=0b=1b=2a=0111a=1124a=2142

For the additive group A and multiplicative group R,

e(a+aβ€²,b)=2(a+aβ€²)b=2abβ‹…2aβ€²b=e(a,b)e(aβ€²,b)

So e is bilinear.

A degenerate pairing would have some non-zero b∈{1,2} such that e(a,b)=1 for every a∈{0,1,2}. However it’s trivial to see that for an input like b=1, we’d need e(a,1)=2aβ‹…1=2a≑1 to hold for all a. The only a∈{0,1,2} satisfying 2a≑1mod7 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

Aβ†’Hom(A,R)a⟼(b↦e(a,b))

is exactly our Ο•, 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→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 G1,G2,GT of prime order r with a pairing e:G1Γ—G2β†’GT, a generator g∈G2, and a hash function H that maps a message onto a point in G1. A signer picks a secret key xβˆˆβ„€r and publishes the public key pk=xβ‹…g∈G2. To sign a message m, they hash it onto the curve and scale by the secret key:

Οƒ=xβ‹…H(m)∈G1

Verification is then a single pairing check, e(Οƒ,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(Οƒ,g)=e(xβ‹…H(m),g)=e(H(m),g)x=e(H(m),xβ‹…g)=e(H(m),pk)

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

The payoff of this approach is being able to aggregate. As the pairing is linear in each argument, a batch of signatures Οƒi=xiβ‹…H(mi) can be summed into one short signature Οƒ=βˆ‘iΟƒi that verifies against all of the public keys at once via e(Οƒ,g)=∏ie(H(mi),pki).

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
Understanding Manifold-Constrained Hyper-Connections β†’