**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.

**Category / Keywords: **public-key cryptography / Tate pairing, ate pairing, elliptic curves, finite fields

**Date: **received 2 Mar 2008, last revised 7 Mar 2008

**Contact author: **frederik vercauteren at esat kuleuven be

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **Corrected statement of theorem 2

**Version: **20080307:091031 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]