Elliptic Nets
November 8th, 2007As always in mathematics, when something turns out to be useful, it’s worth asking whether it can be generalised to a broader setting. For Elliptic Divisibility Sequences, that generalisation is Elliptic Nets. For a free abelian group of finite rank, this is a function W satisfying the condition:
for any p,q,r,s from the group.
(EDS are then recovered as the special case where the chosen group is the integers).
The theory of elliptic nets has been developed extensively by Katherine Stange, and the papers/presentations from her website provide a wealth of information. I’ve been writing a SAGE implementation of her results, from which we need a few key ideas.
What’s remarkable is that it is not just that sequences can be generalised to arrays: the connection to elliptic curves is also preserved. That is, given n distinct points of an elliptic curve, there is a rank n elliptic net corresponding to those points. The terms of the EDS corresponding to each point will appear in the array, but more complicated interactions of the points are also captured. In the rank 1 case, it was possible to estimate heights purely by manipulation of terms of an EDS; in a similar way, routine manipulation of elliptic nets allows for computation of the Tate pairing.
The use of pairings is currently a hot topic in cryptography, with both destructive and constructive applications. The Tate Pairing allows pairs of elements of an elliptic curve group to be mapped to a finite field. In certain cases, and provided the pairing can be computed efficiently, this transplants the Discrete Logarithm Problem (DLP) into an easier environment, thus weakening the cryptosystem. On the other hand, the gap in difficulty between the two DLPs can itself be used to design cryptosystems and protocols, such as Identity based cryptography.
For the theoretical background, I recommend again Stange’s work. The take-home message however, is as follows:
- For a point P of order m on an elliptic curve E, to compute the pairing of P with itself it suffices to recover terms m+1 and m+2 of the EDS associated with P.
- For distinct points P,Q on an elliptic curve E with P of order m, to compute the pairing of P with Q it suffices to recover elements (m,0) and (m,1) of the elliptic net associated with P and Q.
Thus I have been interested in the sequence/net calculations necessary to recover these quantities. Notice that it is not necessary to compute general (i,j) elements, but only the rows (i,0) and (i,1). The former is in fact the EDS associated with P. Like Shipsey’s algorithm, Stange presents a double-and-add algorithm for the general case of reaching elements (m,0) and (m,1) via successive blocks of elements. For details on this, a possible refinement of my own, and a SAGE implementation, see the next post. This would solve the first problem as well, by choosing a random Q, but the (i,1) terms introduce an unnecessary overhead. Eliminating this gives rise to an alternative to Shipsey’s algorithm for EDS, so I’ve implemented this case separately with an equivalent interface to my existing eds class. It’s unclear which approach is preferable where (although Stange’s is almost definitely the one to use over finite fields), so I hope to furnish both with equivalent functionality and compare their performance for height computation (details to follow). Finally, the wrappers to move from points to nets and compute pairings have been implemented, although I need a lot more test cases to identify potential shortcomings! Ultimately, I’d like to bundle all these ideas together into a more friendly, rank-aware elliptic net class for both roles (heights and pairings).