Paper 2009/155

Faster Computation of the Tate Pairing

Christophe Arene, Tanja Lange, Michael Naehrig, and Christophe Ritzenthaler

Abstract

This paper proposes new explicit formulas for the doubling and addition steps in Miller's algorithm to compute the Tate pairing on elliptic curves in Weierstrass and in Edwards form. For Edwards curves the formulas come from a new way of seeing the arithmetic. We state the first geometric interpretation of the group law on Edwards curves by presenting the functions which arise in addition and doubling. The Tate pairing on Edwards curves can be computed by using these functions in Miller's algorithm. Computing the sum of two points or the double of a point and the coefficients of the corresponding functions is faster with our formulas than with all previ ously proposed formulas for pairings on Edwards curves. They are even competitive with all published formulas for pairing computation on Weierstrass curves. We also improve the formulas for Tate pairing computation on Weierstrass curve s in Jacobian coordinates. Finally, we present several examples of pairing-friendly Edwards curves.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
PairingMiller functionexplicit formulasEdwards curves
Contact author(s)
tanja @ hyperelliptic org
History
2010-05-23: last of 3 revisions
2009-04-07: received
See all versions
Short URL
https://ia.cr/2009/155
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/155,
      author = {Christophe Arene and Tanja Lange and Michael Naehrig and Christophe Ritzenthaler},
      title = {Faster Computation of the Tate Pairing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/155},
      year = {2009},
      url = {https://eprint.iacr.org/2009/155}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.