This is a note of blog Exploring Elliptic Curve Pairings. EC pairings introduce a form of “encrypted multiplication”.
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
* can be arbitrary operators as long as they are consistent in the usually
* ways, eg.
a + b = b + a, (a * b) * c = a * (b * c), (a * c) + (b * c) = (a + b) * c.
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.
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
Q are elliptic curve points, and where the output is what’s called an
An EC pairing is a bilinear map
G2 x G1 -> Gt where:
G1is an elliptic curve, where points satisfy an equation of the form
y² = x³ + b, and where both coordinates are elements of
F_pelement is a simple number whose arithmetic is all done modulo some prime number.
G2is 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).
Gtis the type of object that the result of the elliptic curve goes into. In the curves that we look at,
F_p¹²(the same supercharged complex number as used in
A divisor of a function basically counts the zeroes and the infinities of the function.
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 share the same
f(P) = f(-P) = 0. For infinite point
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.
f(x, y) = ax + by + c = 0 that passes through
Q the divisor becomes
[P]+ [Q] + [-P-Q] - 3 * [O].
For any two functions
G, the divisor of
F * G is equal to the divisor of
F plus the divisor of
(F * G) = (F) + (G)). For example if
f(x, y) = P_x - x, then
(f³) = 3 * [P] + 3 * [-P] - 6 * [O].
-P are “triple-counted” to account for the fact that
0 at those points “three times as quickly” in a certain mathematical sense.
The Tate pairing is defined as follows: