### Optimal Pairings

F. Vercauteren

##### Abstract

In this paper we introduce the concept of an \emph{optimal pairing}, which by definition can be computed using only $\log_2 r/ \varphi(k)$ basic Miller iterations, with $r$ the order of the groups involved and $k$ the embedding degree. We describe an algorithm to construct optimal ate pairings on all parametrized families of pairing friendly elliptic curves. Finally, we conjecture that any non-degenerate pairing on an elliptic curve without efficiently computable endomorphisms different from powers of Frobenius requires at least $\log_2 r/ \varphi(k)$ basic Miller iterations.

Note: Corrected statement of theorem 2

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Tate pairingate pairingelliptic curvesfinite fields
Contact author(s)
frederik vercauteren @ esat kuleuven be
History
2008-03-07: last of 5 revisions
See all versions
Short URL
https://ia.cr/2008/096

CC BY

BibTeX

@misc{cryptoeprint:2008/096,
author = {F.  Vercauteren},
title = {Optimal Pairings},
howpublished = {Cryptology ePrint Archive, Paper 2008/096},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/096}},
url = {https://eprint.iacr.org/2008/096}
}

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