Bilinear pairing — plenty of equations, one simple idea
Bilinear paring (often referred to as a bilinear map) is a concept that spans different disciplines from linear algebra to cryptography. As such, it has a rather abstract definition across different fields and even within the same ones. This makes it confusing to understand despite the concept being relatively simple.
The first problem when learning about bilinear pairing is that each piece of literature demonstrates it as a different equality. In the context of cryptography, I stumbled upon (among many others) the following equalities:
With the absence of further explanations, I was unable to understand what the bilinearity is, let alone how it was useful. Since I was struggling with seeing any common patterns, I thought maybe I first needed to understand linear maps.
Linear Map
Wikipedia defines a linear map as a unary function f: V -> W for two vector spaces V, W, where u, v are vectors in V, with the following two conditions:
The fact that there are two conditions stems from the fact the vector spaces are often defined over fields, which have two operations. When thinking about it, both say very similar things: f(c.u) = f(u + u + … + u) = f(u) + f(u) + … + f(u), the scalar multiplication is just a shorthand.
Reading further, it explained that the idea for f is to be operation-preserving, meaning the order of operations does not matter.
The last sentence is crucial as it made me realize the concept: all the linear map says is that it does not matter whether I first apply + and then f or vice versa. Once you understand this, you almost understand the bilinear map.
Bilinear Map (Bilinear Pairing)
A bilinear map is a linear map applied to two parameters, where each parameter is linear when the other is held fixed. Here is an example of a bilinear map:
Holding v fixed, the left-hand side of f is a simple linear map. The same holds for the right-hand side.
With that, nothing further has to be said about bilinearity, every other property can be simply derived. The only difference is that some syntactic sugar is added to simplify equations or different operations than + are used.
Consider the following equation:
It seems different from the previous one but it is really just syntactic sugar in the form of scalar multiplication. The c.u is a shorthand for u + u + … + u repeated c times and the equality can be easily shown:
With the first derivation, the second is not even necessary. Just realize that both f(c.u,v) and f(u,c.v) must be the same as c.f(u,v), so they have to be equal.
Syntax in Groups
Going back to our three cryptography-related equalities, the idea is the same, only the syntax differs. For Equality 1, it does not matter whether I first take the power of the parameters and calculate e or calculate e and then take the power. This might seem different because it is moving powers around, but it is not. Consider a=3 and b=2:
The power is a new syntax, and the * is the new operation (really just syntax again), nothing more.
Continuing in the same fashion would actually made you realize that there are further properties:
Try that yourself.
Equality 2 is the same, except that addition (remember scalar multiplication is just an addition) is used instead of power. Anyone familiar with groups can see that they are equivalent, except that Equality 1 is defined using multiplicative notation, and Equality 2 is defined using additive notation. Or in other words, you will just use + instead of *.
Equality 3 is almost the most trivial:
This is all good, except that the original definition uses * instead of +. While this confused me initially, it is a simple matter of syntax. Regarding elliptic curves, paring is often referred to as e: G₁ × G₂ −> Gₜ, where G₁ and G₂ are written using additive notation, and Gₜ is written using multiplicative notation. The group Gₜ thus has * operation, not +. In abstract algebra, */+ can be defined arbitrarily; they can even be the same operation.
What does the pairing function look like?
For elliptic curve applications, I have no idea. I take it as a block box whose properties I know and do not care what it looks like inside. However, to get a feeling of what it might look like, a nice example is a simple multiplication defined over real numbers.
Suppose e is defined as a multiplication of two real numbers; I get a bilinear map with regards to the + operation in both parameters:
For the long sums of equal elements, the scalar multiplication syntax can be used:
While it is standard to use the same notation for scalar multiplication and multiplication of group elements in ℝ, I distinguish them here so they are consistent across the whole post.
Why is that useful?
Now that the idea has been explained, are there any real applications to this innocent-looking property? Well, as it turns out, there are plenty.
For one, it is often a valuable property in linear algebra, where the consequence of linearity (bilinearity) is that it does not matter in what order we do transformations to an object. For example, it does not matter whether we first scale the object and then rotate it, or vice versa.
Other than that, it has some very neat applications in cryptography. One application is that it allows a one-round three-party key agreement. Even more interesting is pairing-based cryptography, especially in so-called BLS signatures, which allows signature aggregation.
Resources
Here I list the resources that helped me the most.
To understand the basic concept behind bilinearity, I would recommend first understanding the linear map, Wikipedia has a very nice article: https://en.wikipedia.org/wiki/Linear_map.
To build upon the understanding of linear maps, and to grasp the intuition for bilinear maps, I would highly recommend this: https://math.stackexchange.com/questions/924266/definition-of-bilinear-maps.
Lastly, if you would like to build your intuitions with regard to some concrete application of the concept, I highly recommend the following two resources, which explore bilinear mapping in BLS signatures:
