Paper 2005/133

Pairing-Friendly Elliptic Curves of Prime Order

Paulo S. L. M. Barreto and Michael Naehrig

Abstract

Previously known techniques to construct pairing-friendly curves of prime or near-prime order are restricted to embedding degree $k \leqslant 6$. More general methods produce curves over $\F_p$ where the bit length of $p$ is often twice as large as that of the order $r$ of the subgroup with embedding degree $k$; the best published results achieve $\rho \equiv \log(p)/\log(r) \sim 5/4$. In this paper we make the first step towards surpassing these limitations by describing a method to construct elliptic curves of prime order and embedding degree $k = 12$. The new curves lead to very efficient implementation: non-pairing cryptosystem operations only need $\F_p$ and $\F_{p^2}$ arithmetic, and pairing values can be compressed to one \emph{sixth} of their length in a way compatible with point reduction techniques. We also discuss the role of large CM discriminants $D$ to minimize $\rho$; in particular, for embedding degree $k = 2q$ where $q$ is prime we show that the ability to handle $\log(D)/\log(r) \sim (q-3)/(q-1)$ enables building curves with $\rho \sim q/(q-1)$.

Note: The new section 3 deals with implementation issues, and suggest that the proposed family of curves are in some aspects more efficient than previously known curves of prime order.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Revised version presented at SAC'2005 and published in LNCS 3897, pp. 319--331, Springer, 2006.
Keywords
elliptic curvespairing-based cryptosystems
Contact author(s)
pbarreto @ larc usp br
History
2006-02-28: last of 6 revisions
2005-05-10: received
See all versions
Short URL
https://ia.cr/2005/133
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/133,
      author = {Paulo S.  L.  M.  Barreto and Michael Naehrig},
      title = {Pairing-Friendly Elliptic Curves of Prime Order},
      howpublished = {Cryptology ePrint Archive, Paper 2005/133},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/133}},
      url = {https://eprint.iacr.org/2005/133}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.