On the final exponentiation for calculating pairings on ordinary elliptic curves

Michael Scott; Naomi Benger; Manuel Charlemagne; Luis J.  Dominguez Perez; Ezekiel J.  Kachisa

Paper 2008/490

On the final exponentiation for calculating pairings on ordinary elliptic curves

Michael Scott, Naomi Benger, Manuel Charlemagne, Luis J. Dominguez Perez, and Ezekiel J. Kachisa

Abstract

When using pairing-friendly ordinary elliptic curves to compute the Tate and related pairings, the computation consists of two main components, the Miller loop and the so-called final exponentiation. As a result of good progress being made to reduce the Miller loop component of the algorithm (particularly with the discovery of ``truncated loop'' pairings like the R-ate pairing), the final exponentiation has become a more significant component of the overall calculation. Here we exploit the structure of pairing friendly elliptic curves to reduce the computation required for the final exponentiation to a minimum.

Note: Thanks to Yu Chen and Fre Vercauteren for pointing out an error in the sign of x for the BN curves.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published elsewhere. Unknown where it was published
Keywords: Tate Pairing
Contact author(s): mike @ computing dcu ie
History: 2010-08-24: last of 4 revisions; 2008-11-24: received; See all versions
Short URL: https://ia.cr/2008/490
License: CC BY

BibTeX

@misc{cryptoeprint:2008/490,
      author = {Michael Scott and Naomi Benger and Manuel Charlemagne and Luis J.  Dominguez Perez and Ezekiel J.  Kachisa},
      title = {On the final exponentiation for calculating pairings on ordinary elliptic curves},
      howpublished = {Cryptology ePrint Archive, Paper 2008/490},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/490}},
      url = {https://eprint.iacr.org/2008/490}
}