Pairing-Based Cryptography Comes to CIRCL

When we first released CIRCL in 2019, the library offered optimized implementations of core primitives for key exchange and digital signatures. That release was part of a broader effort to put research-grade cryptography to work at Cloudflare, from post-quantum experiments in TLS to Geo Key Manager's zone-based access controls. The latest update to CIRCL expands that foundation considerably, with new packages covering elliptic curve cryptography, pairing-based schemes, and quantum-resistant algorithms.

Pairings are the piece that deserves the most attention here, because they change what elliptic curve systems can do. The cryptographic value they add comes down to a simple limitation in conventional ECC: you can add points and multiply them by scalars, but you cannot multiply one point by another. Scalar multiplication gives you useful linear structure — (a+b)P = aP + bP and b(aP) = a(bP) — and that last identity is what makes Diffie-Hellman key agreement work. But if points could be multiplied directly to turn aP and bP into abP, Diffie-Hellman would collapse instantly.

A pairing provides an intermediate operation that is finally practical to compute. It takes two points and returns an element in a different group:

e : G₁ × G₂ → G_T

What a Bilinear Map Actually Buys You

In a conventional elliptic curve system, everything happens inside a single group G of curve points under addition. A pairing introduces two more: G₁ and G₂ both contain r-torsion points of the curve, and G_T is written multiplicatively — a subgroup of the multiplicative group over a larger finite field, containing the r-roots of unity. Every elliptic curve has some pairing, but only a few make it efficiently computable. Those are the pairing-friendly curves.

The decisive property is bilinearity. For points and scalars, the following hold:

e(P+Q, R) = e(P, R) * e(Q, R)

e(aP, Q) = e(P, Q)^a

And symmetrically for the second operand:

e(P, Q+R) = e(P, Q) * e(P, R)

e(P, bQ) = e(P, Q)^b

A scalar multiplier in either input group escapes to become an exponent in G_T. That structure is exactly what pairings were first exploited for in cryptanalysis: the MOV attack reduces the elliptic curve discrete logarithm problem to one in a finite field. Given kP, an attacker computes g = e(P, Q) and g_k = e(kP, Q) = g^k, then solves the discrete log in G_T. For standard curves like NIST curves or Curve25519 this is not a practical threat, because G_T is enormous and the pairing becomes too inefficient to compute.

The same tool that works as an attack becomes a constructive building block for protocols. The classic demonstration is three-party Diffie-Hellman. Without pairings, Alice, Bob, and Charlie need two communication rounds, forwarding intermediate points so that everyone can eventually derive k = abcP. With a pairing, they do it in one round: each party broadcasts a public point, and each computes a shared value like e(bP, cP)^a, which bilinearity proves equal for all three participants. Joux introduced this one-round tripartite key exchange in 2000.

Pairings also made possible the first practical answer to Shamir's 1984 question about identity-based encryption, which Boneh and Franklin solved in 2001 so that a public key could be an arbitrary string like an email address. More recent deployments include the zk-SNARKs used by Zcash, the public verifiable randomness of drand, compact BLS signatures in Ethereum, and Cloudflare's Geo Key Manager, which relies on a compact broadcast scheme pairings enable.

From Divisors to the Pairing Operation

To implement pairings you need to trace where the bilinear structure comes from. It starts with divisors, formal sums of points on the curve of the form D = Σ nᵢ Pᵢ. The degree of a divisor is the sum of its coefficients. Functions on the curve give rise to principal divisors by counting poles negatively and zeros positively; all principal divisors have degree zero.

The group of degree-zero divisors modulo principal divisors forms the Jacobian. For elliptic curves, a line intersects the curve at three points, and that geometric fact lets every Jacobian element be represented as (P) - (O). This is the origin of the elliptic curve group law.

Functions can be evaluated on divisors by taking a product, and the critical relationship is Weil duality: if two functions f and g have disjoint divisors, then f(div(g)) = g(div(f)). That identity yields the bilinear map. Given an r-torsion point T, there is a function f whose divisor is r(T) - r(O), and one can construct an auxiliary function to obtain the Weil pairing eᵣ(S,T). The Weil pairing is historically foundational but rarely used in practice; more efficient alternatives with distinct G₁ and G₂ groups dominate real implementations.

