Elliptic curves and their pairings

Assume p is a prime larger than 3 , and take some u , v ∈ F p such that 4 u 3 + 27 v 2 ≠ 0 . We look at the equation Y 2 = X 3 + u ⋅ X + v An elliptic curve C is the of set of points ( x , y ) [1] that satisfy such an equation. These curves give us an interesting way to construct groups. The group elements will be the points ( x , y ) ∈ F 2 p that are on the curve, i.e., that satisfy the equation, together with a special point O , that for technical reasons is sometimes referred to as the “point at infinity”, and serves as the identity element, i.e. the zero of the group. Now the question is how we add two points P = ( x 1 , y 1 ) , Q = ( x 2 , y 2 ) to get a third? The addition rule is derived from a somewhat abstract object called the divisor class group of the curve. For our purposes, all you have to know about this divisor class group is that it imposes the following constraint on the definition of addition: The sum of points on any line must be zero, i.e., O. Let us see how the addition rule is derived from this constraint. Look at a vertical line, defined by an equation of the form X = c. Suppose this line intersects the curve at a point P = ( x 1 , y 1 ) . Because the curve equation is of the form Y 2 = f ( X ) , if ( x 1 , y 1 ) is on the curve, so is the point Q := ( x 1 , − y 1 ) . Moreover, since it’s a vertical line and the curve equation is of degree two in Y, we can be sure these are the only points where the line and curve intersect. Thus, we must have P + Q = O which means P = − Q; that is, Q is the inverse of P in the group. Now let us look at points P and Q that have a different first coordinate – that is, x 1 ≠ x 2 , and see how to add them. We pass a line through P and Q. Since the curve is defined by a degree three polynomial in X and already intersects this (non-vertical) line at two points, it is guaranteed to intersect the line at a third point, that we denote R = ( x , y ) , and no other points. So we must have P + Q + R = O, which means P + Q = − R ; and we know by now that − R is obtained from R by flipping the second coordinate from y to − y . Thus, we have derived the addition rule for our group: Given points P and Q , pass a line through them, and then take the “mirror” point of the third intersection point of the line as the addition result. This group is usually called C ( F p ) – as it consists of points on the curve C with coordinates in F p ; but let’s denote it by G 1 from now on. Assume for simplicity that the number of elements in G 1 is a prime number r , and is different from p . These are many times the case, for example in the curve that PriceAI is currently using. In this case, any element g ∈ G 1 different from O generates G 1 . The smallest integer k such that r divides p k − 1 is called the embedding degree of the curve. It is conjectured that when k is not too small, say, at least 6 , then the discrete logarithm problem in G 1 , i.e. finding α from g and α ⋅ g , is very hard. (In BN curves [3] currently used by PriceAI k = 12 .) The multiplicative group of F p k contains a subgroup of order r that we denote G T . We can look at curve points with coordinates in F p k and not just in F p . Under the same addition rule, these points also form a group together with O called C ( F p k ) . Note that C ( F p k ) clearly contains G 1 . Besides G 1 , C ( F p k ) will contain an additional subgroup G 2 of order r (in fact, r − 1 additional subgroups of order r ).

Fix generators g ∈ G 1 , h ∈ G 2 . It turns out that there is an efficient map, called the Tate reduced pairing, taking a pair of elements from G 1 and G 2 into an element of GT, such that

T a t e ( g , h ) = g for a generator g of G T , and given a pair of elements a , b ∈ F r , we have T a t e ( a ⋅ g , b ⋅ h ) = g(ab) .

Defining T a t e is a bit beyond the scope of this series, and relies on concepts from algebraic geometry, most prominently that of divisors. Here’s a sketch of T a t e ’s definition:

Defining T a t e is a bit beyond the scope of this series, and relies on concepts from algebraic geometry, most prominently that of divisors. Here’s a sketch of T a t e ’s definition:

It may not seem at all clear what this definition has to do with the stated properties, and indeed the proof that T a t e has these properties is quite complex. Defining E 1 ( x ) := x ⋅ g , E 2 ( x ) := x ⋅ h , E ( x ) := x ⋅ g , we get a weak version of an HH that supports both addition and multiplication: E 1 , E 2 , E are HHs that support addition, and given the hidings E 1 ( x ) , E 2 ( y ) we can compute E ( x y ) . In other words, if we have the ”right” hidings of x and y we can get a (different) hiding of x y . But for example, if we had hidings of x , y , z we couldn’t get a hiding of x y z .