The Tate Pairing

Elliptic Curves

** E**(F

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 F

** E^{t}**(F

Where *d* is any Quadratic Non Residue mod *q*. This curve has #* E^{t}* =

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 F_{q}*k *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 F_{p}*2 *(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*(F

An example will be useful. The curve is

** E**(F

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

The twisted curve is

** E^{t}**(F

And #** E^{t}** = 154.

This same curve taken over the extension field * E*(F

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

Let *h* = #* E*/

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

The set of distinct points generated by multiplying every element of * G* by

Consider the partitioning of the #* E* points into distinct

The original coset *r** G* is the unique coset that contains

The quotient group **G/***r** G* 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*[

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

The Tate Pairing is *non-degenerate* as for any given **P **not equal to **O,** we can always find a **Q** such that *e _{r}*(

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

*e _{r}*(

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

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 F_{p}*2*, there is a point Q(-*a*,*d*) on the twisted curve defined over F_{p}*. *This is convenient as it means that multiplication of such points can be done on the twisted curve using regular ** E**(

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 *r G*.

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

** E**(F

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

This same curve taken over the extension field * E*(F

In this case the sets ** S** and

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

**P**[*x,y*] = **P*** _{S}* +

Where **P*** _{S}* =

In our case **P*** _{S}* = ((

For a general point **P**[*x,y*]** = P**[(*a,b*),(*c,d*)] of order *r*, *e _{r}*(

Thanks to Paulo Barreto for help with this page.

Comments/Complaints to mscott@indigo.ie