International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: An Analysis of Affine Coordinates for Pairing Computation

Kristin E. Lauter
Peter L. Montgomery
Michael Naehrig
Search ePrint
Search Google
Abstract: In this paper we analyze the use of affine coordinates for pairing computation. We observe that in many practical settings, for example when implementing optimal ate pairings in high security levels, affine coordinates are faster than using the best currently known formulas for projective coordinates. This observation relies on two known techniques for speeding up field inversions which we analyze in the context of pairing computation. We give detailed performance numbers for a pairing implementation based on these ideas, including timings for base field and extension field arithmetic with relative ratios for inversion-to-multiplication costs, timings for pairings in both affine and projective coordinates, and average timings for multiple pairings and products of pairings.
  title={An Analysis of Affine Coordinates for Pairing Computation},
  booktitle={IACR Eprint archive},
  keywords={implementation / Pairing computation, Miller's algorithm, affine coordinates, optimal ate pairing, finite field inversions, pairing cost, multiple pairings, pairing products.},
  note={ 14785 received 22 Jun 2010, last revised 25 Jun 2010},
  author={Kristin E. Lauter and Peter L. Montgomery and Michael Naehrig},