Pairing-friendly elliptic curves of prime order

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

 Type Inproceedings Pages 319–331 Volume 3897 Series Lecture Notes in Computer Science

Previous Versions

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

> Publications > Pairing-friendly elliptic curves of prime order