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

Available format(s)
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
See all versions
Short URL
https://ia.cr/2005/133

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.