Paper 2010/104

Avoiding Full Extension Field Arithmetic in Pairing Computations

Craig Costello, Colin Boyd, Juan Manuel Gonzalez Nieto, and Kenneth Koon-Ho Wong

Abstract

The most costly operations encountered in pairing computations are those that take place in the full extension field $\mathbb{F}_{p^k}$. At high levels of security, the complexity of operations in $\mathbb{F}_{p^k}$ dominates the complexity of the operations that occur in the lower degree subfields. Consequently, full extension field operations have the greatest effect on the runtime of Miller's algorithm. Many recent optimizations in the literature have focussed on improving the overall operation count by presenting new explicit formulas that reduce the number of subfield operations encountered throughout an iteration of Miller's algorithm. Unfortunately, almost all of these operations far outweigh the operations in the smaller subfields. In this paper, we propose a new way of carrying out Miller's algorithm that involves new explicit formulas which reduce the number of full extension field operations that occur in an iteration of the Miller loop, resulting in significant speed ups in most practical situations of between 5 and 30 percent.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
PairingsMiller’s algorithmTate pairingate pairing.
Contact author(s)
craig costello @ qut edu au
History
2010-04-08: revised
2010-03-01: received
See all versions
Short URL
https://ia.cr/2010/104
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/104,
      author = {Craig Costello and Colin Boyd and Juan Manuel Gonzalez Nieto and Kenneth Koon-Ho Wong},
      title = {Avoiding Full Extension Field Arithmetic in Pairing Computations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/104},
      year = {2010},
      url = {https://eprint.iacr.org/2010/104}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.