### Faster Pairing Computations on Curves with High-Degree Twists

Craig Costello, Tanja Lange, and Michael Naehrig

##### Abstract

Research on efficient pairing implementation has focussed on reducing the loop length and on using high-degree twists. Existence of twists of degree larger than $2$ is a very restrictive criterion but luckily constructions for pairing-friendly elliptic curves with such twists exist. In fact, Freeman, Scott and Teske showed in their overview paper that often the best known methods of constructing pairing-friendly elliptic curves over fields of large prime characteristic produce curves that admit twists of degree $3, 4$ or $6$. A few papers have presented explicit formulas for the doubling and the addition step in Miller's algorithm, but the optimizations were all done for the Tate pairing with degree-$2$ twists, so the main usage of the high-degree twists remained incompatible with more efficient formulas. In this paper we present efficient formulas for curves with twists of degree $2, 3, 4$ or $6$. These formulas are significantly faster than their predecessors. We show how these faster formulas can be applied to Tate and ate pairing variants, thereby speeding up all practical suggestions for efficient pairing implementations over fields of large characteristic.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Keywords
PairingsMiller functionsexplicit formulasTate pairingate pairingtwistsWeierstrass curves.
Contact author(s)
michael @ cryptojedi org
History
2010-06-14: last of 3 revisions
See all versions
Short URL
https://ia.cr/2009/615

CC BY

BibTeX

@misc{cryptoeprint:2009/615,
author = {Craig Costello and Tanja Lange and Michael Naehrig},
title = {Faster Pairing Computations on Curves with High-Degree Twists},
howpublished = {Cryptology ePrint Archive, Paper 2009/615},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/615}},
url = {https://eprint.iacr.org/2009/615}
}

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