Bilinear Pairings

In this series, I explore the algebra behind bilinear pairings on elliptic curves, the essential component for ZK SNARKs. My aim is to make these constructions as easily accessible as possible, and so I am ordering posts in order of difficulty, not necessarily in order of how the concepts are layered together.

In previous posts, I have given an introduction to finite groups and fields, and an introduction to elliptic curves. In the current one, I will tell you about bilinear pairings from an algebraic stand point, but I won’t go into the details of how they are computed in this series. I find you don’t need to know that to operate with them, unless you are optimizing an implementation. I prefer to leave that to dedicated libraries, and choose among them based on my specific requirements: platform, speed, learning curve. For these, a great reference is this paper by some of the best authorities on the field.

Group Structure

Bilinear pairings are functions that take two arguments and return one output, usually denoted by

e(G1, G2) --> GT.

All three of these elements are drawn from finite groups, and historically these can come in 3 configurations, according to the relations between them.

• Type 1: G1 and G2 are the same group, or can easily be converted into each other;
• Type 2: G1 and G2 are different groups; it is possible to efficiently convert an element of G2 into an element of G1 but not the other way around;
• Type 3: G1 and G2 are different groups; there is no known efficient way to compute a general element of any of these groups into an element of the other.

Advances in the last 5 years have made Type 1 pairings either insecure or slower than the Type 3 alternatives. For this reason, Type 1 pairings should no longer be used.

The three groups must be cyclic and have the same prime order, which I’ll denote by r. A group is associated to a single operation, and the groups most familiar to us are addition and multiplication of numbers. Because group elements can be anything, we may not have an intuitition for what that operation does, but it is still useful to think of it as something we can relate to. As a consequence, we often call the group operation either “addition” or “multiplication”, and accordingly we say the group is written in “additive” or “multiplicative” notation.

Notation

When dealing with bilinear pairings, it is standard, although by no means necessary, to consider G1 and G2 as additive groups, and GT as multiplicative. I found the library DIZK to be an exception, and to treat all groups additively. But in any case, this is just a matter of cosmetics: remember that the underlying operation is usually much more involved than a single multiplication or addition, and these names only serve to abstract all that complexity away. Any of them will work just fine.

Since all 3 groups must be cyclic, they must have at least a generator. In additive groups, a generator is a number G such that every element E in the group can be written as a multiple of the generator, that is the result of k additions:

E = kG.

In a multiplicative group, an element is instead a power of the generator, or the result of k multiplications.

E = Gk.

In a similar way, the identity element of an additive group is 0 (or something that evokes 0) and the identity of a multiplicative group is 1.

In this post, I will use E1 for the generator of G1 and E2 for the generator of G2.

Properties of Bilinear Pairings

A bilinear pairing is a function e: G1 x G2 --> GT with the following properties:

• Order:All three groups must have order equal to a prime r.
• Efficiency: the pairing function must be efficiently computable.
• Bilinearity: For any elements P1, P2 of G1 and any elements Q1, Q2 of G2, the following holds true:

  e(P1 + P2, Q1) = e(P1, Q1) e(P2, Q1)
  e(P1, Q1 + Q2) = e(P1, Q1) e(P1, Q2)
  

  This implies the following form, which is more often used (along with some other variants):

  e(aP, bQ) = e(P,Q)ab = e(bP, aQ)
  

• Non-degeneracy: the pairing of the generators of the first two groups is not the identity of the third group. If this were the case, every pairing would result in the same (the identity) element of GT:

  e(E1, E2) != 1T
  

Calculating with Bilinear Pairings

The great thing about pairings is that they can be used to move multiplicative constants from one group to another. This is not obvious at first sight, but once you learn to play with them it becomes really easy to check and calculate with pairings. The arguments of a pairing are two group elements, but using the generators of each group each argument can be written as:

• A scalar constant
• A group type, indicated by its generator

For example:

e(P, Q) = e(aE1, bE2)

Let me illustrate with a simple example.

Diffie-Hellman Key Exchange

