An Analysis of Affine Coordinates for Pairing Computation

Kristin Lauter, Peter L. Montgomery, and Michael Naehrig

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.

Available format(s)
Category
Implementation
Publication info
Published elsewhere. Pairing 2010
Keywords
Pairing computationMiller's algorithmaffine coordinatesoptimal ate pairingfinite field inversionspairing costmultiple pairingspairing products.
Contact author(s)
mnaehrig @ microsoft com
History
2010-10-12: last of 2 revisions
See all versions
Short URL
https://ia.cr/2010/363

CC BY

BibTeX

@misc{cryptoeprint:2010/363,
author = {Kristin Lauter and Peter L.  Montgomery and Michael Naehrig},
title = {An Analysis of Affine Coordinates for Pairing Computation},
howpublished = {Cryptology ePrint Archive, Paper 2010/363},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/363}},
url = {https://eprint.iacr.org/2010/363}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.