Pairings or bilinear maps

Source material originally from Alin’s blog. Adapted by @hariria for this example.

Preliminaries

• You are familiar with cyclic groups of prime order (e.g., elliptic curves)
• Let $\idt$ denote the identity element of the group $\Gr_T$
• Let $x \randget S$ denote randomly sampling an element $x$ from a set $S$
• Recall that $\langle g \rangle = \Gr$ denotes $g$ being a generator of the group $\Gr$

Definition of a pairing

A pairing, also known as a bilinear map, is a function $e : \Gr_1 \times \Gr_2 \rightarrow \Gr_T$ between three groups $\Gr_1, \Gr_2$ and $\Gr_T$ of prime order $p$, with generators $g_1 = \langle \Gr_1 \rangle, g_2 = \langle \Gr_2 \rangle$ and $g_T = \langle \Gr_T \rangle$, respectively.

When $\Gr_1 = \Gr_2$, the pairing is called symmetric. Otherwise, it is asymmetric.

Most importantly, a pairing has two useful properties for cryptography: bilinearity and non-degeneracy.

Bilinearity

Bilinearity requires that, for all $u\in\Gr_1$, $v\in\Gr_2$, and $a,b\in\Zp$:

Non-degeneracy

Non-degeneracy requires that:

Efficiency

Efficiency requires that there exists a polynomial-time algorithm in the size of a group element (i.e.; in $\lambda = \log_2{p}$) that can be used to evaluate the pairing $e$ on any inputs.

History

A mathematician in prison

The history of (cryptographic) pairings begins with a mathematician named André Weil[^Wiki22Weil] who, during World War II, is sent to jail for refusing to serve in the French army. There, Weil, “managed to convince the liberal-minded prison director to put [him] in an individual cell where [he] was allowed to keep [..] a pen, ink, and paper.”

Weil used his newly-acquired tools to define a pairing across two elliptic curve groups. However, what was very odd at that time was that Weil put in a lot of effort to make sure his definition of a pairing is computable. And this extra effort is what made today’s pairing-based cryptography possible¹.

Go to prison, not to university?

Funnily, Weil’s time in jail was so productive that he began wondering if he should spend a few months there every year. Even better, Weil contemplated if he should recommend to the relevant authorities that every mathematician spend some amount of time in jail. Weil writes:

I’m beginning to think that nothing is more conducive to the abstract sciences than prison.

[…]

My mathematics work is proceeding beyond my wildest hopes, and I am even a bit worried - if it’s only in prison that I work so well, will I have to arrange to spend two or three months locked up every year?

In the meantime, I am contemplating writing a report to the proper authorities, as follows: “To the Director of Scientific Research: Having recently been in a position to discover through personal experience the considerable advantages afforded to pure and disinterested research by a stay in the establishments of the Penitentiary System, I take the liberty of, etc. etc.”

You can read all of this and more in his fascinating autobiography, written from his perspective as a mathematician[^Weil92].

From breaking cryptography to building cryptography

Weil’s work was the foundation. But three more developments were needed for pairing-based cryptography to rise.

First development: Miller’s algorithm

In 1985, Victor Miller writes up a manuscript showing that Weil’s pairing, which actually involves evaluating a polynomial of exponential degree, can in fact be computed efficiently in polynomial time[^Mill86Short].

In December 1984, Miller gave a talk at IBM about elliptic curve cryptography where he claimed that elliptic curve discrete logs were more difficult to compute than ordinary discrete logs over finite fields². Miller was challenged by Manuel Blum, who was in the audience, to back up this claim by giving a reduction: i.e., showing that an algorithm $B$ for solving discrete log on elliptic curves can be efficiently turned into another algorithm $A$ for solving discrete logs in finite fields. Such a reduction would imply the problem solved by $B$ (i.e., computing elliptic curve discrete logs) is at least as hard, if not harder, than $A$‘s problem (i.e., computing finite field discrete logs).

