International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Optimal Pairings

Authors:
F. Vercauteren
Download:
URL: http://eprint.iacr.org/2008/096
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-17773,
  title={Optimal Pairings},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography /  Tate pairing, ate pairing, elliptic curves, finite fields},
  url={http://eprint.iacr.org/2008/096},
  note={ frederik.vercauteren@esat.kuleuven.be 13945 received 2 Mar 2008, last revised 7 Mar 2008},
  author={F. Vercauteren},
  year=2008
}