Paper 2010/526

Faster Explicit Formulas for Computing Pairings over Ordinary Curves

Diego F. Aranha, Koray Karabina, Patrick Longa, Catherine H. Gebotys, and Julio López

Abstract

We describe efficient formulas for computing pairings on ordinary elliptic curves over prime fields. First, we generalize lazy reduction techniques, previously considered only for arithmetic in quadratic extensions, to the whole pairing computation, including towering and curve arithmetic. Second, we introduce a new compressed squaring formula for cyclotomic subgroups and a new technique to avoid performing an inversion in the final exponentiation when the curve is parameterized by a negative integer. The techniques are illustrated in the context of pairing computation over Barreto-Naehrig curves, where they have a particularly efficient realization, and also combined with other important developments in the recent literature. The resulting formulas reduce the number of required operations and, consequently, execution time, improving on the state-of-the-art performance of cryptographic pairings by 27%-33% on several popular 64-bit computing platforms. In particular, our techniques allow to compute a pairing under 2 million cycles for the first time on such architectures.

Note: Extended version of Eurocrypt 2011. Typo corrected in formula (2); expanded caption in Table 4.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Efficient software implementationexplicit formulasbilinear pairings
Contact author(s)
plonga @ uwaterloo ca
History
2011-09-12: last of 5 revisions
2010-10-19: received
See all versions
Short URL
https://ia.cr/2010/526
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/526,
      author = {Diego F.  Aranha and Koray Karabina and Patrick Longa and Catherine H.  Gebotys and Julio López},
      title = {Faster Explicit Formulas for Computing Pairings over Ordinary Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2010/526},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/526}},
      url = {https://eprint.iacr.org/2010/526}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.