Paper 2006/392

The Tate Pairing via Elliptic Nets

Katherine E. Stange

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.

Note: Minor corrections to publication version. Publication date June 2007: Pairing-Based Cryptography First International Conference, Pairing 2007, Tokyo, Japan, July 2-4, 2007, Proceedings Series: Lecture Notes in Computer Science, Vol. 4575 http://www.springer.com/east/home/computer/security+and+cryptology?SGWID=5-40160-22-173747708-0

Metadata
Available format(s)
PDF PS
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Tate pairingelliptic curve cryptographyelliptic divisibility sequenceelliptic netMiller's algorithmpairing-based cryptography.
Contact author(s)
stange @ math brown edu
History
2007-06-12: last of 7 revisions
2006-11-12: received
See all versions
Short URL
https://ia.cr/2006/392
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/392,
      author = {Katherine E.  Stange},
      title = {The Tate Pairing via Elliptic Nets},
      howpublished = {Cryptology ePrint Archive, Paper 2006/392},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/392}},
      url = {https://eprint.iacr.org/2006/392}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.