This is a note of blog Exploring Elliptic Curve Pairings. EC pairings introduce a form of “encrypted multiplication”.

Introudction

Pairing let you check certain kinds of more complicated equations on elliptic curve points. For example, if P = G * p, Q = G * q and R = G * r, you can check whether or not p * q = r, having just P, Q and R as inputs. Traditional EC math lets your check linear constraints on the numbers, eg. if if P = G * p, Q = G * q and R = G * r, checking 5 * P + 7 * Q = 11 * R is really checking that 5 * p + 7 * q = 11 * r.

Pairings let you check quadratic constraints, eg. checking e(P, Q) * e(G, G * 5) = 1 is really checking that p * q + 5 = 0. e(P, Q) operator is the paring, also called bilinear map. The word “bilinear” here basically means that it satisfies two constraints: e(P, Q + R) = e(P, Q) * e(P, R) and e(P + Q, R) = e(P, R) * e(Q, R). Note that + and * can be arbitrary operators as long as they are consistent in the usually + and * ways, eg. a + b = b + a, (a * b) * c = a * (b * c), (a * c) + (b * c) = (a + b) * c.

If P, Q, R and S were simple numbers, then making a simple pairing is easy: e(x, y) = 2^xy and it is bilinear. However, simple numbers have no concept of a “public key” or a “one-way function”: knowing x and e(x, y) you can easily find y. We want mathematical objects that are as close as possible to “black boxes”, where you can add, subtract, multiply and divide, but do nothing else. This is where elliptic curves and elliptic curve pairings come in.

EC Pairing

It is possible to make a bilinear map over elliptic curve points — that is, come up with a function e(P, Q) where the inputs P and Q are elliptic curve points, and where the output is what’s called an F_p¹² element.

An EC pairing is a bilinear map G2 x G1 -> Gt where:

  • G1 is an elliptic curve, where points satisfy an equation of the form y² = x³ + b, and where both coordinates are elements of F_p. An F_p element is a simple number whose arithmetic is all done modulo some prime number.
  • G2 is an elliptic curve, where points satisfy the same equation as G1, except where the coordinates are elements of F_p¹² (ie. they are the supercharged complex numbers; we define a new “magic number” w, which is defined by a 12th degree polynomial like w^12 - 18 * w^6 + 82 = 0).
  • Gt is the type of object that the result of the elliptic curve goes into. In the curves that we look at, Gt is F_p¹² (the same supercharged complex number as used in G2).

A divisor of a function basically counts the zeroes and the infinities of the function.

Let P = (P_x, P_y) be a fixed point, f(x, y) = x - P_x where x, y are coordinates of a point. Because P and -P share the same x, so f(P) = f(-P) = 0. For infinite point O, f(O) is infinite. The divisor is [P] + [-P] - 2 * [O]. The [] here means that it is in the set of zeroes and infinities of the funciton. -2 is negative because [O] is infinite twice.

For function f(x, y) = ax + by + c = 0 that passes through P and Q the divisor becomes [P]+ [Q] + [-P-Q] - 3 * [O].

For any two functions F and G, the divisor of F * G is equal to the divisor of F plus the divisor of G: (F * G) = (F) + (G)). For example if f(x, y) = P_x - x, then (f³) = 3 * [P] + 3 * [-P] - 6 * [O]. P and -P are “triple-counted” to account for the fact that approaches 0 at those points “three times as quickly” in a certain mathematical sense.

The Tate pairing is defined as follows:

1
2
3
4
5
(F_P) = n * [P] - n * [O], where n is the order of G1, ie. n * P = O for any P`
(F_Q) = n * [Q] - n * [O]
(g) = [P + Q] - [P] - [Q] + [O]

This means that: F_P^z * F_Q^z = F_(P + Q)^z