Miller set out to find a reduction by thinking about the only thing that related an elliptic curve group and a finite field: the Weil pairing. Funnily, what he quickly realized was that, although the Weil pairing gives a reduction, it’s in the opposite direction: i.e., it turned out an algorithm $A$ for discrete log in finite fields could be efficiently turned into an algorithm $B$ for discrete logs in elliptic curves with the help of the Weil pairing. This “unwanted” reduction is easy to see. Since $e(g^a, g) = e(g,g)^a$, solving discrete log on the elliptic curve element $g_a\in \Gr$ is just a matter of solving it on $e(g,g)^a\in \Gr_T$, which is actually a multiplicative subgroup of a finite field (see the inner details of pairings).

This almost showed the opposite of what Miller sought to prove, potentially destroying elliptic curve cryptography, but fortunately the degree of the extension field that the Weil pairing mapped into was too large, making this “unwanted” reduction inefficient and thus not a reduction after all.

This whole affair got Miller interested in seeing if the Weil pairing could be computed efficiently, which led to the discovery of his algorithm. Interestingly, he submitted this manuscript to FOCS, a top theoretical computer science conference, but the paper got rejected and would not be published until much later in the Journal of Cryptology (according to Miller)³.

Second development: MOV attack

In 1991, Menezes, Vanstone and Okamoto[^MVO91] leverage Miller’s efficient algorithm for evaluating the Weil pairing to break the discrete logarithm assumption on certain elliptic curves in sub-exponential time. This was quite amazing since, at that time, no sub-exponential time algorithms were known for elliptic curves.

Third development: Joux’s tripartite Diffie-Hellman

So far, pairings only seemed useful for cryptanalysis. No one knew how to use them for building (instead of breaking) cryptography.

This changed in 2000, when Joux[^Joux00] used pairings to implement a 1-round key-exchange protocol between three parties, or tripartite Diffie-Hellman. Previously, such 1-round protocols were only known between two parties while three parties required 2 rounds.

From there, an abundance of new, efficient cryptography started pouring over:

• BLS (short) signatures[^BLS01]
• identity-based encryption[^BF01]
• additively-homomorphic encryption with support for one multiplication[^BGN05]
• succinct zero-knowledge proofs[^GGPR12e]

Arithmetic tricks with pairings

There are a few tricks cryptographers often use when dealing with pairings in their proofs of correctness or security of a cryptosystem.

The most obvious trick, “multiplying in the exponent”, comes from the bilinearity property.

Bilinearity also implies the following trick:

Or, alternatively:

Another trick, which is just an analogous way of defining bilinearity, is:

Why does this work? Let $y,z$ denote the discrete logs (w.r.t. $g_2$) of $v$ and $w$, respectively. Then, we have:

Or, alternatively:

Applications of pairings

Tripartite Diffie-Hellman

We have three parties Alice, Bob and Charles with secret keys $a, b$, and $c$ (respectively). They send each other their public keys $g^a, g^b, g^c$ and agree on a shared secret key $k = e(g, g)^{abc}$.⁴

How?

Consider Alice’s point of view. She gets $g^b$ and $g^c$ from Bob and Charles. First, she can use her secret $a$ to compute $g^{ab}$. Second, she can use the pairing to compute $e(g^{ab}, g^c) = e(g, g)^{abc} = k$.

By symmetry, all other players can do the same and agree on the same $k$.

BLS signatures

Boneh, Lynn and Shacham give a very short signature scheme from pairings[^BLS01], which works as follows:

• Assume $\Gr\_2 = \langle g_2 \rangle$ and that there exists a hash function $H : \{0,1\}^* \rightarrow \Gr_1$ modeled as a random oracle.
• The secret key is $s \in \Zp$ while the public key is $\pk = g\_2^s \in \Gr\_2$.
• To sign a message $m$, the signer computes $\sigma = H(m)^s\in \Gr\_1$.

Notice that correctly-computed signatures will always verify since:

