Path to understanding: elliptic curves, pairings, and BLS signatures

One of the most fun things about working with blockchain technology is the opportunity to tinker around with cutting-edge cryptography technology. Recently, I was fortunate enough to have the opportunity to learn about BLS (Boneh, Lynn, Shacham) signatures.¹ This post serves as a checkpoint in my understanding of the scheme and the concepts that undergird it, as well as a guide for others.

I am not a professional mathematician, so I will not be explaining these topics rigorously or completely. Rather, the goal is to articulate the mental model for working with these primitives for posterity and public edification. Almost as importantly, this article is short, digestible (hopefully), and provides a lot of references for digging deeper.

This article is a light introduction to the concepts necessary to understand Vitalik Buterin’s article about cryptographic pairings.

Groups & finite fields

Most cryptosystems deal with groups in some form. A group basically consists of a set of elements, and an operator that combines two group elements to produce another group element.

For example, the set $\{0, 1, 2, 3, 4\}$ with operation $+ \pmod{5}$ is a group.

The set $\{\text{all rotation \& reflection symmetries of a regular polygon}\}$ with operation $\circ$ (composition) is a group.

Selected topics that are critical to understanding BLS signatures include:

• A generator. This is a group element which, when the group operation is repeatedly applied to it, produces every other group element.
• Abelian groups (the group operation is commutative).

The concept of a group is not only useful for understanding BLS signatures: this mathematical structure is used in many cryptographic schemes, including RSA & ECDSA signature schemes, as well as zero-knowledge proofs.

Groups of integers with mathematical operations like addition or multiplication are called finite fields. When referring to a group with a specific operation, we say “additive group” or “multiplicative group.”

The discrete logarithm problem

So, we have a group and an operator. Let’s say, for example, our group is the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8\}$ and the operation is multiplication $\times \pmod{9}$.

Repeatedly performing the multiplication operation on an element with itself is called exponentiation. The notation for repeatedly multiplying element $x$ with itself $y$ times is $x^y$. For example:

$$ \begin{align*} 2^1 &= 2 &= 2 \pmod{9} \\ 2^2 &= 2 \times 2 &= 4 \pmod{9} \\ 2^3 &= 2 \times 2 \times 2 &= 8 \pmod{9} \\ 2^4 &= 2 \times 2 \times 2 \times 2 &= 7 \pmod{9} \\ 2^5 &= 2 \times 2 \times 2 \times 2 \times 2 &= 5 \pmod{9} \\ \end{align*} $$

As it turns out, this operation is fairly straightforward to understand and implement. However, the same is not true for the inverse: the logarithm.

As a quick refresher, a logarithm is like the opposite of exponentiation. Whereas the exponential expression $x^y$ tells us the value of multiplying $x$ with itself $y$ times, the logarithm, denoted $\log_x{y}$, tells us how many times we need to multiply $x$ with itself to get $y$. That is to say, $x^{\log_x{y}} = y$ for $x > 1, y > 0$.

In normal, non-finite-field mathematics, the logarithm is comparatively easy to calculate, but for finite fields, it is more challenging,² and so much so that its difficulty is the basis for the security of many cryptosystems.

Elliptic curves as groups

Groups don’t have to be rings of integers; they can also be points along a curve. In particular, the points along an elliptic curve can be used to form groups that are quite useful in cryptography.³

An elliptic curve looks like $y^2 = x^3 + ax + b$ for constants $a$ and $b$.⁴ We use points on the curve, along with a special point called “the point at infinity”⁵ to form the membership set.

Now that we have our group members, we need an operation to combine them. Elliptic curve points can be combined using a process called “elliptic curve pointwise addition.”

Recall that the equation for an elliptic curve is a cubic curve (polynomial order 3), so a line (order 1) will intersect it at $3 \times 1 = 3$ points.⁶ We use this fact to define the addition of two points along the curve.

Let the two points we wish to add be $\mathcal{P}$ and $\mathcal{Q}$. We draw a line from $\mathcal{P}$ to $\mathcal{Q}$, and $\mathcal{R}$ is the third point that the line intersects. We set up the equation $\mathcal{P} + \mathcal{Q} + \mathcal{R} = \mathcal{O}$, where $\mathcal{O}$ is the point at infinity (and also happens to be the additive identity ≠ the origin). Solving for $\mathcal{P} + \mathcal{Q}$ gives us $\mathcal{P} + \mathcal{Q} = -\mathcal{R}$. “Negating” a point on the curve means flipping it across the x-axis.⁷

This operation is called elliptic curve pointwise addition, and it is the group operation (also called the “group law”) for elliptic curves.

When repeatedly adding an elliptic curve point to itself, there is a problem analogous to the discrete logarithm problem in finite fields, called the “elliptic curve discrete logarithm problem.”⁸ The difficulty of this problem similarly provides security for some cryptosystems.

Pairings are bilinear maps

A bilinear map is a function $e: \mathbf{G}_1 \times \mathbf{G}_2 \rightarrow \mathbf{G}_T$⁹ that satisfies the following constraints:

$$ \begin{align*} X, X^\prime &\in \mathbf{G}_1 \\ Y, Y^\prime &\in \mathbf{G}_2 \\ a &\in \mathbb{Z} \end{align*} $$ ¹⁰

$$ \begin{align} e(X + X^\prime,Y) &= e(X,Y) \times e(X^\prime,Y) \\ e(X,Y + Y^\prime) &= e(X,Y) \times e(X,Y^\prime) \\ e(aX,Y) &= e(X,Y)^a \\ e(X,aY) &= e(X,Y)^a \\ e(X,Y)^a \ne 1 &\leftrightarrow a \ne 0 \end{align} $$^{11 12}

Lines (3) and (4) are the most interesting for our purposes.¹³ Simply put, we are allowed to freely swap scalar factors between the two parameters of $e$.

One common example of a simple bilinear map on the integers is the function $e(x,y)=2^{xy}$.

For the remainder of this post, $\mathbf{G}_1 = \mathbf{G}_2$, so we’ll just call the input group $\mathbf{G}$. An elliptic curve pairing is a bilinear map where $\mathbf{G}$ is an elliptic curve.¹⁴ Two such pairings are the Weil pairing and the Tate pairing.¹⁵

BLS signatures

The BLS signature scheme uses elliptic curve pairings¹⁶ to describe a simple signature scheme.

A signature scheme is a means of proving that an actor is the originator (or creator, generator, approver, etc.) of a message. This involves the actor using a secret value (a “private key” or “secret key”) to generate a “signature” to distribute with the message. The actor also distributes a “public key” (or “verification key”) which others can use to verify that the signature was generated using the private key, which implies that the signature could only have been generated by the actor.

Setup

Usually predetermined as part of the protocol design.

1. Choose elliptic curve $\mathbf{E}$ with generator $g$.
2. Choose pairing function $e: \mathbf{E} \times \mathbf{E} \rightarrow \mathbf{G}_T$.

Key generation

Performed once by the actor who plans to generate signatures.

1. Choose a private key, scalar $\alpha$.
2. Calculate and distribute public key $p = \alpha g$.

Signing

Performed every time the actor signs a message.

1. Choose message $m \in \mathbf{E}$.¹⁷
2. Calculate and distribute signature $\sigma = \alpha m$.

Verification

Performed by anyone wishing to verify the signature for a message.

1. Check whether $e(p, m) = e(g, \sigma)$:

$$ \begin{align*} e(p, m) &= e(g, \sigma) \\ &= e(g, \alpha m) \\ &= e(g, m)^\alpha \\ &= e(\alpha g, m) \\ &= e(p, m) \end{align*} $$

This scheme has a number of very nice properties, one of which is its efficiency: signatures are quick and easy to generate, and are small in size—just a single point on the elliptic curve. However, because elliptic curves pairings are still quite expensive to compute, verifying signatures is quite slow compared to other signature schemes.

Aggregate signatures can be easily constructed by multiplying signatures together.¹⁸

Threshold signatures (distribute $n$ keyshares, any $t < n$ of them can generate a valid signature) can also be constructed (slightly less simply than aggregate signatures).¹⁹

Additional resources

Videos

• Pairings in Cryptography (Dan Boneh)
• BLS Signatures and Key Sharing with Crypto Pairs (Bill Buchanan)
• Cryptography 101 for Blockchain Developers Part 3/3: Elliptic Curve Pairings (OpenZeppelin)

Articles

• Exploring Elliptic Curve Pairings (Vitalik Buterin) (archive.org)
• What Are Elliptic Curve Pairings? (Zellic) (archive.org)

Books

• Pairings for beginners (Craig Costello) (archive.org)²⁰

I’m a software engineer for NEAR Protocol and a graduate student at the Tokyo Institute of Technology.

Connect with me on Twitter and Mastodon.