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⩽6$. More general methods produce curves over ${\text{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 ${\text{F}}_p$ and ${\text{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 $$ to minimize $$; in particular, for embedding degree $$ where $$ is prime we show that the ability to handle $$ enables building curves with $$.

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.