See the BLS paper[^BLS01] for how to prove that no attacker can forge BLS signatures given access to $\pk$ and a signing oracle.

Cool properties of BLS signatures

BLS signatures are quite amazing:

1. They are one of the simplest schemes to implement, given access to an elliptic-curve library.
2. One can aggregate many signatures from different public keys on the same message $m$ into a single multi-signature that continues to verify using just 2 pairings.
3. One can even aggregate such signatures across different messages into a single aggregate signature.
   • However, such aggregate signatures take $n+1$ pairings to verify.
4. One can easily and efficiently[^TCZplus20] build a threshold BLS signature scheme, where any subset of $\ge t$ out of $n$ signers can collaborate to sign a message $m$ but no less than $t$ can ever produce a valid signature.
   • Even better, BLS threshold signatures are deterministic and give rise to threshold verifiable random functions (VRFs) which are useful for generating randomness on chain.
5. One can define very-efficient blind-variants of BLS signatures, where the signer can sign a message $m$ without learning the message $m$.
6. BLS signatures are very efficient in practice.
   • As far as I remember, they are the most efficient scheme for (1) multi-signatures, (2) aggregate signatures and (3) threshold signatures
   • For single-signer BLS, they are slower than Schnorr signatures over non-pairing-friendly curves

Identity-based encryption (IBE)

In an IBE scheme, one can encrypt directly to a user-friendly email address (or a phone number), instead of a cumbersome public key which is difficult to remember or type-in correctly.

Boneh and Franklin give a very efficient IBE scheme from pairings[^BF01].

For IBE to work, a trusted third-party (TTP) called a private key generate (PKG) must be introduced, who will issue secret keys to users based on their email addresses. This PKG has a master secret key (MSK) $\msk \in \Zp$ with an associated master public key (MPK) $\mpk = g_2^s$, where $\langle g_2 \rangle = \Gr_2$.

The $\mpk$ is made public and can be used to encrypt a message to any user given their email address. Crucially, the PKG must keep the $\msk$ secret. Otherwise, an attacker who steals it can derive any user’s secret key and decrypt everyone’s messages.

Let $H_1 : \{0,1\}^* \rightarrow \Gr_1^* \text{ and } H_T : \Gr_T \rightarrow \{0,1\}^n$ be two hash functions modeled as random oracles. To encrypt an $n$-bit message $m$ to a user with email address $id$, one computes:

To decrypt, the user with email address $id$ must first obtain their decryption secret key $\dsk_{id}$ from the PKG. For this, we assume the PKG has a way of authenticating the user, before handing them their secret key. For example this could be done via email.

The PKG computes the user’s decryption secret key as:

You can see why correctly-encrypted ciphertexts will decrypt successfully, since:

To see why this scheme is secure under chosen-plaintext attacks, refer to the original paper[^BF01].

How do pairings actually work?

Mostly, I have no idea. How come? Well, I never really needed to know. And that’s the beauty of pairings: one can use them in a black-box fashion, with zero awareness of their internals.

Still, let’s take a small peek inside this black box. Let us consider the popular pairing-friendly BLS12-381 curve[^Edgi22], from the family of BLS curves characterized by Barreto, Lynn and Scott[^BLS02e].

For BLS12-381, the three groups $\Gr_1, \Gr_2, \Gr_T$ involved are:

• The group $\Gr_1$ is a subgroup of an elliptic curve $E(\F_q) = \left\{(x, y) \in (\F_q)^2 \mid y^2 = x^3 + 4 \right\}$ where $\vert\Gr_1\vert = p$
• The group $\Gr_2$ is a subgroup of a different elliptic curve $E'(\F_{q^2}) = \left\{(x, y) \in (\F_{q^2})^2 \mid y^2 = x^3 + 4(1+i) \right\}$ where $i$ is the square root of $-1$ and $\vert\Gr_2\vert = p$.
• The group $\Gr_T$ are all the $p$th roots of unity in $\F_{q^{k}}$, where $k=12$ is called the embedding degree

