Skip to content

Elliptic Curve Pairing

Table of contents

Open Table of contents

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:E1×E2Fe: E_1 \times E_2 \rightarrow \mathbb{F}

where ee is the pairing, E1E_1 and E2E_2 are the Elliptic Curves and F\mathbb{F} is a finite field.

Elliptic Curve Pairing Visualization

Note that the Elliptic Curves E1E_1 and E2E_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:

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)abe(aP,bQ)=e(abP,Q)e(aP,bQ)=e(bP,aQ)\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 PP, QQ and RR are points on the Elliptic Curve and aZa \in \mathbb{Z}, bZb \in \mathbb{Z}.

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

e(aP,bQ)=e(P,Q)ab=e(abP,Q)=e(bP,aQ)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:

E1=E2=EE_1 = E_2 = E

and

P=Q=GP = Q = G

In this case we have:

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

which means that given aGaG and bGbG we can distinguish abGabG from randomness because we know that e(abG,G)=e(aG,bG)e(abG, G) = e(aG, bG) but e(rand,G)e(aG,bG)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 aGaG, bGbG and GG it’s infeasible to distinguish abGabG from a random point on the Elliptic Curve EE.

Additional Resources