Parameter Shifts and Curve Families

Pairing-based systems must balance security across three groups, since the discrete log can be attacked in whichever is weakest. Before 2015, Barreto-Naehrig (BN) curves with a 256-bit prime and an extension of degree 12 hit a good efficiency and security balance for 128-bit security. That changed with a 2015 result from Kim and Barbescu that accelerated attacks on finite fields.

The consequence was a parameter shift: fields had to grow roughly from what was a 192-bit security level down to what became the new 128-bit standard. In this new regime, Barreto-Lynn-Scott (BLS) curves with a prime around 384 bits and embedding degree 12 turn out to be faster than BN curves at the same security level. The IETF draft draft-irtf-cfrg-pairing-friendly-curves now specifies parameters for both BN and BLS families across multiple target security levels, giving applications deploying pairing-based cryptography room for agility as attacks improve.

Pairing-Based Cryptography in Go

Pairing-based cryptography has a rich history of implementations, starting with C/C++ libraries like Ben Lynn's PBC, Michael Scott's Miracl, and Diego Aranha's Relic. In Go, Adam Langley's golang.org/x/crypto/bn256 package brought pairings to the standard ecosystem, and our colleague Brendan McMillion's github.com/cloudflare/bn256 significantly improved its performance. But the BN256 curve no longer meets the 128-bit security level due to recent attacks, which pushed us to look for stronger alternatives.

This led to including pairings in CIRCL, built around the BLS12-381 curve. That curve is already widely deployed in zk-SNARK protocols and short signature schemes, which makes our Go implementation interoperable with existing libraries in other languages. Code that exercises the linearity property of a pairing shows how direct the API is to use:

import (
    "crypto/rand"
    "fmt"
    e "github.com/cloudflare/circl/ecc/bls12381"
)

func ExamplePairing() {
    P,  Q := e.G1Generator(), e.G2Generator()
    a,  b := new(e.Scalar), new(e.Scalar)
    aP, bQ := new(e.G1), new(e.G2)
    ea, eb := new(e.Gt), new(e.Gt)

    a.Random(rand.Reader)
    b.Random(rand.Reader)

    aP.ScalarMult(a, P)
    bQ.ScalarMult(b, Q)

    g  := e.Pair( P, Q)
    ga := e.Pair(aP, Q)
    gb := e.Pair( P,bQ)

    ea.Exp(g, a)
    eb.Exp(g, b)
    linearLeft := ea.IsEqual(ga) // e(P,Q)^a == e(aP,Q)
    linearRight:= eb.IsEqual(gb) // e(P,Q)^b == e(P,bQ)

    fmt.Print(linearLeft && linearRight)
    // Output: true
}

The fixed curve parameters open the door to optimizations that aren't practical on general-purpose curves. Prime field arithmetic and the towering construction for extension fields are two areas where we could apply specialized techniques.

Formally verified field arithmetic

Prime field arithmetic is historically one of the trickiest parts of a crypto library to get right. Hand-written implementations have to respect subtle input constraints, and mistakes have caused vulnerabilities in many projects. This is exactly the kind of code that a machine should write and verify.

We used fiat-crypto to generate Go code for addition, subtraction, multiplication, and squaring over the 381-bit prime field of BLS12-381. The tool is invoked by a script in our repository. The generated code is straight-line with no branches, relies on the math/bits package for machine-level instructions, and runs in constant time.

This approach also avoids the generic big.Int package, which is slow, allocates memory dynamically, and does not guarantee constant-time execution. Since the generated code has no branches, there is nothing to leak through timing. Operations not covered by fiat-crypto are simple enough to check manually.

Towering fields

Beyond arithmetic over the base prime field, a pairing needs operations over extension fields. Think of the jump from real numbers to complex numbers: the familiar +, -, *, and / still exist, but are computed differently. Complex numbers are a quadratic extension of the reals — a second floor built on top of the ground floor.

