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 $\mathbb{F}_{p}$, in just $2.63$ million of clock cycles on a single core of an Intel Core i7 $2.8$GHz processor, which implies that the pairing computation takes $0.942$msec. 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 = 36t^4 +36t^3 +24t^2 +6t+1$, with $t = 2^{62} - 2^{54} + 2^{44}$. 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
-
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} }