The Tate Pairing

Elliptic Curves

E(Fq) : y2 = x3+Ax+B

Elliptic curves are considered interesting primarily as an alternative group structure, with certain advantages when it comes to the implementation of common cryptographic protocols. The main advantage is that much smaller keys can be used, as there is no known polynomial-time algorithm for the discrete logarithm problem for the great majority of such curves. Given a point P on a curve E defined over a finite field Fq where q = pm (where p is a large prime) this is the problem of determining a given aP. In most circumstances the points on such a curve form a simple cyclic group. Each point on the curve has an order. This is the smallest positive integer r such that rP = O, where O is the identity point of the group, the so-called point at infinity. The number of points on the curve, the order of the curve, is referred to as #E. Every valid r divides #E. We also need to know the important relationship #E = q+1-t, where t is the trace of the Frobenius, and t is relatively small - a constant for each curve. We note also the "twisted" curve

Et(Fq) : y2 = x3+ d2Ax+ d3B

Where d is any Quadratic Non Residue mod q. This curve has #Et = q+1+t points on it.

So far so good. A rather boring cyclic group.

The Embedding Degree

However something rather magical happens when a curve with the same equation is considered over the field Fqk for a certain value of k. The group structure undergoes a strange blossoming, and takes on a new, more exotic character. The smallest value of k for which this happens is referred to as the embedding degree. For a random curve the embedding degree will be very large. However it can be as small as k=1, and it is not in fact difficult to find curves for any positive value of k. Here for simplicity we concentrate on the particular case k=2 and q=p a prime. In the field Fp2 (called the quadratic extension field) elements are represented as (a,b) which is a+ib where i is the "square root" of a QNR. If p = 3 mod 4 one can conveniently choose the QNR as p-1.

A k=2 curve E(Fp) has p+1-t points on it. Call this set of points S. It contains a subgroup of points of prime order r and a representative of these is a point P. The same curve over E(Fp2) will have #E(Fp2) = (p+1-t)(p+1+t) points on it, as a consequence of Weil's Theorem. For a k=2 curve r exactly divides both p+1 and (p+1-t), and hence necessarily r divides t. And r2 divides #E.

An example will be useful. The curve is

E(F131) : y2 = x3-3x+8

with p =131, r =11, t=22, P(123,100), #E=110. There are points on the curve of order 110, and the group is cyclic. There is a subgroup of order r. The curve is not supersingular.

The twisted curve is

Et(F131) : y2 = x3-3x-8

And #Et = 154.

This same curve taken over the extension field E(Fp2) has 16940=154.110 points on it. And there are no points on the curve of this order - it is not cyclic. We represent a point on this curve as Q[x,y] = Q[(a,b),(c,d)]

Group Structure

There are a couple of ways of considering all these points. But first some notation. The complete set of curve points is called G, of order #E. The set of all points that are transformed to O by multiplication by r ("killed by r") is called G[r]. These are the r-torsion points. Since r is prime, this is all the points of order r plus O. There are r2 such points, and these r2 points can be organised as r+1 distinct cyclic subgroups of order r - they all share O. Note that one of these subgroups is S[r] and consists of all those r-torsion points from the original curve E(Fp) - points of the form Q[(a,0),(c,0)], which are of course on both curves.

Let h = #E/r2 . Then a random point on the curve can be mapped to a point in one of these sub-groups of order r by multiplying it by this co-factor h. For simplicity we assume that r does not divide h.

For our example curve r=11 and h=140.

The set of distinct points generated by multiplying every element of G by r is called rG. The number of elements in rG is h. This is called a coset.

Consider the partitioning of the #E points into distinct cosets. This can be done by adding a random point R to every element of rG. There are exactly r2 such distinct cosets, each with h elements.

The original coset rG is the unique coset that contains O. Every coset contains exactly one r-torsion point. Elements of these cosets are not all of the same order. They do not form a group.

