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
-
CC BY
BibTeX
@misc{cryptoeprint:2008/096,
author = {F. Vercauteren},
title = {Optimal Pairings},
howpublished = {Cryptology {ePrint} Archive, Paper 2008/096},
year = {2008},
url = {https://eprint.iacr.org/2008/096}
}