A pairing on BLS12-381 works in a tower of extensions reaching up to F_p^12, where F_p is the base field. The construction follows a chain of moduli:

  • F_p^2 is built as polynomials in F_p[u] reduced modulo u^2 + 1 = 0.
  • F_p^6 is built as polynomials in F_p^2[v] reduced modulo v^3 + u + 1 = 0.
  • F_p^12 can be built either as polynomials in F_p^6[w] reduced modulo w^2 + v = 0, or as polynomials in F_p^4[w] reduced modulo w^3 + v = 0.

The choice of moduli affects the number of operations needed. We implemented the F_p^12 construction that yields the lowest operation count. These higher-level operations are straightforward to implement and verify by hand, though an automated generator like fiat-crypto could help developers less familiar with tower internals — a capability tracked in Issue 904 and Issue 851 of that project.

Miller loop and final exponentiation

We implemented the optimal r-ate pairing, which computes an evaluation f_Q(P) followed by an exponentiation to a fixed power. The function evaluation uses the Miller loop, an algorithm structurally similar to double-and-add scalar multiplication. The value f_Q(P) lives in F_p^12 but needs one more step — the final exponentiation — to become an element of the r-roots of unity.

Because the exponent is fixed per curve, specialists can tune the final exponentiation. In the Miller loop, the elements of F_p^12 being multiplied have a special shape as polynomials: no linear term, and a constant term in F_p^2. We wrote a specialized multiplication that skips the multiplications guaranteed to produce zero, which shortened the pairing computation by 12%.

Products of pairings

Many protocols need a product of several pairings — for multiple signatures, or for cancellation schemes like dual system encodings. Evaluating each pairing separately would repeat the expensive final exponentiation multiple times. Our API therefore accepts vectors of points, computing the intermediate values first and applying the final exponentiation only once to the product.

Handling explicit signs in the product is nearly free: negate one of the input points. General exponents are harder, particularly with side channel protection, but exposing a product interface means future optimization can accelerate the internal computation without changing applications.

Decoding, twists, and subgroup checks

Raw binary inputs must be validated as legitimate points before being used. Checking that a point lies on the curve is straightforward, but confirming it has the required order normally costs an expensive full scalar multiplication. Pairing settings have cleverer options.

For G_2, points have coordinates in F_p^12, but working on a twist E' of the curve E reduces that to operations in the cheaper subfield F_p^2. The twist also gives efficiently computable endomorphisms; for two field multiplications we get an endomorphism that greatly lowers the cost of scalar multiplication.

Sean Bowe found a way to do subgroup checks much more efficiently by combining scalars that zero out r-torsion points, and we implemented his technique.

Hashing to curves

Protocols like the Boneh-Franklin identity-based encryption scheme require a hash function that maps arbitrary strings — email addresses, for instance — to points on an elliptic curve while behaving like a conventional cryptographic hash. Boneh and Franklin's original method worked for groups where the characteristic satisfies p ≡ 2 mod 3, which is restrictive for other curves.

A naive alternative that inverts a curve equation for the x-coordinate has a serious drawback: it runs in variable time because not every x-coordinate produces a square root, so the algorithm must increment a counter and retry. Non-constant time behavior has real consequences; the DragonBlood attack against WPA3 full key recovery is a cautionary example.

Secure hash-to-curve algorithms must be constant time, must always land on the intended group — whether that is the full curve or a subgroup like G_1 or G_2 — and maintain random oracle behavior. The draft-irtf-cfrg-hash-to-curve specification from the IETF Crypto Forum Research Group defines algorithms that meet these criteria for several curves, BLS12-381 included. Our implementation follows that recommendation, incorporating techniques from the broader pairing literature, a good survey of which is Craig Costello's Pairings for Beginners. We expect pairings to matter more as applications of this cryptography keep appearing across the ecosystem.

Looking ahead

The CIRCL library is now available with bilinear pairing support. Beyond pairings, the library already includes other primitives such as HPKE, VOPRF, and Post-Quantum algorithms. The Cloudflare research team will continue work on improving both the performance and the security of the library. If you are using CIRCL in one of your projects, the team is interested in hearing about your use case via research.cloudflare.com.