Pairing-Friendly Elliptic Curves of Prime Order.
|Title||Pairing-Friendly Elliptic Curves of Prime Order.|
|Publication Type||Conference Paper|
|Year of Publication||2005|
|Authors||BARRETO, P. S. L. M., and M. Naehrig|
|Conference Name||Selected Areas in Cryptography -- SAC'2005|
|Date Published||february, 2006|
|Publisher||Lecture Notes in Computer Science - Springer Berlin / Heidelberg|
|ISBN Number||0302-9743 (Print) 1611-3349 (Online)|
Previously known techniques to construct pairing-friendly curves of prime or near-prime order are restricted to embedding degree . More general methods produce curves over 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 ρ ≡ 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 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 ρ; 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 ρ ~ q/(q–1).