High-speed software implementation of the optimal ate pairing over Barreto-Naehrig curves 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.33 million of clock cycles on a single core of an Intel Core i7 2.8GHz processor, which implies that the pairing computation takes 0.832msec. 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.

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 12 articles , 1 standard article )

Showing results 1 to 12 of 12.
Sorted by year (citations)

  1. Duquesne, Sylvain; Ghammam, Loubna: Memory-saving computation of the pairing final exponentiation on BN curves (2016)
  2. Chen, Xiaofeng; Susilo, Willy; Li, Jin; Wong, Duncan S.; Ma, Jianfeng; Tang, Shaohua; Tang, Qiang: Efficient algorithms for secure outsourcing of bilinear pairings (2015)
  3. Karabina, Koray: Squaring in cyclotomic subgroups (2013)
  4. Aranha, Diego F.; Beuchat, Jean-Luc; Detrey, Jérémie; Estibals, Nicolas: Optimal eta pairing on supersingular genus-2 binary hyperelliptic curves (2012)
  5. Aranha, Diego F.; Karabina, Koray; Longa, Patrick; Gebotys, Catherine H.; López, Julio: Faster explicit formulas for computing pairings over ordinary curves (2011)
  6. Aranha, Diego F.; Knapp, Edward; Menezes, Alfred; Rodríguez-Henríquez, Francisco: Parallelizing the Weil and Tate pairings (2011)
  7. Costello, Craig; Lauter, Kristin; Naehrig, Michael: Attractive subfamilies of BLS curves for implementing high-security pairings (2011)
  8. Scott, Michael: On the efficient implementation of pairing-based protocols (2011)
  9. Beuchat, Jean-Luc; González-Díaz, Jorge E.; Mitsunari, Shigeo; Okamoto, Eiji; Rodríguez-Henríquez, Francisco; Teruya, Tadanori: High-speed software implementation of the optimal ate pairing over Barreto-Naehrig curves (2010)
  10. Dominguez Perez, Luis J.; Scott, Michael: Designing a code generator for pairing based cryptographic functions (2010)
  11. Ghosh, Santosh; Mukhopadhyay, Debdeep; Roychowdhury, Dipanwita: High speed flexible pairing cryptoprocessor on FPGA platform (2010)
  12. Naehrig, Michael; Niederhagen, Ruben; Schwabe, Peter: New software speed records for cryptographic pairings (2010)