International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The Tate Pairing via Elliptic Nets

Authors:
Katherine E. Stange
Download:
URL: http://eprint.iacr.org/2006/392
Search ePrint
Search Google
Abstract: We derive a new algorithm for computing the Tate pairing on an elliptic curve over a finite field. The algorithm uses a generalisation of elliptic divisibility sequences known as elliptic nets, which are maps from $\Z^n$ to a ring that satisfy a certain recurrence relation. We explain how an elliptic net is associated to an elliptic curve and reflects its group structure. Then we give a formula for the Tate pairing in terms of values of the net. Using the recurrence relation we can calculate these values in linear time. Computing the Tate pairing is the bottleneck to efficient pairing-based cryptography. The new algorithm has time complexity comparable to Miller's algorithm, and is likely to yield to further optimisation.
BibTeX
@misc{eprint-2006-21883,
  title={The Tate Pairing via Elliptic Nets},
  booktitle={IACR Eprint archive},
  keywords={implementation / Tate pairing, elliptic curve cryptography, elliptic divisibility sequence, elliptic net, Miller's algorithm, pairing-based cryptography.},
  url={http://eprint.iacr.org/2006/392},
  note={ stange@math.brown.edu 13676 received 6 Nov 2006, last revised 12 Jun 2007},
  author={Katherine E. Stange},
  year=2006
}