Chapter status: 👷 in progress 👷

TODO:

Pairings

Pairings have allowed a great number of new applications in cryptography. They were first used by Menezes, Okamoto, and Vanstone [MOV91] to break the discrete logarithm problem in supersingular elliptic curves (this is the so-called MOV attack). Later, they were used constructively by Joux [Jou00] to obtain a tripartite Diffie-Hellman protocol and by Boneh and Franklin [BF03] to obtain an identity-based encryption scheme. This got the three of them the Gödel prize in 2013.

We will start with the abstract definition of pairing groups and then we will see how to construct such groups from specific elliptic curves.

Contents

• Abstract Definition
• Further Resources

Abstract Definition

Let ${\mathbb{G}}_1,$ ${\mathbb{G}}_2,$ and ${\mathbb{G}}_t$ be three cyclic groups of prime order $r.$ For reasons that will become clear later, we will denote ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$ additively and ${\mathbb{G}}_t$ multiplicatively (in particular, ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$'s identity elements are denoted $0$ while ${\mathbb{G}}_t$'s identity element is denoted $1).$ A pairing is an efficiently computable function $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_t$ which satisfies two properties:

• non-degeneracy: $P\ne 0$ and $Q\ne 0$ implies $e(P,Q)\ne 1;$
• bilinearity: for every $P_1,P_2\in {\mathbb{G}}_1$ and $Q\in {\mathbb{G}}_2$ and for every $P\in {\mathbb{G}}_1$ and $Q_1,Q_2\in {\mathbb{G}}_2,$ $$\begin{array}{rl}e(P_1+P_2,Q)& =e(P_1,Q)e(P_2,Q)\\ e(P,Q_1+Q_2)& =e(P,Q_1)e(P,Q_2).\end{array}$$

Note that bilinearity implies the (more useful in practice) property that for every $P\in {\mathbb{G}}_1,$ $Q\in {\mathbb{G}}_2,$ and $a,b\in {\mathbb{Z}}_r,$ $$e(aP,bQ)=e(P,Q{)}^{ab}.$$

Non-degeneracy has many other definitions (all equivalent assuming bilinearity), such as:

• $e$ is not the constant function $1,$
• if $G_1$ and $G_2$ are generators of respectively ${\mathbb{G}}_1$ and ${\mathbb{G}}_2,$ then $e(G_1,G_2)$ is a generator of ${\mathbb{G}}_t.$

Constructing groups admitting a pairing is not very hard. For example, take ${\mathbb{G}}_1={\mathbb{G}}_2={\mathbb{Z}}_r$ (the group of integers mod $r$ equipped with addition), take for ${\mathbb{G}}_t$ any cyclic group of order $r,$ let $g$ be a generator of ${\mathbb{G}}_t,$ and define $e(x,y):=g^{xy}.$

However, for being useful from a cryptographic point of view, we need the discrete logarithm problem to be hard in the three groups ${\mathbb{G}}_1,$ ${\mathbb{G}}_2,$ and ${\mathbb{G}}_t.$ (In the example above, while it may be hard in ${\mathbb{G}}_t,$ it is certainly not in ${\mathbb{G}}_1$ and ${\mathbb{G}}_2.$) This is where elliptic curves come to the rescue.

Some more vocabulary: A pairing is said symmetric when ${\mathbb{G}}_1={\mathbb{G}}_2$ and asymmetric when ${\mathbb{G}}_1\ne {\mathbb{G}}_2.$ As we will see, both types can be constructed from elliptic curves. Historically, the first proposed constructions were symmetric, but nowadays the asymmetric type prevails for efficiency reasons. It is an open problem to construct a pairing such that ${\mathbb{G}}_1={\mathbb{G}}_2={\mathbb{G}}_t=\mathbb{G}$ and the discrete logarithm problem is (conjectured) hard in $\mathbb{G}.$

Further Resources

Here are some good resources about pairing-friendly elliptic curves:

• Pairings for beginners by Craig Costello
• Section 5.4 of the Moonmath manual
• Martijn Maas' master thesis
• this post about the security of pairing-friendly curves by Giacomo Pope
• a post about BLS12-381 by Ben Edgington
• a post about BN254 by Jonathan Wang.