The quotient group G/rG is the group formed of all these cosets.

Finally - the Tate Pairing

The Tate Pairing operates on a pair of points, P of prime order r (a member of G[r]) and a point Q which is a representative member of one of the cosets. It is denoted er(P,Q). It evaluates as an element of the finite field Fp2 of order r - observe that r divides p2-1. Its value is the same irrespective of which element of a particular coset is chosen. Recall that each coset has exactly one r-torsion point. For convenience we will choose P to be a member of S[r] - as it also lies on E(Fp), this makes the Tate Pairing calculation much faster.

However the Tate pairing can evaluate as 1. This will occur if P is a multiple of Q, which will be the case if Q is chosen from a coset whose r-torsion point is also a member of S[r]. For a randomly chosen Q and for large r this is extremely unlikely - the odds are 1/r.

The Tate Pairing is non-degenerate as for any given P not equal to O, we can always find a Q such that er(P,Q) is not 1. Also er(P,P)=1 for P in S[r] (and k > 1).

However probably the most important property of the Tate pairing is bilinearity

er(aP,bQ) = er(P,Q)ab

Note that P must be of order r, but Q need not be.

Which coset to choose Q from? There are computational advantages in choosing points of the form Q[(a,0),(0,d)]. Call the set of points of this form T. It is not difficult to see that if there are p+1-t points of the form Q[(a,0),(c,0)] then there will be p+1+t points of the form Q[(a,0),(0,d)]. Substitute all a<p for x in the curve equation. Then if the RHS is a QR the point is Q[(a,0),(±c,0)], otherwise its Q[(a,0),(0,±d)]. There will always be a subgroup of order r, consisting of points of this form. Q can therefore be chosen as an element of T. Note that points of this form stay in this form under point multiplication, so such a Q will be in a coset supported by an element of T[r].

But wait. There are also p+1+t points on the twisted curve. Is there a connection between the group of points of the form Q[(a,0),(0,d)] and the group of points on the "twisted" curve? Yes there is - they are isomorphic. For every point of the form Q[(a,0),(0,d)] on the curve defined over the quadratic extension field Fp2, there is a point Q(-a,d) on the twisted curve defined over Fp. This is convenient as it means that multiplication of such points can be done on the twisted curve using regular E(Fp) methods.

A diagram might help. The point-at-infinity is in the centre. Twelve subgroups of order 11 radiate out from it. Each of the points in each subgroup support a coset. The point-at-infinity supports the coset rG.

An alternative idea is to use a supersingular curve. For example

E(Fp) : y2 = x3+x

with p =131, r =11, t=0, P(6,22), #E=132. There are points on the curve of order 132, and the group is cyclic. There is a subgroup of order r.

This same curve taken over the extension field E(Fp2) has 17424 (=132.132) points on it. As before there are no points on the curve of this order - it is not cyclic.

In this case the sets S and T are of the same order. But more than that - every point in S can be mapped directly to a point in T of the same order via the automorphism f(x,y) = (-x,0),(0,y). For every point Q[(a,0),(c,0)] in S, there is a point Q[(-a,0),(0,c)] in T. This allows the introduction of the alternative function êr(P,Q) = er(P,f(Q)), where P is a member of S[r] and Q is a member of S. Note that êr(P,P) is not 1.

What about all those other subgroups of order r ? In fact they are of little interest. Any general point P[x,y] = P[(a,b),(c,d)] of order r on the curve can be written as the sum of a point from S and a point from T using the Trace Map.

P[x,y] = PS + PT

Where PS = Trace(P)/k, and PT = P - PS

In our case PS = ((a+ib,c+id)+(a-ib,c-id))/2 (an elliptic curve point addition followed by elliptic curve point division by 2)

For a general point P[x,y] = P[(a,b),(c,d)] of order r, er(P,P) = er(PS,PT). er(PT,PS) which is NOT equal to 1.