International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On compressible pairings and their computation

Michael Naehrig
Paulo S. L. M. Barreto
Search ePrint
Search Google
Abstract: In this paper we provide explicit formulae to compute bilinear pairings in compressed form, and indicate families of curves where particularly generalised versions of the Eta and Ate pairings due to Zhao \emph{et al.} are especially efficient. With the new formulae it is possible to entirely avoid $\F_{p^k}$ arithmetic during pairing computation on elliptic curves over $\F_p$ with even embedding degree $k$. Using our new method all intermediate results in the Miller loop are represented by just one $\F_{p^{k/2}}$ element and manipulated in compressed form. For certain families of ordinary curves with embedding degree $k = 6m$ all arithmetic can be done in a subfield of size $p^m$ and the representation can be further compressed to two $\F_{p^m}$ elements.
  title={On compressible pairings and their computation},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / pairing-based cryptography, compressible pairings, algebraic tori, Tate pairing, Eta pairing, Ate pairing, twists},
  note={ 13833 received 16 Nov 2007},
  author={Michael Naehrig and Paulo S. L. M. Barreto},