The other bilinear mappings

Grid-modified 

All of the IBE algorithms that Voltage's products use need a complicated function called a "pairing" to work. A pairing is a bilinear mapping that's not degenerate and isn't too hard to compute. But the term "bilinear" can have more than one meaning. In the context of pairing-based cryptography, it means a function of two variables that's linear in each of them, so that for a bilinear function e you have that

e(ga,gb) = e(g,g)ab

Pairing-based cryptography may be a very active area of research, but that doesn't mean that many people have heard of that particular meaning of "bilinear." A more common meaning describes how Möbius transformations work. These are functions of a complex variable that look like

f(z) = (az + b) / (cz + d)

where a, b, c, and d are complex numbers. Most people probably think of Möbius transformations when they hear the term "bilinear mapping." That's probably why I sometimes get asked questions about Möbius transformations and how they're used in cryptography. And that's why I'm putting this information about Möbius transformations here – to help answer those questions when they come up again. 

Möbius transformations aren't really linear as we usually think of it. The function f(z) = 1/z is a Möbius transformation, for example, but it's not really what we usually think of as being a linear transformation.

But Möbius transformations are very close to being linear transformations. If we write the Möbius transformation

f(z) = (az + b) / (cz + d)

as the matrix

 
a b
c d
 

then lots of things work for Möbius transformations like you'd expect them to for a linear transformation. In particular, we have that

  • The identity Möbius transformation corresponds to the identity matrix.
  • A Möbius transformation has an inverse if and only if its corresponding matrix has an inverse.
  • The inverse of a Möbius transformation with a particular matrix is the Möbius transformation that corresponds to the inverse of that matrix.
  • The composition of two Möbius transformations corresponds to the matrix that you get by multiplying the matrices of the individual transformations.

So we might want to say that Möbius transformations behave almost, but not quite, like linear transformations. But that's not really true. They really are linear transformations, but you need to use projective coordinates to see that.

Suppose that we write a complex number z as z = z1 / z2 and think of (z1,z2) as being a point in a complex projective space. Then we have that

f(z1 / z2) = (a (z1 / z2) + b) / (c (z1 / z2) + d)

= (a z + b z2) / (c z1 + d z2)

= w1 / w2

so that when we do that, the operation of a Möbius transformation is just

 
w1
w2
 
=
 
a b
c d
 
 
z1
z2
 

That gives us the linearity that we'd like. So although Möbius transformations may not look quite like linear transformations, they really are linear transformations. You just need to use projective coordinates to see it.

Leave a Reply

Your email address will not be published. Required fields are marked *