How does the pairing map across these three groups work? Well, the pairing $e(\cdot,\cdot)$ expands to something like:

It’s useful to know that computing a pairing consists of two steps:

1. Evaluating the base $f_{p, u}(v)$, also known as a Miller loop, in honor of Victor Miller’s work
2. Raising this base to the constant exponent $(q^k - 1)/p$, also known as a final exponentiation.
   • This step is a few times more expensive than the first

For more on the internals, see other resources[^Cost12]$^,$[^GPS08]$^,$[^Mene05].

Implementing pairing-based crypto

This section discusses various implementation-level details that practitioners can leverage to speed up their implementations.

Use asymmetric pairings!

The pairing over BLS12-381 is asymmetric: i.e., $\Gr_1 \ne \Gr_2$ are two different groups (of the same order $p$). However, there also exist symmetric pairings where $\Gr_1 = \Gr_2$ are the same group.

Unfortunately, “such symmetric pairings only exist on supersingular curves, which places a heavy restriction on either or both of the underlying efficiency and security of the protocol”[^BCMplus15e]. In other words, such supersingular curves are not as efficient at the same security level as the curves used in asymmetric pairings.

Therefore, practitioners today, as far as I am aware, exclusively rely on asymmetric pairings due to their higher efficiency when the security level is kept the same.

BLS12-381 performance

