Previously known techniques to construct pairing-friendly curves of prime or near-prime order are restricted to embedding degree $k \leq 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 = \log(p)/\log(r) ~ 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 operations need no more than $\F_{p^4}$-arithmetic, and pairing values can be compressed to one third 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) ~ (q − 3)/(q − 1)$ enables building curves with $\rho ~ q/(q − 1)$.

PDF file

In  Selected Areas in Cryptography - SAC 2005

Publisher  Springer
Springer-Verlag

Details

Previous Versions

Paulo S. L. M. Barreto and Michael Naehrig. Pairing-friendly elliptic curves of prime order, Springer, 2006.