In 1976, Whitfield Diffe and Martin Hellman published a paper that revolutionized cryptography, and changed the game for ever, by creating the first application of public-key cryptography. This was a protocol for Key Exchange, allowing two parties who had never shared any secret information to create a common key and send secret messages to each other. This influential protocol is still fundamental today in all of cryptography.

Diffie-Hellman is a simple scheme involving two parties, affectionately called Alice and Bob. They both must use a common definition of a finite group. Just like when using the same messenger or mail server, they don’t have to communicate between each other to do this, they simply access some public definition of the group. This includes the group generator, g:

• Alice chooses her private key to be a random integer, a.
• Bob chooses her private key to be a random integer, b.
• Alice calculates her public key: A = ga and sends it to Bob.
• Bob calculates his public key: B = gb and sends it to Alice.

Now, they can both compute the same common secret, that will be their key.

Alice computes:

S = Ba = (gb)a = gab.

Bob computes:

S = Ab = (ga)b = gab.

The security of this protocol rests on the difficulty of finding a from A, which is currently impossible in practice.

3-Way Diffie-Hellman

Once Diffie-Hellman was well established, people quickly started asking whether they could do the same for more participants. In 2000, Antoine Joux solved this problem for 3 participants, giving the first cryptographic application of bilinear pairings.

With 3 participants, Alice, Bob and Charlie, each with their keys defined analogously as above, standard Diffie-Hellman is not applicable. If Alice and Bob exchange their secret, there is then no way for them to embed Charlie’s private key in there as well. The best they could do is S * C = gab + c but Charlie would, applying the same logic, generate gac+b instead. There would be no match. Pairings can solve this. Each party picks their keys on a pairing-friendly elliptic curve, and send their public key to each other. After this exchange, each party knows these keys:

Alice: a, aG, bG, cG
Bob: b, aG, bG, cG
Charlie: c, aG, bG, cG

Now, each of them can compute the pairing of the other two’s public keys and then multiply it by their own private key. The result is the same. Let’s see why.

For Alice, we have:

e(bG, cG)a = (e(G,G)bc)a = e(G,G)abc

For Bob, a similar calculation gives:

e(aG, cG)b = (e(G,G)ac)b = e(G,G)abc

and analogously for Charlie.

It’s all About Moving Things Around

If you study this example carefully and understand it, you will not have many problems in understanding pairing-based cryptography and checking the correctness of proofs. In the above, I’ve used the generator G, but remember the same manipulation would be valid for any other point: the scalar just migrates from the argument to the outside of the pairing. In the end, it boils down to this:

• Different parties start with the same elements, for example different integers, grouped in different ways.
• Using pairings and exponentiation, all parties can bring all elements together and compute the same result.

Some of these elements will be encoded in an element of the first group; some into an element of the second group; and some will be known outright. Encoded elements can not be known in plain form, that is, from aG it is impossible to recover a (this is the same difficulty problem I referred in the original Diffie-Hellman section). But in the end, everyone will find an encoding of all their elements in the target group, thus getting the same value.

Bilinear Pairings with Zero Elements

Some definitions of bilinearity that use the latter form, with a and b, specifically exclude the cases when either of those constants is 0. This includes, for example, the BCTV14 paper and Wikipedia. Also, some libraries seem unable to compute the pairing when one of the inputs corresponds to the 0 element. But this behaviour is not implied by the first form. For example, we can write:

e(0 E1, Q1)
e(P1 - P1, Q1) = 
e(P1, Q1) * e(-P1, Q1) =
e(a1 E1, Q1) * e(-a1 E1, Q1) =
e(E1, Q1)a1 * e(E1, Q1)-a1 =
e(E1, Q1)(a1 - a1) =
e(E1, Q1)0 = 1T

So, if you ever find yourself dealing with a library that refuses to handle pairings when an argument is 0, you can always test for that case and replace the whole pairing by 1 instead.

It is time for me to say goodbye for today. I hope the above has given you a better understanding of bilinear pairings and cleared a bit of the mystery around them. There are many uses of them in cryptography beyond Snarks, including for example Identity- and Attribute-Based Encryption. They are a fascinating side of cryptography.

As usual, if you like what I write or have any comments, please let me know. Like, share and use it in your own work.

Meanwhile, have fun in your own adventures.