I will give a few key performance numbers for the BLS12-381 curve implemented in Filecoin’s (blstrs Rust wrapper around the popular blst library. These microbenchmarks were run on a 10-core 2021 Apple M1 Max using cargo bench.

Pairing computation times

alinush@MacBook [~/repos/blstrs] (master %) $ cargo +nightly bench -- pairing_
running 4 tests
test bls12_381::bench_pairing_final_exponentiation     ... bench:     276,809 ns/iter (+/- 1,911)
test bls12_381::bench_pairing_full                     ... bench:     484,718 ns/iter (+/- 2,510)
test bls12_381::bench_pairing_g2_preparation           ... bench:      62,395 ns/iter (+/- 4,161)
test bls12_381::bench_pairing_miller_loop              ... bench:     148,534 ns/iter (+/- 1,203)

• a Miller loop computation
  • 210 microseconds
• a final exponentiation
  • 276 microseconds

Therefore, a pairing takes around 486 microseconds (i.e., the sum of the two).

Exponentiation times

• $\Gr_1$ exponentiations are the fastest
  • 72 microseconds
• $\Gr_2$ exponentiations are around 2$\times$ slower
  • 136 microseconds
• $\Gr_T$ exponentiations are around 3.5$\times$ slower than in $\Gr_2$
  • 500 microseconds

Multi-exponentiations

This is a well-known optimization that I’m including for completeness.

Specifically, many libraries allow you to compute a product $\prod_{0 < i < k} \left(g_i\right)^{x_i}$ of $k$ exponentiations much faster than individually computing the $k$ exponentiations and aggregating their product.

For example, blstrs seems to be incredibly fast in this regard:

running 4 tests
test bls12_381::bench_g1_multi_exp                     ... bench:     760,554 ns/iter (+/- 47,355)
test bls12_381::bench_g1_multi_exp_naive               ... bench:  18,575,716 ns/iter (+/- 42,688)
test bls12_381::bench_g2_multi_exp                     ... bench:   1,876,416 ns/iter (+/- 58,743)
test bls12_381::bench_g2_multi_exp_naive               ... bench:  35,272,720 ns/iter (+/- 266,279)

• a size-256 multi-exponentiation in $\Gr_1$
  • takes 760 microseconds in total, or 3 microseconds per exponentiation!
  • done naively, it would take 18.5 milliseconds in total, which is $24\times$ longer
• a size-256 multi-exponentiation in $\Gr_2$
  • takes 1.88 milliseconds in total, or 7.33 microseconds per exponentiation!
  • done naively, it would take 35.3 milliseconds, which is $18.8\times$ longer

Group element sizes

• $\Gr_1$ group elements are the smallest
  • e.g., 48 bytes for BLS12-381 or 32 bytes for BN254 curves[^BN06Pair]
• $\Gr_2$ group elements are 2$\times$ larger
  • e.g., 96 bytes on BLS12-381
• $\Gr_T$ elements are 12$\times$ larger
  • In general, for a pairing-friendly curve with embedding degree $k$, they are $k$ times larger

Other operations

• $\Gr_1$ multiplications (recall we are using multiplicative notation for groups, not additive notation)
  • Normal: 565 nanoseconds (when both points are in projective $(X, Y)$ coordinates)
  • Mixed: 438 nanoseconds (when first point is in projective coordinates, second is in affine $(X, Y, Z)$ coordinates)
    • Faster, because saves one projective-to-affine conversion
• $\Gr_2$ multiplications
  • Normal: 1,484 nanoseconds
  • Mixed: 1,095 nanoseconds
• Hashing to $\Gr_1$ takes around 50 microseconds (not accounting for the extra time required to hash down larger messages using SHA2-256)

Switching between $\Gr_1$ and $\Gr_2$

When designing a pairing-based cryptographic protocol, you will want to carefully pick what to use $\Gr_1$ and what to use $\Gr_2$ for.

For example, in BLS signatures, if you want small signatures, then you would compute the signature $\sigma = H(m)^s \in \Gr_1$ and settle for a slightly-larger public key be in $\Gr_2$. On the other hand, if you wanted to minimize public key size, then you would let it be in $\Gr_1$ while taking slightly longer to compute the signature in $\Gr_2$.

Comparison to non-pairing-friendly elliptic curves

When compared to an elliptic curve that does not admit pairings, pairing-friendly elliptic curves are around two times slower.

For example, the popular prime-order elliptic curve group Ristretto255 offers:

ristretto255/basepoint_mul
                        time:   [10.259 µs 10.263 µs 10.267 µs]
 
ristretto255/point_mul  time:   [40.163 µs 40.187 µs 40.212 µs]

• $\approx 2\times$ faster exponentiations of 40 microseconds
  • which can be sped up to 10 microseconds, using precomputation when the exponentiation base is fixed
• 32 byte group element sizes

Multi-pairings

Whenever, we have to compute the product of $n$ pairings, we can first compute the $n$ Miller loops and do a single final exponentiation instead of $n$. This drastically reduces the pairing computation time in many applications.

Conclusion

This blog post was supposed to be just a short summary of the three properties of pairings: bilinearity, non-degeneracy and efficiency.

Unfortunately, I felt compelled to discuss their fascinating history. And I couldn’t let you walk away without seeing a few powerful cryptographic applications of pairings.

After that, I realized practitioners who implement pairing-based cryptosystems might benefit from knowing a little about their internal workings, since some of these details can be leveraged to speed up implementations.

Acknowledgements

I would like to thank Dan Boneh for helping me clarify and contextualize the history around Weil, as well as for his 2015 Simons talk, which inspired me to do a little more research and write this historical account.

Big thanks to:

• Lúcás Meier, Pratyush Mishra, Ariel Gabizon and Dario Fiore for their enlightening points on what “succinct” (S) stands for in SNARKs[^GW10] and for reminding me that SNARKs with $O(1)$ group elements proof size exist from RSA assumptions[^LM18].
• Sergey Vasilyev for pointing out typos in the BLS12-381 elliptic curve definitions.
• @BlakeMScurr for pointing out an incorrect reference to Joux’s work[^Joux00].
• Conrado Guovea for pointing me to Victor Miller’s account of how he developed his algorithm for evaluating the Weil pairing (discussed here).
• Chris Peikert for pointing out that there are plenty-fast IBE schemes out there that do not rely on pairings[^DLP14e].

PS: Twitter threads are a pain to search through, so if I missed acknowledging your contribution, please kindly let me know.