Cryptology ePrint Archive: Report 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.

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)

Short URL: ia.cr/2008/096

Discussion forum: Show discussion | Start new discussion