Paper 2010/354

High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves

Jean-Luc Beuchat, Jorge Enrique González Díaz, Shigeo Mitsunari, Eiji Okamoto, Francisco Rodríguez-Henríquez, and Tadanori Teruya

Abstract

This paper describes the design of a fast software library for the computation of the optimal ate pairing on a Barreto--Naehrig elliptic curve. Our library is able to compute the optimal ate pairing over a 254-bit prime field Fp, in just 2.63 million of clock cycles on a single core of an Intel Core i7 2.8GHz processor, which implies that the pairing computation takes 0.942msec. We are able to achieve this performance by a careful implementation of the base field arithmetic through the usage of the customary Montgomery multiplier for prime fields. The prime field is constructed via the Barreto--Naehrig polynomial parametrization of the prime p given as, p=36t4+36t3+24t2+6t+1, with t=262254+244. This selection of t allows us to obtain important savings for both the Miller loop as well as the final exponentiation steps of the optimal ate pairing.

Note: fix typo

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
francisco @ cs cinvestav mx
History
2010-09-13: last of 7 revisions
2010-06-18: received
See all versions
Short URL
https://ia.cr/2010/354
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/354,
      author = {Jean-Luc Beuchat and Jorge Enrique González Díaz and Shigeo Mitsunari and Eiji Okamoto and Francisco Rodríguez-Henríquez and Tadanori Teruya},
      title = {High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/354},
      year = {2010},
      url = {https://eprint.iacr.org/2010/354}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.