Paper 2008/096

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

Metadata
Available format(s)
PDF PS
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
2008-03-03: received
See all versions
Short URL
https://ia.cr/2008/096
License
Creative Commons Attribution
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.