52 Things: Number 14: What is a cryptographic pairing?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. We build on the previous few weeks by introducing the notion of a pairing.

Pairing definition: Given 3 cyclic groups $\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_3$ of order $q$ with generators $g_1,g_2,g_3$ respectively. We say a function $e:\mathbb{G}_1\times\mathbb{G}_2\rightarrow\mathbb{G}_3$ is a pairing if the following hold:

1. [bilinearity] $\forall A,B\in\mathbb{G}_1,C,D\in\mathbb{G}_2$: $e(A+B,C)=e(A,C)\cdot e(B,C)$ and $e(A,C+D)=e(A,C)\cdot e(A,D)$
2. [non-dengeneracy] $e(g_1,g_2)\neq 1$
3. [efficiency] $e$ is efficiently computable

Types of pairing: There are 3 type of pairings that will be described below:

1. $\mathbb{G}_1=\mathbb{G}_2$
2. $\mathbb{G}_1\neq\mathbb{G}_2$ but there is an efficiently computable isomorphism from $\mathbb{G}_2$ to $\mathbb{G}_1$ and maps the generator $g_2$ to $g_1$
3. $\mathbb{G}_1\neq\mathbb{G}_2$ and there is no efficiently computable isomorphism

The last two are asymmetric pairings while the first is a symmetric pairing.

A warning on pairings: It feels like I am always having a warning section in each of my blogs but these are important and I feel should be included. In type 1 (and can be shown similarly for type 2) pairings (this doesn't mean type 3 are safe) the DDH problem (given $g,g^x,g^y,g^z$ does $z=x\cdot y$) is easy since you can check if $e(g^x,g^y)\overset{\$}{=}e(g^z,g)$. Another thing to be careful of is that it is possible to make a pairing that does everything you want it to,

Uses of pairings: Pairings have a wide range of uses, including; cryptanalysis, Identity Based Encryption, Attribute Based Encryption and Leakage Resilient Cryptography.

Instantiation of pairings: The only way we know how to instantiate pairings is over elliptic curves (see the last few blogs in the 52 things series) and this is another reason why elliptic curves have become so desirable in cryptography. More recently Multi-Linear Maps have appeared in the literature which work over different groups. However, that is a story for another time...