Elliptic Curve Pairing

Open Table of contents

What it is
How it works
Elliptic Curve Pairings and Security
References

What it is

An Elliptic Curve Pairing is a mechanism that takes as input two points from two Elliptic Curves and maps those points to a single number.

Conceptually, one can think of this mapping as the equivalence of Elliptic Curve point multiplication.

How it works

Mathematically, an Elliptic Curve pairing is defined as the mapping of two Elliptic Curve points to an element in another group like a finite field:

e: E_1 \times E_2 \rightarrow \mathbb{F}

where $e$ is the pairing, $E_1$ and $E_2$ are the Elliptic Curves and $\mathbb{F}$ is a finite field.

Elliptic Curve Pairing Visualization

Note that the Elliptic Curves $E_1$ and $E_2$ don’t have to be different. Also note that once a pairing occurred, the resulting value which is an element in another group can’t be reused for a subsequent pairing.

Elliptic Curve Pairings come with certain properties called bilinear mappings:

\begin{aligned} e(P + Q, R) &= e(P, R)e(Q, R) \\ e(P, R + Q) &= e(P, R)e(P, Q) \\ e(aP, bQ) &= e(P, Q)^{ab} \\ e(aP, bQ) &= e(abP, Q) \\ e(aP, bQ) &= e(bP, aQ) \end{aligned}

where $P$ , $Q$ and $R$ are points on the Elliptic Curve and $a \in \mathbb{Z}$ , $b \in \mathbb{Z}$ .

Using these bilinear mappings we can “move around” the coefficients $a$ and $b$ on those two curves while keeping the mapping the same:

e(aP, bQ) = e(P, Q)^{ab} = e(abP, Q) = e(bP, aQ)

Elliptic Curve Pairings and Security

Leveraging the findings studied so far there’s one special case worth exploring.

It’s the case where both Elliptic Curves are the same and only one point on the curve is considered:

E_1 = E_2 = E

and

P = Q = G

In this case we have:

e(aG, bG) = e(G, G)^{ab} = e(abG, G)

which means that given $aG$ and $bG$ we can distinguish $abG$ from randomness because we know that $e(abG, G) = e(aG, bG)$ but $e(rand, G) \ne e(aG, bG)$ .

The result is that once we have a pairing we can solve the Decisional Diffie Hellman (DDH) problem which states that given $aG$ , $bG$ and $G$ it’s infeasible to distinguish $abG$ from a random point on the Elliptic Curve $E$ .

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.