International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Delaying Mismatched Field Multiplications in Pairing Computations

Authors:
Craig Costello
Juan Manuel Gonzalez Nieto
Colin Boyd
Kenneth Koon-Ho Wong
Download:
URL: http://eprint.iacr.org/2010/123
Search ePrint
Search Google
Abstract: Miller's algorithm for computing pairings involves performing multiplications between elements that belong to different finite fields. Namely, elements in the full extension field $\mathbb{F}_{p^k}$ are multiplied by elements contained in proper subfields $\mathbb{F}_{p^{k/d}}$, and by elements in the base field $\mathbb{F}_{p}$. We show that significant speedups in pairing computations can be achieved by delaying these ``mismatched'' multiplications for an optimal number of iterations. Importantly, we show that our technique can be easily integrated into traditional pairing algorithms; implementers can exploit the computational savings herein by applying only minor changes to existing pairing code.
BibTeX
@misc{eprint-2010-23024,
  title={Delaying Mismatched Field Multiplications in Pairing Computations},
  booktitle={IACR Eprint archive},
  keywords={Pairings, Miller’s algorithm, finite field arithmetic, Tate pairing, ate pairing.},
  url={http://eprint.iacr.org/2010/123},
  note={ craig.costello@qut.edu.au 14707 received 5 Mar 2010, last revised 7 Apr 2010},
  author={Craig Costello and Juan Manuel Gonzalez Nieto and Colin Boyd and Kenneth Koon-Ho Wong},
  year=2010
}